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 ...
SORTING
Author
Message
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 98321 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
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?
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.
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.
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
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..)
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
}
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.
Quote:
Well, from the OP's statement, it is possibly up to 16 elements, and the OP specifically stated assembly.
Well, for 5 elements of an array
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.
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
"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)
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
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?
dbrion0606 wrote:
I know what that means, but I'm not sure everyone else here is so comfortable with vi (or ex).
:1,$s@5@16@g
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 ...".
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?).
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 98321 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
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).
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).
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.
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...)
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 98321 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
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).
But I wanted compilable c code boss
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 98321 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
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:
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.
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.
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 98321 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
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.
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.
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.
microcarl wrote:
Do you mean a recursive version of quicksort?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.
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:
'Tain't an acronym.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.
I would have "spelled" it O(N**2).
bobgardner wrote:
Big O notation is a mathematical notation for characterising functions. In computer science it can be used to characterise algorithmic complexity.
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.
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] |
 |
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)
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...
JohanEkdahl wrote:
The word you were looking for is polynomially.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.
Exponentially would be something like O(2**n).
Quote:
Heap sort and merge sort are O(n*log(n)).E.g. Quicksort is 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).
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
The feminists have already trademarked the Big O.
bobgardner wrote:
This isn't the Off Topic forum, Bob...
The feminists have already trademarked the Big O.
|
"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] |
|
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 98321 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
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?
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.)
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...