ShellSort – A compact routine that sorts data in place

ShellSort – A compact routine that sorts data in place

' ShellSort.  A compact routine that sorts data in place (no extra memory ' needed) and runs in O(N (log N)^2) time.  Not stable (does not preserve ' original order of records with equal keys).' Like InsertionSort, works by taking a key from the right side of the list and ' comparing it with keys to the left until the correct position is found to ' insert it.  Differs from InsertionSort (and resembles CombSort) by moving ' leftward by interval GAP instead of one key at a time.  GAP is initially ' large (to move keys close to their final position rapidly) and is ' subsequently reduced until it equals 1 and the list is sorted.  Two versions ' are given.  pShellSortS is an indirect (pointerized) version for strings,'  which can be adapted to doubles by changing the declaration of A().  ' ShellSortL is a direct version for longs, which can be adapted to integers.'' Speed:  pShellSortS sorts 500,000 random strings in 115 sec; sorts 100186 ' library call numbers in 18 sec; sorts 25479 dictionary words in 3.2 sec ' (random order), 0.83 sec (presorted) or 1.4 sec (reverse sorted).  ShellSortL ' sorts 500,000 random longs in 67 seconds.  Timed in Excel 2001 on an 800 mhz ' PowerBook.'' Bottom line:  with O(N (log N)^2) behavior, there are better choices.' 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 IpShellSortS L, R, S1, P1ShellSortL L, R, L1' CODE:Sub pShellSortS(L As Long, R As Long, A() As String, P() As Long)    Dim GAP As Long    Dim I As Long    Dim J As Long    Dim TMP As Long    GAP = 1    'Find largest possible GAP.    While GAP * 3 < R - L        GAP = GAP * 3 + 1    Wend    While GAP > 0        For I = GAP + 1 To R        'Start with a right hand pointer.            TMP = P(I)            J = I        'Compare it leftward at intervals of GAP.            Do While J > GAP         'If the left pointer's value is higher, shift it right & go left          ' another GAP.                If A(P(J - GAP)) > A(TMP) Then                    P(J) = P(J - GAP)                    J = J - GAP                Else                    Exit Do                End If            Loop        'The right pointer's value was equal or higher, so insert it here.            P(J) = TMP        Next I    'Shrink the GAP until it reaches 1.        GAP = GAP / 3    WendEnd SubSub ShellSortL(L As Long, R As Long, A() As Long)    Dim GAP As Long    Dim I As Long    Dim J As Long    Dim TMP As Long    GAP = 1    While GAP * 3 < R - L        GAP = GAP * 3 + 1    Wend    While GAP > 0        For I = GAP + 1 To R            TMP = A(I)            J = I            Do While J > GAP                If A(J - GAP) > TMP Then                    A(J) = A(J - GAP)                    J = J - GAP                Else                    Exit Do                End If            Loop            A(J) = TMP        Next I        GAP = GAP / 3    WendEnd Sub

Share the Post:
Heading photo, Metadata.

What is Metadata?

What is metadata? Well, It’s an odd concept to wrap your head around. Metadata is essentially the secondary layer of data that tracks details about the “regular” data. The regular

XDR solutions

The Benefits of Using XDR Solutions

Cybercriminals constantly adapt their strategies, developing newer, more powerful, and intelligent ways to attack your network. Since security professionals must innovate as well, more conventional endpoint detection solutions have evolved

AI is revolutionizing fraud detection

How AI is Revolutionizing Fraud Detection

Artificial intelligence – commonly known as AI – means a form of technology with multiple uses. As a result, it has become extremely valuable to a number of businesses across

AI innovation

Companies Leading AI Innovation in 2023

Artificial intelligence (AI) has been transforming industries and revolutionizing business operations. AI’s potential to enhance efficiency and productivity has become crucial to many businesses. As we move into 2023, several

data fivetran pricing

Fivetran Pricing Explained

One of the biggest trends of the 21st century is the massive surge in analytics. Analytics is the process of utilizing data to drive future decision-making. With so much of

kubernetes logging

Kubernetes Logging: What You Need to Know

Kubernetes from Google is one of the most popular open-source and free container management solutions made to make managing and deploying applications easier. It has a solid architecture that makes