hc11 program help

I need help writing a program that will take 20 random hex numbers and place then in ascending order.

Any help would be greatly appreciated.

IM

Reply to
Isaac Marroquin
Loading thread data ...

place

Can you write a program to find the largest of 20 hex numbers? Can you take that number and set it aside? Can you write a program to find the largest of the remaining 19 numbers? Can you guess what comes next?

Kelly

Reply to
Kelly Hall

place

Google for "bubble sort". Google for "random number generation".

This is basic stuff. Why do you need help? Is it homework?

Tip: a "hex humber" is just a number represented in hex format. I.e. there's nothing special about sorting "hex numbers".

Steve

formatting link
formatting link

Reply to
Steve at fivetrees

Change schools, the HC11 is a dead duck, you should be learning on something a little more contemporary. In the meantime:-

A = 19 t = 0 outloop: B = 0 inloop: X = &data (address of the data) if x[0] > x[1] t = x[0] x[0] = x[1] x[1] = t x = x+1 b = b+1 if B 0 goto outloop END

This is a simple bubble sort. It's been so long I hope I got it right ;@}

Al

Isaac Marroqu> I need help writing a program that will take 20 random hex numbers and place

Reply to
onestone

If you're planning on writing embedded code for a living sometime, then you'd be well advised to put in some study on sorting algorithms in general. The standard text is (or at least was) Vol 3 - "Sorting and Searching" of Donald Knuth's "The Art of Computer Programming" series.

If you just want a one-off fix for this, Google for "insertion sort". I'd recommend against using a bubble sort, since it's probably the most inefficient algorithm known to man or coder, and I'd personally mark you down if you used it in your project.

--
  Max
Reply to
Max

Hey, go easy on me, I just started taking this class. I asked for help, not to shoot me down with your criticizms.

Thanks for the help though, I appreciate it.

IM

Reply to
Isaac Marroquin

Gotcha. So you admit you want us to do your homework for you.

FOAD.

pete

--
pete@fenelon.com "there's no room for enigmas in built-up areas"
Reply to
Pete Fenelon

not

I admit to nothing! Besides, I asked for help. Help doesn't necessarily mean writing out the program for me.

Wouldn't complain if someone did though ;-)

IM

Reply to
IM

"Max" wrote

How would you score someone that used the "comb sort" variation of the bubble sort?

Reply to
Anthony Fremont

help, not

Geez Pete, it's not like he was trying to lie about it. He didn't ask anyone to do it for him, he just asked for some help.

Reply to
Anthony Fremont

That's the problem with public forums, you don't always get what you want. Had you lurked for a while you'd have known that many regulars get pissy about homework help, after all if you can't figure it out for yourself now, what will you do when you're meant to be a real engineer, many regulars also get pissy about people who can't even be bothered to try and help themselves. How hard is it to do a google search for "computer sorting algorithms" or something similar.

Al

Isaac Marroqu> Hey, go easy on me, I just started taking this class. I asked for help, not

Reply to
onestone

Now that's cheeky, I gave you the logic for it, isn't that enough ;@}

Al

IM wrote:

--
Please remove capitalised letters to reply
My apologies for the inconvenience
 Click to see the full signature
Reply to
onestone

I haven't seen comb sorts categorised as being a variation of a bubble sort. The term usually refers to a form of diminishing-interval sorting, with the classic "Shell" sort as the most common real-world example. Such methods often switch to a straight insertion sort for shorter intervals (as do the better implemetations of faster partition-exchange algorithms such as "Quicksort").

But to answer your question; I'd mark such a project quite highly, since it demonstrates that the student has at least done some minimal research into different sorting algorithms.. But, given that the list to be sorted is only 20 items long, the most appropriate algorithm is almost certainly a straight insertion sort, so I'd probably knock off a mark or two for using a more complex method which is less than optimal in the given case.

--
  Max
Reply to
Max

the

The first example that I saw was simply inner and outer loops (N*N) with the comparison interval shrinking until it became 1, at which point it became an ordinary bubble sort. I must admit that I haven't seen it mentioned much in any form, even though it's quite simple to implement. It's also quite efficient even when compared to quicksort methods with say 150,000 items.

;-) Got any job openings?

I would agree that for 20 items, efficiency techniques possibly aren't worth the effort. However, since an insertion sort is no less complex than a bubble sort (both are N-squared), I don't see what the big deal is with one vs another in insertion/selection/bubble sorts. I've seen mention of selection and insertion sorts running as much as 50% faster than a bubble sort, though I tend to be a bit skeptical of claims like that.

Reply to
Anthony Fremont

It's really very well known and documented under the name "Shell sort". Don Shell first wrote it up in 1959, so it's got a loooong history.

Errrrm .... no. Based on average number of comparisons, the efficiency of a shell sort is proportional to n^2 / e (roughly the same as a heapsort, and a little better than an insertion), while with Quicksort it's n log n. For large n, that's a HUGE difference.

The efficiencies stay in proportion, but insertion sort requires around half the number of comparisons of a bubble sort since, on average, it is only necessary to compare against half of each sub-list to find the insertion point in each pass. The difference can become significant with large n.

Easy to demonstrate by just counting the number of comparisons. Assuming random data, an insertion sort requires roughly half the effort of a bubble.

--
  Max
Reply to
Max

Some errors there. Shell is often competitive for small n, due to the small overhead. However both heapsort and quicksort are O(NlogN) algorithms, as is mergesort (suitable for lists). Bubble, insertion, and selection are all O(N*N), with the difference again being in the overhead. Quicksort is unique in the ability to have a very taut inner loop, thus reducing the overhead.

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
 Click to see the full signature
Reply to
CBFalconer

Ah yes, a slip there. Mind you, isn't order n log n only achievable with heapsorts if you use auxiliary vectors, rather than sorting in-place? But quicksort needs a stack, so .... humm.

It's maybe worth mentioning that the basic form of the quicksort algorithm has very poor performance on ordered data (each pass will only partition a single item from the vector). Don Knuth's "median-of-three" version fixes that, with minor overhead, but not all C library "qsort()" routines use it.

--
  Max
Reply to
Max

Heapsort and mergesort can easily function in place. Unlike quicksort, their worst case performance remains O(NlogN). For any 'median' or other partitioning quicksort can be driven into worst case (N*N) performance. See:

SOFTWARE?PRACTICE AND EXPERIENCE, VOL. 29(0), 1?4 (0 1999) A Killer Adversary for Quicksort M. D. MCILROY Dartmouth College, Hanover, NH 03755, USA

which I have on my system as "mdmspe.pdf". Googling for that might find it.

In addition, C library qsort need not be quicksort.

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
 Click to see the full signature
Reply to
CBFalconer

Not the incarnation of it I learned (and which features in TAOCP Vol. 3). Original Heapsort works entirely in-place, and it's O(n*log(n)) not just on average, but even in worst case, doing so.

More to the point, there's nothing requiring C library implementations to use Quicksort to implement qsort() _at_all_. One libc I know of uses merge sort.

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply to
Hans-Bernhard Broeker

with

it

implement.

Interesting. I've seen websites that do indeed suport this claim. I saw reference to it for the first time in a Byte magazine article. As indicated here:

formatting link
and here
formatting link
Shell is not referenced as having anything to do with its authorship at all. Credit seems to go to Stephen Lacey and Richard Box. It would appear that when refering to an insertion sort of decreasing comparison intervals, one should say Shell sort. However, when referring to a bubble sort with similar (same?) technique applied, it's a comb sort.

Reply to
Anthony Fremont

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.