Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


Tip of the Day
Language: VB5, VB6
Expertise: Advanced
Jan 13, 2003

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 String
Dim P1(L To R) As Long
Dim L1(L To R) As Long
 
For I = L To R
    S1(I) = GetRandomString()
    P1(I) = I
    L1(I) = GetRandomLong()
Next I

pSelSortS L, R, S1, P1
SelSortL 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 I
End Sub

Sub 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 I
End Sub

David B. Ring
 
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap