The Museum of HP Calculators

HP Forum Archive 17

 HP35s Sorting RoutineMessage #1 Posted by Nenad (Croatia) on 28 Aug 2007, 4:43 p.m. Hello, world The following is a small step for a man, but even much smaller for the mankind! What is so important in the program that follows? The fact that this is the only sorting routine I fully understand. Why? Because I learned it first time in Fortran IV on IBM 1130 in 1977 (imagine dinosaurs walking around). As it worked correctly at that time, I did not give even a try to understand and/or learn any other sorting procedure, just ported this one from one computer to another. This is how it looks like in HP Basic (if I typed here the original IBM 1130 program from my memory, who would care about it anyway): ```! HP Basic Sorting Routine DIM A(800) INPUT "N=", N REDIM A(N) ! Input unsorted data FOR I=1 TO N DISP I INPUT A(I) NEXT I ! Sorting FOR I=1 TO N-1 FOR J=I+1 TO N ! edited, thanks Gerson IF A(I)>A(J) THEN TEMP=A(I) A(I)=A(J) A(J)=TEMP END IF NEXT J NEXT I ! Output sorted data FOR I=1 TO N PRINT I, A(I) NEXT I END ``` The presented listing in HP Basic serves to preserve talking too much about the HP35s program itself. HP35s program listing // edited, thanks all ```*LBL S ! asterisk should have been omitted, but this reminds me of my HP-67 time INPUT N ! # of data points 1 + STO I STO (I) ! reserve variable space+1 RCL N 1E3 / 1 + STO I S013: RCL (I) VIEW(I) ! prompt for data input STO(I) ! here I input my data point ISG I GTO S013 SF 10 EQN "SORTING" PSE CF 10 RCL N 1 - 1E3 / 1 + STO I S030: RCL N 1E3 / RCL I IP + 1 + STO J S039: RCL (I) RCL(J) xy? x>

 Re: HP35s Sorting RoutineMessage #2 Posted by Vincze on 28 Aug 2007, 4:57 p.m.,in response to message #1 by Nenad (Croatia) Am I right to assume that you just keep entering data somehow? What let it know when you done entering data? **Edit** Never mind, I see answer on line S002. Duh... Edited: 28 Aug 2007, 4:58 p.m.

 Re: HP35s Sorting RoutineMessage #3 Posted by Don Shepherd on 28 Aug 2007, 6:46 p.m.,in response to message #1 by Nenad (Croatia) Ahh, the bubble sort. It has always held a high place in my minimalist philosophy.

 Re: HP35s Sorting RoutineMessage #4 Posted by Thomas Radtke on 29 Aug 2007, 6:11 a.m.,in response to message #3 by Don Shepherd Doesn't look like bubblesort. AFAIR, bubblesort compares only adjacent entries and usually takes several runs.

 Re: HP35s Sorting RoutineMessage #5 Posted by Gerson W. Barbosa on 28 Aug 2007, 7:46 p.m.,in response to message #1 by Nenad (Croatia) Hello Nenad, Quote:```! Sorting FOR I=1 TO N-1 FOR J=1 TO N``` This should be ```! Sorting FOR I=1 TO N-1 FOR J=I+1 TO N``` shouldn't it? Would you try the following classic variation for the bubble-sort algorithm and see how it would perform on the 35s? ```! HP Basic Sorting Routine DIM A(800) INPUT "N=", N REDIM A(N) ! Input unsorted data FOR I=1 TO N DISP I INPUT A(I) NEXT I ! Sorting FOR I=1 TO N-1 K=I FOR J=I+1 TO N IF A(K)>A(J) THEN K=J END IF NEXT J IF I<>K THEN TEMP=A(K) A(K)=A(I) A(I)=TEMP END IF NEXT I ! Output sorted data FOR I=1 TO N PRINT I, A(I) NEXT I END``` Regards, Gerson. Edited: 28 Aug 2007, 7:47 p.m.

 Re: HP35s Sorting RoutineMessage #6 Posted by Paul Dale on 28 Aug 2007, 7:48 p.m.,in response to message #5 by Gerson W. Barbosa Quote: This should be ```! Sorting FOR I=1 TO N-1 FOR J=I+1 TO N``` shouldn't it? [/pre] This makes it more efficient but it works either way. By the way, it isn't bubble sort. - Pauli

 Re: HP35s Sorting RoutineMessage #7 Posted by Gerson W. Barbosa on 28 Aug 2007, 8:18 p.m.,in response to message #6 by Paul Dale Quote: By the way, it isn't bubble sort. Which one? The original algorithm presented by Nenad or the variation? I always thought the former was bubble-sort, but I may be wrong. Gerson.

 Re: HP35s Sorting RoutineMessage #8 Posted by Paul Dale on 28 Aug 2007, 8:34 p.m.,in response to message #7 by Gerson W. Barbosa Neither is bubble sort. They are known as selection sort. Similar dismal performance though. Wikipedia is good for information (and animations) about bubble sort and selection sort. - Pauli Edited: 28 Aug 2007, 8:35 p.m.

 Nice animations! Thanks! NTMessage #9 Posted by Gerson W. Barbosa on 28 Aug 2007, 8:52 p.m.,in response to message #8 by Paul Dale

 Re: HP35s Sorting RoutineMessage #10 Posted by Don Shepherd on 28 Aug 2007, 9:13 p.m.,in response to message #6 by Paul Dale Sure looks like bubble sort to me. You are working your way throught the array, swapping cells side-by-side so the larger is on the right, and ultimately the larger cells "bubble" to the top.

 Re: HP35s Sorting RoutineMessage #11 Posted by Paul Dale on 28 Aug 2007, 9:17 p.m.,in response to message #10 by Don Shepherd My mistake, the original is bubble, just coded funnily. Gerson's is selection. - Pauli

 Re: HP35s Sorting RoutineMessage #12 Posted by Don Shepherd on 28 Aug 2007, 9:36 p.m.,in response to message #11 by Paul Dale Thanks Pauli. Now I am spending my evening reminiscing about sort strategies from 30 years ago! We are such creatures of the past. I remember in school we always talked about how *bad* the bubble sort was, although it was great in its simplicity. Then one day I found out about the quicksort, and that seemed much more efficient. The sad truth is, in all my jobs, I never had the need to implement a sort routine; there was always one already there!

 Re: HP35s Sorting RoutineMessage #13 Posted by Vincze on 29 Aug 2007, 8:50 a.m.,in response to message #12 by Don Shepherd Yes, I recall to. It be interesting if we could test other sort data structures and see which is quickest on 35s. We all know that Bubble sort is not most efficient, but it is simple. It look like Nenad's bubble sort is the more enhanced one that adds some efficiencies. (all elements in position >= n-i are already in proper position after iteration i. And step to determine when everything in order to prevent unnecessary iteration). It be nice if we can try quicksort or Shell sort, or even Radix sort. I am not sure if these would be possible in RPN, but it would be interesting to try. My friend, Nenad, I hope you write this sort up and submit to Datafile to share with others. It is nice work. Edited: 29 Aug 2007, 8:51 a.m.

 Re: HP35s Sorting RoutineMessage #14 Posted by Ed Look on 29 Aug 2007, 1:17 p.m.,in response to message #5 by Gerson W. Barbosa I need a routine to sort from twenty to oh, say a hundred numbers, and then do some basic statistics on them, like average, median, etc., and have been intending for a couple of weeks now to code it in my 35s (and then 33s) I'll try to find some time... probably between the end of baseball on TV and bedtime (what, about twenty minutes??) and come up with something. I will also NOT look at these posted programs and then I'll probably revive this thread and compare to see how poorly mine looks in relation to yours. But, I did see something that has given me a big hint to start with- I might just try a FORTRAN sorting routine first (or maybe a 48G+ RPL routine first) and then translate to 35s RPN keystrokes! That might be easier than just doing it cold from the 35s keyboard.

 Re: HP35s Sorting RoutineMessage #15 Posted by Don Shepherd on 29 Aug 2007, 2:28 p.m.,in response to message #14 by Ed Look Ed, the 17bii or 17bii+ can do it all without programming! I realize you probably want to write a program, though.

 Re: HP35s Sorting RoutineMessage #16 Posted by Vincze on 29 Aug 2007, 3:26 p.m.,in response to message #15 by Don Shepherd How can 17bii do it without program? Are you talking just statistics functions, or sorting as well? **EDIT** Never mind, I go out to HP site and download manual for 17BII, and yes, it can sort list of numbers AND do statistical calculations. That too cool. Edited: 29 Aug 2007, 3:40 p.m.

 Re: HP35s Sorting RoutineMessage #17 Posted by Bruce Bergman on 29 Aug 2007, 4:36 p.m.,in response to message #16 by Vincze Yes it is (cool, that is). I think the 17bii/17bii+ gets a bum rap at times; it's much more powerful than I ever thought, and IMHO puts the 12c to shame. It's easy to gloss over what it does, but Don illustrates the power it has very simply implemented. thanks, bruce

 Re: HP35s Sorting RoutineMessage #18 Posted by Don Shepherd on 29 Aug 2007, 5:27 p.m.,in response to message #16 by Vincze Vincze, now that's research!! : ) Don

 Re: HP35s Sorting RoutineMessage #19 Posted by Ed Look on 29 Aug 2007, 5:23 p.m.,in response to message #15 by Don Shepherd Ah, Don, I no gots no 17bii, + or - . :(

 Re: HP35s Sorting Routine (EDITED)Message #20 Posted by Nenad (Croatia) on 29 Aug 2007, 9:18 a.m.,in response to message #1 by Nenad (Croatia) Thank you all for your posts and comments, they are really appreciated. I have edited my original post upon your comments. Just forgot to add the following to the edited post: ```LBL S LN=225 CK=4BA1 ``` (the CK info might be useless, who knows) Gerson: You are perfectly right. The correct statement in HP Basic program is (and was intended to be): ```FOR J=I+1 TO N ``` All: In my original post I have made two essential mistakes: the one above and the one in the HP35s program. In the latter the loop above began at J=I instead at J=I+1. It is obvious that I still remember the original FORTRAN IV routine correctly, but I was a bit careless transcribing my original post from my notebook (not a computer, but a real notebook, that I cary with me down to the seashore to write down such thoughts;) Never mind, my post is now corrected, though not very useful. Imagine somebody entering up to 800 numbers into the HP35s, just to sort them (as he/she cannot transfer these data to something else, because of the lack of I/O, but this is another story).

 Re: HP35s Sorting Routine (EDITED)Message #21 Posted by Arne Halvorsen (Norway) on 29 Aug 2007, 9:26 a.m.,in response to message #20 by Nenad (Croatia) Have you tried to sort 800 numbers on the hp35s :-) Fun to know how long time program would use. I guess you could write a small program to fill it up with random numbers to be sorted. Actual, if there would be a use of a sorting numbers on the hp35s it would be results of other programs I guess. Edited: 29 Aug 2007, 9:27 a.m.

 Re: HP35s Sorting Routine (EDITED)Message #22 Posted by Maximilian Hohmann on 29 Aug 2007, 10:39 a.m.,in response to message #21 by Arne Halvorsen (Norway) Hello! Quote:Have you tried to sort 800 numbers on the hp35s :-) There is a very nice animated comparison (+ background information) about various sorting algorithms to be found here: http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html Saves you the hassle to enter all those numbers into the 35s, that is really not the right machine for this kind of stuff. Greetings, Max

 Re: HP35s Sorting Routine (EDITED)Message #23 Posted by Vincze on 29 Aug 2007, 11:06 a.m.,in response to message #22 by Maximilian Hohmann My friend Max, it took this Hungarian a little time trying to figure out how to make animations work. I kept clicking on links and get java code, but finally this Hungarian wise up and click on picture. That is very cool indeed. You also very right that HP35s not proper tool to sort large numbers (or even small number set). In real life, I would use SQL server to do that, or Excel spreadsheet for small set (or my own brain). I think this is an excellent study though by our friend Nenad on how indirect variable are used. I know, I learn much from his program on how to implement this on 35s.

 Re: HP35s Sorting Routine (EDITED)Message #24 Posted by Gerson W. Barbosa on 29 Aug 2007, 12:07 p.m.,in response to message #22 by Maximilian Hohmann Thanks for the link! I thought QuickSort was tops, now I see there is Fast QuickSort. What will come next? Rapid Fast QuickSort? :-) Regards, Gerson.

 Re: HP35s Sorting Routine (EDITED)Message #25 Posted by Vincze on 29 Aug 2007, 11:27 a.m.,in response to message #21 by Arne Halvorsen (Norway) My friend Arne, I not try 800 items, but as an exercise, I try 100 items. I let calculator run for 10 minutes and it still running. I abort program as I needed calculator for something, but I would imagine 800 would take considerable amount of time with simple bubble sort algorithm.

 Re: HP35s Sorting Routine (EDITED) - Look at current month DatafileMessage #26 Posted by Gene Wright on 29 Aug 2007, 1:48 p.m.,in response to message #25 by Vincze I have been printing sorting routines in Datafile for the 35s. The sorting routine (I put) in the 35s indirect module is a very bad implementation - of course, I wrote it! :-) I then used an updated sort from Miguel in the current month along with some tests for speed. Random, sorted, reverse sorted, to see how the timings went. Used a specified seed of 0.123456789 and filled the first 100 indirect registers with the random numbers generated. Should be repeatable and a good test to see how a sort works. Timings for Miguel's routine were: Random list of 100 from 0.123456789 seed: 230 seconds Resort of sorted list: 17 seconds Worst (?) case of inverse sorted list: 420 seconds Much better than the one I used in the module. :-)

 Re: HP35s Sorting Routine (EDITED) - Look at current month DatafileMessage #27 Posted by Vincze on 29 Aug 2007, 3:50 p.m.,in response to message #26 by Gene Wright My friend, Gene, I normally just skip article you write in Datafile. I just kidding my friend. :) Actually, I have not studied current issue much, but I will look at it when I have chance.