HP35s Sorting Routine - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: HP35s Sorting Routine (/thread-123510.html) HP35s Sorting Routine - Nenad (Croatia) - 08-28-2007 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>= 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 Routine (EDITED) - Nenad (Croatia) - 08-29-2007 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) - Arne Halvorsen (Norway) - 08-29-2007 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) - Maximilian Hohmann - 08-29-2007 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) - Vincze - 08-29-2007 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) - Vincze - 08-29-2007 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) - Gerson W. Barbosa - 08-29-2007 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 - Ed Look - 08-29-2007 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 Routine (EDITED) - Look at current month Datafile - Gene Wright - 08-29-2007 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 - Don Shepherd - 08-29-2007 Ed, the 17bii or 17bii+ can do it all without programming! I realize you probably want to write a program, though. Re: HP35s Sorting Routine - Vincze - 08-29-2007 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 Routine (EDITED) - Look at current month Datafile - Vincze - 08-29-2007 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. Re: HP35s Sorting Routine - Bruce Bergman - 08-29-2007 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 Routine - Ed Look - 08-29-2007 Ah, Don, I no gots no 17bii, + or - . :( Re: HP35s Sorting Routine - Don Shepherd - 08-29-2007 Vincze, now that's research!! : ) Don Re: HP35s Sorting Routine - Drago Pejic - 08-30-2007 Without any intension to make any commercial advertisement or expose a big ego, I am sure that Data Integrity Institute Inc. has developed and owns the world fastest and most efficient sort algorithm. It is non comparison sort, something very remotely related to radix sort, but it is not radix sort or any academically described. Remember all quick sorts are so called comparison sorts where you have two kinds of comparisons: - active comparison, where each item is compared (of course respecting the item type, like integer, float, string, etc.) to others, sometime several times - passive comparison, where the item position (which is always an integer) in the array and eventually in the file is compared and check that is inside boundary It is apparently that any comparison will tremendously slow down sorting process. Data Integrity Institute Inc. sorting algorithm does not perform either active (item) comparison or passive (position of the item) one. That allows Data Integrity Institute Inc. Copula Application Specific Enterprise ETL Appliances to process any, does no matter how big and complex data vault, within 3 hours. Data Integrity Institute Inc. sorting algorithm requires least 512 MB of memory per CPU core in the 32 bit environment and least 128 GB of memory per CPU core in the 64 bit environment. If there is no such memory in the 64 bit environment, efficiency of 64 bit will be several times better than 32 bit, but not such significantly as it could be if there is enough memory available, when it really blasts. I would like to discuss this, but I am not sure if it is appropriate here. I do not want distract anybody. Also, I can not disclose any secret detail about Data Integrity Institute Inc. sorting algorithm, because it is our most valuable asset and competitive advantage. I can tell that I had two major revelations, something like religious bliss, in ten years while I was obsessed with sorting problem. One was when I went behind quick sort and comparison, and another when I discover how to handle resources in an perfect arrange, which is major obstacle why is radix sort only an academic category. To Nenad from Croatia: Puno pozdrava Nenade. Drago Pejic, M. Sc., F.L.M.I. http://www.dataintegrityinstitute.com Edited: 30 Aug 2007, 8:03 a.m. Re: HP35s Sorting Routine - Arne Halvorsen (Norway) - 08-30-2007 Sound cool... What are the complexities; average case and worst case? As for quick sort but with less overhead? Edited: 30 Aug 2007, 8:12 a.m. Re: HP35s Sorting Routine - Drago Pejic - 08-30-2007 Data Integrity Institute Inc. Copula Application Specific Enterprise ETL Appliance processes data record that is composed from one or more fields of any type of data, usually previously almost ordered, but not every time, of course, so it always performs as worst case. The advantage of the algorithm is that ignores any scenario and processes what is there, as is. Source data records are stored in the file, or part of file. The one sort task can handle 2^31 files (or described part of file, ignoring rest), each file size of 2^63, simultaneously. Target data are stored in the specified file or array of files. The sort process takes a chunk of the file into memory, process that and store in the target file structure. It is not in place sort so source data will be preserved. All SQL engines (DB2, Oracle, etc.) utilize a comparison sort (quick sort, heap sort, merge sort) that are similarly efficient. They are designed for transactional processing (account update, flight reservation, etc.) that handles one record at time. Now, everybody wants to use an SQL engine for analytical processing (data warehouse, business intelligence, data mining) where millions or records need to be handled simultaneously. It is hard to explain that SQL, designed for transactional processing, can not efficiently do that. Mayor problem is comparison sort (you compare each item to others plus you check the item position in the array every time) and so called B tree indexing where in order to locate the item in the index you have to travel for each item along many tree branches. B tree is great concept to locate a singe item, but not for massive simultaneous processing. Drago Pejic, M. Sc., F.L.M.I. http://www.dataintegrityinstitute.com Re: HP35s Sorting Routine - Arne Halvorsen (Norway) - 08-30-2007 Pretty interesting... slighty related to what you address, just installed latest mysql for a data analysis app and performance just dropped! Thing is ofcourse now default installation uses a database engine that implements transaction. Reconfigured to use good old non transact engine and performance back. Real force of mysql is that you can choose!