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 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 IpInsertS L, R, S1, P1InsertL 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 RPEnd SubSub 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 RPEnd Sub

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


The Latest

your company's audio

4 Areas of Your Company Where Your Audio Really Matters

Your company probably relies on audio more than you realize. Whether you’re creating a spoken text message to a colleague or giving a speech, you want your audio to shine. Otherwise, you could cause avoidable friction points and potentially hurt your brand reputation. For example, let’s say you create a

chrome os developer mode

How to Turn on Chrome OS Developer Mode

Google’s Chrome OS is a popular operating system that is widely used on Chromebooks and other devices. While it is designed to be simple and user-friendly, there are times when users may want to access additional features and functionality. One way to do this is by turning on Chrome OS

homes in the real estate industry

Exploring the Latest Tech Trends Impacting the Real Estate Industry

The real estate industry is changing thanks to the newest technological advancements. These new developments — from blockchain and AI to virtual reality and 3D printing — are poised to change how we buy and sell homes. Real estate brokers, buyers, sellers, wholesale real estate professionals, fix and flippers, and beyond may