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

By submitting your information, you agree that devx.com may send you DevX offers via email, phone and text message, as well as email offers about other products and services that DevX believes may be of interest to you. DevX will process your information in accordance with the Quinstreet Privacy Policy.


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

WEBINAR:

On-Demand

Application Security Testing: An Integral Part of DevOps


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
×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.
Thanks for your registration, follow us on our social networks to keep up-to-date