radix vs quiksort

[Moneo]

Moneo, heap sort is not faster than quick sort but its a 'stable' performer. I have the code in C if you want it.

Thanks, BBQ, but I really have no need for C routines right now.
*****

[TheBigBasicQ]

moneo, its not a big deal to port them to QB. If you want I'll do it when I have the time.

[Moneo]

BBQ, Ok fine, when you have the time. Then I'll run it in the SORTDEMO against Microsoft's version of the Heap sort.
*****

[Moneo]

SBM,
The original SORTDEMO.BAS was posted on another thread. It did not contain the Radix sort. We're going to have to include it in a modified version.
*****

[Moneo]

Rather than start a new thread, I chose to continue this old thread of April 2005 because it has a lot of related information.

In a previous post I mentioned that when I have to do a memory sort I use a simple Shell sort. Actually it's a Selection sort which I acquired at Citibank 20 years ago.

Anyway, to get to the point, here it is:

Code:

defint a-z
rem A() is the array, n=number of elements in array

for i=1 to n
    m=i
    FOR j=i+1 to n
        if A(j)<A(m) THEN m=j
    NEXT j
    SWAP A(i),A(m)
NEXT I

A few days ago, I put this 7 line sorting algorithm into the famous SORTDEMO.BAS program. It runs faster than all the other algorithms, including a 15% increase in speed versus the fastest Quick Sort.

I thought maybe the SORTDEMO was not a good test, so I wrote a program having 4000 elements in an array of random strings. I ran this program for the best Quicksort and the above SelectionSort, and again the SelectionSort was faster.

Just wanted to share this with you guys. I still can't believe it.
*****

[yetifoot]

* yetifoot runs away with the code for some hardcore testing.

i never saw one that short before.

[yetifoot]

could you take a look at this? i seem to be finding it very slow, im sure i implemented it ok..

Code:

Sub MoneoSort(ArrayToSort(), StartEl, NumEls)
  Dim As Integer i, j, m
    For i = StartEl To NumEls + StartEl - 1
      m = i
      For j = i + 1 To NumEls + StartEl - 1
        If ArrayToSort(j) < ArrayToSort(m) Then m = j
      Next j
      Swap ArrayToSort(i), ArrayToSort(m)
    Next i
End Sub

In a test of 5000 strings i got 3 secs with this sort vs a few milliseconds with quicksort.

in a test of 500,000 i got 3.2 in quicksort and am still waiting for the result with this sort (its been a few minutes)

[Moneo]

.....

Code:

Sub MoneoSort(ArrayToSort(), StartEl, NumEls)
  Dim As Integer i, j, m
    For i = StartEl To NumEls + StartEl - 1
      m = i
      For j = i + 1 To NumEls + StartEl - 1
        If ArrayToSort(j) < ArrayToSort(m) Then m = j
      Next j
      Swap ArrayToSort(i), ArrayToSort(m)
    Next i
End Sub

You changed both the FOR loops by introducing "StartEl". Maybe that is having some effect. Try it exactly the way it was written in the original. Also, NumEls should be defined as integer.
*****

[yetifoot]

its still not working for me. i'm using 5000 random strings of 4-8 chars long, using characters 65-90. it seems to sort them ok, but very slowly.

[Anonymous]

are we talking qb or fb here?