quickest SORT method on 4 numbers ?
Blitz3D Forums/Blitz3D Programming/quickest SORT method on 4 numbers ?
| ||
| I have 4 integers each value is in the range 0 - 384 whats the quickest sort method for this type of data ? |
| ||
| 4 numbers? Just do a bubble sort. With 4 elements, the choice of sort algorithm is really sort of irrelevant. |
| ||
This code starts at the second array element, and checks to see if its value is less than the one above it. If so, it swaps its value with the one above it. It then moves onto the third array elements and checks to see if it is less than the second and so on.
Repeat
Moved = False
; Presumes ints are in an array where the first int is in array position 0, and the last in array position TOTAL_INTS-1
For Loop = 1 to TOTAL_INTS-1
If Integers(Loop) < Integers(Loop-1)
Temp = Integers(Loop)
Integers(Loop) = Integers(Loop-1)
Integers(Loop-1) = Temp
Moved = True
Endif
Next
Until Not Moved
|
| ||
| thanks |
| ||
| sswift's code will be plenty fast, but you did ask for the fastest which would be a 4 element version of QuickSort... Quicksort works by splitting the data set into halfs recursively and sorting each half. Eventually everything is sorted as the recursion pops back up the stack. so ... compare (1) and (2) and sort them (i.e. swap if necessary) compare (3) and (4) and sort them then compare (2) and (3) and sort them. everything now sorted. |
| ||
| Quicksort may not be fastest. There might be some unintuitive algorithm, specifically for four elements, which is faster. I'll have to give this some more thought. This whole thing sounds like a Computer Science homework problem. |
| ||
And this:compare (1) and (2) and sort them (i.e. swap if necessary) compare (3) and (4) and sort them then compare (2) and (3) and sort them. is not Quicksort and doesn't work. Try it on a reversed list: D C B A. |
| ||
| I think he forgot to add 'repeat if not sorted'. Isn't that a bubble sort, though? |
| ||
| If you know that you have only a very small and fixed sized set to put in order, the *quickest* mechanism is to 'hard code' a comparison tree. Of course you can generate these. I'll give the example of ordering A, B, C If A <= B If B <= C O(A,B,C) Else If A <= C O(A,C,B) Else O(C,A,B) EndIf EndIf Else If A <= C O(B,A,C) Else If B <= C O(B,C,A) Else O(C,B,A) EndIf EndIf EndIf Result is 3 numbers ordered in 2 or 3 comparisons (average is 2.67) with no loop overhead, swaps etc. Note that if the numbers can be equal (say A=1, B=2, C=2) then the order of the equal values is pretty arbitrarily determined by the order of the comparisons in the tree. It could be O(A,B,C) or O(A,C,B) which are equally valid. There are n! branches to consider. So your requirement of 4 numbers means 4! = 24 branches but the number of comparisons will again be the lowest possible and there is no other overhead. I'll leave the actual tree for N-4 to you if you are interested enough. If you have additional information such as A is 90% likely to be the lowest, B and C are equally likely to be next most likely and D is say 25% likely to be greater than both B and C then you can do better. I guess the the Huffman coding algorithm would be the way to determine the optimal comparison tree. Of course as others may well point out, this level of optimisation is almost certainly unnecessary as you're only dealing with 4 numbers. Even the least efficient way of doing it would probably be fine. But you did ask for the *quickest* way. |
| ||
| Thanks Floyd (and Big10P). I should have emphasised the recursively part :-( |
   |