SelectionSort – Short, simple and sloooow

' SelectionSort.  Short, simple and sloooow.  This is another O(N^2) sort that ' should never be used on long lists.  Like InsertionSort,'  it needs no extra memory (in place) and preserves the existing order of ' records with equal keys.  Unfortunately, it's slower,'  and there's no reason to use it instead of InsertionSort.  Works by looking ' thru the list for the smallest key and placing it first,'  then looking for the next largest, and so on.  If the slow linear search for ' each key is replaced by a faster "priority queue" approach,'  a reasonably fast algorithm can be created (see HeapSort).  Two versions are ' given.  pSelSortS is an indirect (pointerized) version for strings,'  which can be adapted to doubles by changing the declaration of A().  ' SelSortL is a direct version for longs, which can be adapted to integers.'  ' Speed:  Don't ask.'' Bottom line:  Included because it's a clear and simple approach,'  but too slow to be useful.' Usage:  Dim S1(L To R) As StringDim P1(L To R) As LongDim L1(L To R) As Long For I = L To R    S1(I) = GetRandomString()    P1(I) = I    L1(I) = GetRandomLong()Next IpSelSortS L, R, S1, P1SelSortL L, R, L1' CODE:Sub pSelSortS(L As Long, R As Long, A() As String, P() As Long)    Dim I As Long    Dim J As Long    Dim Min As Long    Dim TMP As Long    For I = L To R - 2    'Start with the first key.        Min = I    'Compare to each key to the right        For J = I + 1 To R        'Every time we find a lower value, keep that pointer.            If A(P(J)) < A(P(Min)) Then                Min = J            End If        Next J    'When we've scanned all keys, swap the low key's pointer to the end of the     ' sorted list.        TMP = P(I)        P(I) = P(Min)        P(Min) = TMP    Next IEnd SubSub SelSortL(L As Long, R As Long, A() As Long)    Dim I As Long    Dim J As Long    Dim Min As Long    Dim TMP As Long    For I = L To R - 2        Min = I        For J = I + 1 To R            If A(J) < A(Min) Then                Min = J            End If        Next J        TMP = A(I)        A(I) = A(Min)        A(Min) = TMP    Next IEnd Sub

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

Recent Articles: