HP Forums

In this learning module:

Indirect sorting program

A really, really bad sorting routine is presented in Example 2 (ok, I wrote it - that's why it's bad). I was in a hurry, etc. :-)

I'd like to challenge new 35s owners to work on developing a fast, short indirect register sorting program.

Input to the program should be a number like X.YYY, specifying the first and last indirect register to be sorted. I would assume ascending order.

All lettered registers are available for use, but try not to use many. :-)

Winner ought to be determined by the size x run time method used at HHC conferences.

For the sample matrix, I'll try digging up the old "Cheeseman" array used in the PPC Journal to test PPC ROM sorting routines. Might be fun to see how long it takes.

Regardless, now that we have some registers worth sorting, it is time to dramatically improve upon my pitiful effort!

Gene

Edited: 25 July 2007, 8:49 a.m.

Hi, Gene:

Gene posted:

"Winner ought to be determined by the size x run time method used at HHC conferences."
May I suggest that, for practical, real-life purposes other criteria would be more useful, namely (a) The shortest routine, running time a secondary consideration within reason, and (b) The fastest routine, size a secondary consideration, again within reason.

The rationale is that, usually, you are either constrained for space (because you need to be capable to process as much data as possible) in which case you'll certainly want to minimize program size above all, or else you're not specially constrained for space, in which case you'll want your sort to proceed as fast as possible.

The size x run time criterium seems to me to fulfill neither of those practical requirements and it was probably used just to ease the judges' cumbersome and difficult task of objectively selecting a winner.

As such, I'll propose that people accepting the challenge would submit either one or two routines, each individually optimized for the speed/size criteria.
That's certainly what I'll do, as my primary goal is to produce maximally useful routines, not winning challenges. :-)

P.S.: Sorting methods also greatly vary in performance depending on the nature of the data being sorted, i.e., some methods that are nearly optimal for quasi-random data may perform abysmally if the data are already almost sorted or reverse-sorted.

So I would suggest that timings should be given for:

1. A random-data array, generated by using the HP35S' built-in random-number
   function starting from the seed Pi. This will guarantee repeatability and the same array for everyone.

2. A perfectly sorted array: 1, 2, 3, ..., n

3. A perfectly reverse-sorted array: n, n-1, ..., 3, 2, 1

4. An array with all elements equal: 1, 1, 1, ... , 1
   

I guess many participants will find that their routine does well with some of the array types but not so well with others. Depending on the real-life application this might be important, as having data which is almost perfectly sorted to begin with is quite common, actually.

Edited: 25 July 2007, 9:13 a.m.

Hallo!

Quote:

---

... for practical, real-life purposes ...

---

I think, that for practical, real-life purposes nobody will ever enter large numbers of data into a pocket calculator with no I/O capabilities whatsoever with the intention of sorting them as quickly as possible ;-)

So I would rather consider this challenge as an intellectual excercise akin to solving a chess-puzzle and forget everything I ever knew about real-life issues while working at it...

Greetings, Max

Quite good points, Valentin. The shortest routine would be nice as would the fastest, particularly with random data.

I do think these have a value. There are often times one needs to rearrange numbers in a program, even without I/O. It may only be 10, 20, or 30 numbers, but that's not unreasonable, IMO.

So, who will be first to dramatically improve upon my pitiful efforts? :-)

Hi, Maximilian:

Maximilian posted:

"I think, that for practical, real-life purposes nobody will ever enter large numbers of data into a pocket calculator with no I/O capabilities whatsoever with the
intention of sorting them as quickly as possible ;-)"
I beg to difer. I certainly don't do it very frequently, if at all, but can think of many instances where this could be desirable, from a surveyor out in the field (rough terrain) taking a number of measurements and doing some computations with them on the fly, to someone trying to come up with a solution to some "lottery numbers" challenge which requires sorting 6 numbers as fast as possible, say. The possibilities are limitless and there are incredibly varied users out there engaged in a miriad activities.

I think that a powerful, solid, and relatively inexpensive calc such as the HP35S will indeed get used for many real-life purposes, be they work-related, fun-related, or whatever. This being so, developing programs for it deserves to be taken with a professional attitude, as I'm sure most of us always strive for actually.

Thanks for your comments and

While surveyors do need to enter lots of numbers into handheld calculators, I can't think of a time when they'd need to sort a list of numbers. . .

The biggest issues that they are grumbling about right now are:

1) Lack of good R>P P>R conversions.
2) lack of HMS+ HMS-

TW

Some statistical calculations, like Spearman Rank correlation require the data to be sorted in order to obtain the ranks (sort order) for the values.

Namir