QB64 Phoenix Edition
Insert Sort 4 ways demostration - Printable Version

+- QB64 Phoenix Edition (https://staging.qb64phoenix.com)
+-- Forum: QB64 Rising (https://staging.qb64phoenix.com/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://staging.qb64phoenix.com/forumdisplay.php?fid=3)
+---- Forum: Programs (https://staging.qb64phoenix.com/forumdisplay.php?fid=7)
+---- Thread: Insert Sort 4 ways demostration (/showthread.php?tid=1570)

Insert Sort 4 ways demostration - TempodiBasic - 03-23-2023

Hi
here another tedious way to order an array.
Insertion sort method....

the logical idea of Bubblesort is to compare a pair of contiguous items and to swap them shifting the big to the right and the little to the left (or vice versa) getting at the end an increasing (decreasing) array. The end comes when no more swaps.

the logical idea behind Insertion sort method is a bit different: we take for ordered the first item (or the last item) of the array. Shifting to the right (or to the left if we start at rightest item of the array) we compare it with the ordered items of the ordered subset of the array. If the new item is bigger (or littler) than the ordered item we shift it until this condition of to be bigger (to be littler) is false or we arrive at the end of the ordered subset of items. 
At each comparison we perform a swap between the two items in comparison. These operations of comparison and swapping are performed for all the items of the array.

As it is possible to start from left or from right, and making a comparison for > or < here follows a little demo to show all these 4 ways:
Code: (Select All)
_Title "Insert sorting algorithm demostration"
Rem Insert sort demonstration
Rem it creates an ordered increasing subset of elements taken from the scrambled set of items to be ordered
Rem it uses 2 indexes: 1 for ordererd subset and 1 for unordered subset

Randomize Timer
Const max = 10
Dim a(1 To max) As Integer, b(1 To max) As Integer
Print " Original array unordered";
init a()
Show a()
Print String$(80, "@");
CopyArr a(), b()

Show a()
Print "ordering array...from left decreasing "
InsertFromLeft a()
Color 4
Show a()
Color 7
CopyArr b(), a()
Show a()
Print "ordering array...from left increasing"
InsertFromLeftInc a()
Color 2
Show a()
Color 7

CopyArr b(), a()
Show a()
Print "ordering array...from right increasing"
InsertFromRight a()
Color 5
Show a()
Color 7
CopyArr b(), a()
Show a()
Print "ordering array...from right decreasing"
InsertFromRightDec a()
Color 3
Show a()
Color 7
End

Rem -----INSERTION SORT starting from leftest item of array-----------
Rem it orders a() starting from the left of array in decreasing way
Rem the array is ordered from left/higher value to right/lower value
Rem -------------------------------------------------------------------
Sub InsertFromLeft (A() As Integer)
    For b = 1 To (max - 1) Step 1
        c = b
        Do While c > 0
            If A(c + 1) > A(c) Then
                Swap A(c), A(c + 1)
            End If
            c = c - 1
        Loop
    Next
End Sub

Rem -----INSERTION SORT starting from leftest item of array-----------
Rem it orders a() starting from the left of array in increasing way
Rem the array is ordered from left/higher value to right/lower value
Rem -------------------------------------------------------------------
Sub InsertFromLeftInc (A() As Integer)
    For b = 1 To (max - 1) Step 1
        c = b
        Do While c > 0
            If A(c + 1) < A(c) Then
                Swap A(c), A(c + 1)
            End If
            c = c - 1
        Loop
    Next
End Sub

Rem -----INSERTION SORT starting from rightest item of array-----------
Rem it orders a() starting from the right of array in increasing way
Rem the array is ordered from left/higher value to right/lower value
Rem -------------------------------------------------------------------
Sub InsertFromRight (A() As Integer)
    For b = (max - 1) To 1 Step -1
        c = b
        While c < (max)
            If A(c + 1) < A(c) Then Swap A(c), A(c + 1)
            c = c + 1
        Wend
    Next
End Sub

Rem -----INSERTION SORT starting from rightest item of array-----------
Rem it orders a() starting from the right of array in increasing way
Rem the array is ordered from left/higher value to right/lower value
Rem -------------------------------------------------------------------
Sub InsertFromRightDec (A() As Integer)
    For b = (max - 1) To 1 Step -1
        c = b
        While c < (max)
            If A(c + 1) > A(c) Then Swap A(c), A(c + 1)
            c = c + 1
        Wend
    Next
End Sub

Rem -----INIT--------------------------------------------------
Rem it initializes  array a() giving it random values
Rem -----------------------------------------------------------
Sub init (a() As Integer)
    For b = 1 To max
        a(b) = Int(Rnd * max - 1) + 1
    Next b
    Print
End Sub

Rem -----SHOW--------------------------------------------------
Rem it print out the items of a()
Rem it must be aware that a() has almost 1 item (max = 1)
Rem -----------------------------------------------------------
Sub Show (a() As Integer)
    For b = 1 To max
        Print a(b); "_";
    Next b
    Print
End Sub

Rem -----COPYARR-----------------------------------------------
Rem it copies a() in b ()
Rem it must be aware that b() has equal or more items then a()
Rem -----------------------------------------------------------
Sub CopyArr (a() As Integer, b() As Integer)
    For b = 1 To max
        b(b) = a(b)
    Next b
    Print " Array copied!"
End Sub



[Image: immagine-2023-03-23-024918540.png]

Thanks for new ideas or demos or feedback.