▼
Posts: 172
Threads: 21
Joined: Sep 2005
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)
x<y? ! In case of reverse sort change to x>y?
x><y ! No need for TEMP variable, this is what I like
STO (J)
x><y
STO (I)
ISG J
GTO S039
ISG I
GTO S030
SF 10
EQN "FINISHED"
PSE
CF 10
1
RCL N
1E3
/
+
STO I
S060: VIEW (I)
RCL (I)
ISG I
GTO S060
RTN
Note: In our language there is an expression "A jobless priest baptises little goats". Certainly you can notice from the entire post above that I am still on vacations;)
Edited: 29 Aug 2007, 9:01 a.m. after one or more responses were posted
▼
Posts: 376
Threads: 35
Joined: Jul 2007
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.
Posts: 1,392
Threads: 142
Joined: Jun 2007
Ahh, the bubble sort. It has always held a high place in my minimalist philosophy.
▼
Posts: 1,089
Threads: 32
Joined: Dec 2005
Doesn't look like bubblesort. AFAIR, bubblesort compares only adjacent entries and usually takes several runs.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Posts: 1,392
Threads: 142
Joined: Jun 2007
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
My mistake, the original is bubble, just coded funnily.
Gerson's is selection.
- Pauli
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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!
▼
Posts: 376
Threads: 35
Joined: Jul 2007
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.
Posts: 801
Threads: 36
Joined: Nov 2005
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.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Ed, the 17bii or 17bii+ can do it all without programming! I realize you probably want to write a program, though.
▼
Posts: 376
Threads: 35
Joined: Jul 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.
▼
Posts: 553
Threads: 57
Joined: Sep 2006
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
Posts: 1,392
Threads: 142
Joined: Jun 2007
Vincze, now that's research!!
: )
Don
Posts: 801
Threads: 36
Joined: Nov 2005
Ah, Don, I no gots no 17bii, + or - . :(
Posts: 172
Threads: 21
Joined: Sep 2005
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).
▼
Posts: 151
Threads: 18
Joined: Aug 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.
▼
Posts: 620
Threads: 14
Joined: Feb 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
▼
Posts: 376
Threads: 35
Joined: Jul 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.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 376
Threads: 35
Joined: Jul 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.
▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
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. :-)
▼
Posts: 376
Threads: 35
Joined: Jul 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.
Posts: 2
Threads: 0
Joined: Jan 1970
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.
▼
Posts: 151
Threads: 18
Joined: Aug 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.
▼
Posts: 2
Threads: 0
Joined: Jan 1970
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
▼
Posts: 151
Threads: 18
Joined: Aug 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!
|