dcsimg
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

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

Building the Right Environment to Support AI, Machine Learning and Deep Learning


InsertionSort - A simple routine with minimal overhead

' InsertionSort.  A simple routine with minimal overhead.  Should never be used 
' to sort long lists because of its O(N^2) behavior,
'  but is the method of choice for sorting short (5-50 key) lists or long lists 
' that have been mostly sorted by a faster algorithm.  InsertionSort is faster 
' than either Bubble or SelectionSort and should be used anywhere you would 
' consider using those.  Sorts in place (no extra memory needed) and is stable 
' (preserves the original order of records with equal keys).  Works by creating 
' a sorted list at the beginning of the array of keys.  As each unsorted key to 
' the right is examined, it is compared back thru the sorted list until the 
' right position to insert it is found.  Two versions are given.  pInsertS is 
' an indirect (pointerized) version for strings,
'  which can be adapted to doubles by changing the declaration of A().  InsertL 
' is a direct version for longs, which can be adapted to integers.
' 
' Speed:  Abysmally slow for anything but short lists.
'
' Bottom line:  should be used only to finish up for faster sorts with higher 
' overhead; for that purpose, this is the sort to choose.

' 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

pInsertS L, R, S1, P1
InsertL L, R, L1

' CODE:

Sub pInsertS(L As Long, R As Long, A() As String, P() As Long)
    Dim LP As Long
    Dim RP As Long
    Dim TMP As Long
    Dim T As String

    'RP points to the first unsorted key.   
    For RP = L + 1 To R
     'Get the new value.
       TMP = P(RP)
        T = A(TMP)
    'Compare it back thru the sorted part as long as it's bigger.
        For LP = RP To L + 1 Step -1
            If T < A(P(LP - 1)) Then P(LP) = P(LP - 1) Else Exit For
        Next LP
    'It's bigger than all keys to the left, so insert it here.
        P(LP) = TMP
    Next RP
End Sub

Sub InsertL(L As Long, R As Long, A() As Long)
    Dim LP As Long
    Dim RP As Long
    Dim TMP As Long
    
    For RP = L + 1 To R
        TMP = A(RP)
        For LP = RP To L + 1 Step -1
            If TMP < A(LP - 1) Then A(LP) = A(LP - 1) Else Exit For
        Next LP
        A(LP) = TMP
    Next RP
End Sub

David B. Ring
 
Comment and Contribute

 

 

 

 

 


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

 

 

Sitemap
Thanks for your registration, follow us on our social networks to keep up-to-date