SORTING

Go To Last Post
41 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hello
i wish to know how to program atmega32 assembly language for sorting ascending order ( from 0x40 on-wards) and the result need to store in 0x50 on-wards any one help me please ...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Are those RAM or flash addresses?

I'm guessing RAM as writing to flash is extremely tricky. But then there are two further questions I wonder about:

1) RAM starts at 0x60 in a mega32 in fact so how could you use 0x40 and 0x50?

2) if it is in RAM how does your input data get to 0x40 in the first place?

I assume this is a school project? Can you just copy the entire assignment here rather than paraphrasing it?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It sounds exactly like a school project.

I cannot think of anything more stupid to waste the pupil's time.

Having got that off of my chest, Google for any Assembly Language Textbook.

It does not matter whether you find a program written for 6502, Z80, 6809, 8051, ...
They all have similar instructions. You just have to replace with the equivalent AVR opcodes.

This requires you sitting down with an AVR manual and an 6502/Z80/.. manual.

There was a whole series of ASM textbooks written by Lance Leventhal. As far as I can remember, they all had this particular exercise. 40 years ago, CPUs were fairly slow and expensive. C compilers were stupid and did not really work very well for small 8-bit CPUs. Hence my generation was brought up on ASM. The world has moved on. It sounds as if your teacher has not !

While you are doing this pointless exercise, you can invent methods of torture for your teacher.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

While you are doing this pointless exercise, ...

Pointless? I wish a lot more posters here would have gone through the equivalent of my "Algorithms" course that came right after introductory programming. Lists, queues, trees, sorting, ... Then follow up later with the advanced topics--heavy on Knuth.

Now, if the text and classroom discussion had no mention of sorting before the assignment, then it might be different. Still, it could be a "challenge" if the students are expected to research simple sorting methods.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

its a classic computer science degree question. We had to do all the methods of sorting and show each benefits and down falls... like bubble... ripple etc.

we had to do it in Pascal... and there was no internet then. get the books out....

google is your friend

read this.. http://en.wikipedia.org/wiki/Sor...

Dam! that's actually a good article!

Nigel

Last Edited: Tue. Sep 3, 2013 - 01:33 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
I wish a lot more posters here would have gone through the equivalent of my "Algorithms" course that came right after introductory programming.

+1

(Now let's just wait for Uncle B for the -1..)

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well, for 5 elements of an array, the worst algorithm (O(n2) with too many swaps) wikipedia shows is not slower than much better algorithms and perhaps avr-gcc -S can translate it into assembly (or gcc -S if OP wants PC assembly ...). I tested it on a PC before putting it on an arduino to filter ADC values... BTW : it needs some adaptation, as ihe array was sorted in place

int median(/* uint16_t tablo[5] */ ){
     for (uint8_t i =0; i< (5 -1) ; i++) { 
       for (uint8_t j = (i+1); j< 5; j++) {
         if (tablo[i] > tablo[j]) {
           uint16_t medaux = tablo[i];
           tablo[i] = tablo[j];
           tablo[j] = medaux;
         }
       }
     }
     return tablo[2]; // used to compute a median
}
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have no problem with teaching sorting algorithms.

I do think that it is a little pointless to do it in ASM.

For a start, anything more than bubble or insertion gets hairy in ASM.

Likewise, stacks, deques, queues, lists, ... are all easier to teach and understand in Pascal, C, Java, ...

Most importantly, having learned about their various 'features', the student knows which is the more suitable type to use and select the appropriate library classes.

My argument is always: "learn how to find app notes, data sheets and libraries", then "learn how to use them properly"

Yes. As a final year project, you might ask the best students how to improve the "standard solution" to a resource limited micro.

If you give the 'less-endowed' students this sort of assignment, they probably fail to spend adequate time and effort on the "learn docs properly".

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Well, for 5 elements of an array
Well, from the OP's statement, it is possibly up to 16 elements, and the OP specifically stated assembly.

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes. And the whole assignment would have been perfectly appropriate 30-40 years ago.

dbrion0606's example could show
1. the algorithm
2. the O(n) efficiency

It is about time that I take my dog for a walk.
I will continue to be rude about 'out-of-date' teachers.
Others will have a different view.

Incidentally, while I think ASM should be an 'advanced' minor subject, I really feel that all Science students should understand Ohm's Law and know how to use a calculator.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I have no problem with teaching sorting algorithms.

I do think that it is a little pointless to do it in ASM.


I missed the assembler part. +1 on this quote of David too then.. :D

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

"it is possibly up to 16 elements,"

:1,$s@5@16@g
or adapt with a brain ... (BTW : such a O(n2) sort is not that far when n grows : I verified it had no influence with n=5, but it would be rather unconsistent if asm coding led to slower code by choosing a slow algorithm.....

" and the OP specifically stated assembly."

And I wrote xxxx-gcc -S could convert into asm for xxxx s cpus (OK: "only avr's and pc : I tested masp430, too. That makes the choice of language a detail.... (I do not know I wrote c or c++ as both xxx-gcc and xxxx-g++ accept it)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

david.prentice wrote:
Yes. And the whole assignment would have been perfectly appropriate 30-40 years ago.

and know how to use a calculator.

David.

in training (RAF) we were not allowed to use calculators until we could prove how they worked!

Nigel

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
dbrion0606's example could show
1. the algorithm
2. the O(n) efficiency

No, David, you are too kind:
it is O(n2) unefficiency (but it satisfies me for 5 values).

And if Mr OPs find it hard to understand and to improve the generated assembly, what about really efficient sorting algorithms?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

dbrion0606 wrote:
:1,$s@5@16@g
I know what that means, but I'm not sure everyone else here is so comfortable with vi (or ex).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I do think that it is a little pointless to do it in ASM.

I missed the assembler part. +1 on this quote of David too then..


If it is an assembly language class, I don't see any problem with a [trivial] sort as an exercise. Not even getting into efficiency or classic/proven algorithms, it is a good assembler exercise even if brute-force "find the smallest, then the next smallest, then ...".

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
I know what that means, but I'm not sure everyone else here is so comfortable with vi (or ex).

Well, I suppose OP has ... a comfortable brain (you forgot to quote everything, did not you?).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Quote:
I do think that it is a little pointless to do it in ASM.

I missed the assembler part. +1 on this quote

Key things in assembler are learning things like index register techniques. While the actual sort itself may be a fairly pointless exercise I would have thought that implementing it in Asm would exercise some of the bits that need the most exercising so it seems like a perfectly valid assignment to me.

(I guess OP has gone to bed though).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But would understanding / maybe improving a computer generated assembler file be such a bad exercice?
(the only time I wrote large pieces of code in 6809 assembly, 34 years ago, I wrote (as comments) what I wanted to be done in Algol/Pascal and was very unhappy the translation could not be made automatically).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I would have written directly in 6502 assembly language 40 years ago. In fact, I would probably write an insertion sort in 6502 today, and then translate to AVR.

I learned C some years later. And yes, I would always choose C or another HLL now. Then hand-optimise the ASM that the compiler generated.

Oh, I was trying to type a generic Big-Oh notation. i.e. n to represent N1, N1.5, N2, N3 etc

David.

Yes. As an ASM exercise, sorting certainly makes a good test. I would still opt for a student that knows Ohms Law than ASM expertise.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have run into a situation where I need a sort on an AVR. I have a CAN bus card with an AT90CAN32 on it and I can capture a bunch of 8 bytes can pkts into ram, but the pc program that I use with the commercial can scanner (kvaser leaf) has a neat feature that shows the opcodes sorted by opcode as they come in. I have no idea how to do this in c on the avr. In fact I dont think it can be done. (The last sentence was a tease to get some c code to try out... Thankx in advance...)

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I have no idea how to do this in c on the avr

Knuth algorithms should implement the same on any CPU whether it is i386 or AVR (if you pay attention to type widths).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But I wanted compilable c code boss

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

How complicated is it to simply code an algorithm into a particular language?

Anyway if you search any kind of well known sort (bubble, quick, etc) you are bound to find it in several languages on Wikipedia.

BTW doesn't your C compiler library offer:

http://www.nongnu.org/avr-libc/u...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Imagecraft stdlib.h doesn't have a qsort, so I looked in the ansi stdlib, and it doesn't seem to be there either. So shucks.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The hardest sorting method we did in college, I think, was by recursion. The fear was that you would run out of ram before the sort was finished and the machine would crash. Realize, though, back then we were using MC68HC811E2 controllers.

You can avoid reality, for a while.  But you can't avoid the consequences of reality! - C.W. Livingston

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The GCC C library is open source of course ;-)

So...

http://svn.savannah.nongnu.org/v...

(but no guarantees about how generic this C is)

Sorry to OP for OT.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

With the limited resources of a microcontroller, you are never going to sort large arrays. So O(N1.5) or O(N2) are really not going to make much difference.

In fact the simpler algorithms that may be O(N2) may be appalling for large N but are faster for trivial N.

I am sure that you will find every popular algorithm written in every popular language. Shellsort is non-recursive and pretty efficient.

Knuth has a whole volume on Sorting and Searching.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I never saw O(N2) in EE school. Must be a compsci term. In journalism school they tell you to spell out acronyms on first use.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

microcarl wrote:
The hardest sorting method we did in college, I think, was by recursion. The fear was that you would run out of ram before the sort was finished and the machine would crash. Realize, though, back then we were using MC68HC811E2 controllers.
Do you mean a recursive version of quicksort?
IIRC the way to handle that is to recurse on the smaller subproblem and iterate on the other.
If recursion on both was required, I suppose one could find another pivot.

My usual pivot selection was the median of first, last and middle.

bobgardner wrote:
I never saw O(N2) in EE school. Must be a compsci term. In
journalism school they tell you to spell out acronyms on first
use.
'Tain't an acronym.
I would have "spelled" it O(N**2).

Iluvatar is the better part of Valar.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

bobgardner wrote:
I never saw O(N2) in EE school. Must be a compsci term. In journalism school they tell you to spell out acronyms on first use.
Big O notation is a mathematical notation for characterising functions. In computer science it can be used to characterise algorithmic complexity.

Also check out Sorting algorithms.

JJ

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I bet that O(N2) is explained in wikipedia under the sorting topic; else, they give a link -and never went to a journalism school-;
Bruteforce sorting (compute the min of the N elements, then the min of the N-1 remaining ....) teads to N+(N-1)+...+1 comparisons -and maybe swaps, if it is in place- i.e N*(N+1)/2 comparisons: when N becomes large, it grows like N**2/2. When N is small, it does not matter (I verified 5 was small enough -5*3 comparisons-; ex if you make a pivot on the median of the mean, median and max, you have to make 5*3 scans to find mean, max and avg +2 comparisons before starting a sophisticated sort: from the very beginning, sophisticated sorts are penalized for small arrays; perhaps N=16 remains small enough, too)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

http://en.wikipedia.org/wiki/Big...

Something like this: Big O notation is (in CS) used for classifying algorithm depending on the amount of input. An algorithm that is O(1) does not vary in run time, for O(n) the variation is linear proportional to the sie of the input, for O(n**2) it is exponentially (squared) to the size of the input.

The "brute force" sorting algorithms (bubble-, insertion-sort) are O(n**2).

E.g. Quicksort is O(n*log n).

Apart from being a convenient way of talking about different classes of sorting algorithms, it has little use small(ish) for microcontroller apps.

YMMV, but in general pick any O(n**2) algorithm you are familiar with and use that. The advantages of using an O(n*log n) algorithm comes mainly with bigger data sets.

http://en.wikipedia.org/wiki/Ins...
http://en.wikipedia.org/wiki/Bub...

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

JohanEkdahl wrote:
http://en.wikipedia.org/wiki/Big...

Something like this: Big O notation is (in CS) used for classifying algorithm depending on the amount of input. An algorithm that is O(1) does not vary in run time, for O(n) the variation is linear proportional to the sie of the input, for O(n**2) it is exponentially (squared) to the size of the input.

The word you were looking for is polynomially.
Exponentially would be something like O(2**n).
Quote:
E.g. Quicksort is O(n*log n).
Heap sort and merge sort are O(n*log(n)).
Quicksort is not, it is O(n**2).
Big O is a bound on the worst case.
That said, most cases give one n*log(n).
Quicksort, heap sort and merge sort are omega(n*log(n)), which means that the best case is n*log(n).
Bubble sort and insertion sort are omega(n).

Iluvatar is the better part of Valar.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Quicksort is not, it is O(n**2).

Bob will be happy I am slowly forgetting the CS stuff.. Well-well, 35 years is not a bad memory retention time. :D

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The feminists have already trademarked the Big O.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

bobgardner wrote:
The feminists have already trademarked the Big O.
This isn't the Off Topic forum, Bob...

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I cannot help thinking OP has been scared away :-(

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
I cannot help thinking OP has been scared away :-(

Yeah, and it's up to us to assume he's either digging into a good book on searching algorithms, or joining the next available party.... Would massaging his android smartphone count as being a compromise in between?

Einstein was right: "Two things are unlimited: the universe and the human stupidity. But i'm not quite sure about the former..."

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

May be he did both (wikipedia pseudo code looks like C; once coded into real C, tested on a PC and translated into avr assembly, there remains a lot of time for parties.)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Exactly as my mother told me when i was young: "First yo do your homework, THEN you can go out for playing!!" I see, times don't seem to have changed - or both of us are dreaming about today's student's priorities...

Einstein was right: "Two things are unlimited: the universe and the human stupidity. But i'm not quite sure about the former..."