DSA 10: Insertion Sort - Shift & Insert

3rd attempt which uses less variable assigning
data structures
algorithms
Author

Tony Phung

Published

January 19, 2025

1. Code

1.1 Psuedo-Code

Not the greatest psuedo-code but it’lll do for now.

  • Outer loop:
    • from 1 to last index of array (or array size)
  • For each index r of outer loop:
    • Allocate current-index arr[l] to temp-variable (temp-val): tmp
    • while l>0 and temp-value (tmp) to previous-value (l-1)
      • If temp-val < prev-value: shift prev-val right by 1, then decrement l and go back to start of -loop
      • If temp-val > prev-value:
        • if: shifted previously, assign arr[l]=tmp
        • else: next r

1.2 Python-Code

vals_to_list_fn = lambda vals: [int(val) for val in str(vals)]

def insert_sort_shift_and_insert(arr: list[int]):
    print(arr)
    for r in range(1,len(arr)):
        shifted=False
        l=r
        tmp=arr[l]
        print(f"\t{[r]}")
        while l>0 and tmp<arr[l-1]:
            arr[l]=[] #uncessary - temporarily blank-out [l] - for visaul debugging-purposes
            print(f"(idx[{l-1}]={arr[l-1]}_vs_tmp={tmp}) COMPARE: {arr} | tmp={tmp}")
            arr[l]=arr[l-1] # shift-right 1
            arr[l-1]=[] # uncessary - for visual debugging-purposes
            print(f"(idx[{l-1}]={arr[l-1]}_vs_tmp={tmp}) SHIFTD: {arr} | tmp={tmp}")
            shifted=True
            l-=1
        if shifted:
            arr[l] = tmp 
            print(f"(idx[{l})=tmp={tmp}) \t     INSERT: {arr} | tmp={tmp}")
        else:
            print(f"SKIPPED: Already sorted from 0 to {r}: {arr[0:r+1]} of {arr}")
    print(arr)
    return arr
vals = 12354
arr = vals_to_list_fn(vals)
insert_sort_shift_and_insert(arr)
[1, 2, 3, 5, 4]
    [1]
SKIPPED: Already sorted from 0 to 1: [1, 2] of [1, 2, 3, 5, 4]
    [2]
SKIPPED: Already sorted from 0 to 2: [1, 2, 3] of [1, 2, 3, 5, 4]
    [3]
SKIPPED: Already sorted from 0 to 3: [1, 2, 3, 5] of [1, 2, 3, 5, 4]
    [4]
(idx[3]=5_vs_tmp=4) COMPARE: [1, 2, 3, 5, []] | tmp=4
(idx[3]=[]_vs_tmp=4) SHIFTD: [1, 2, 3, [], 5] | tmp=4
(idx[3)=tmp=4)       INSERT: [1, 2, 3, 4, 5] | tmp=4
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

2. Testing

Test Scenarios from previous post [DSA 9: Insertion Sort - With Test Scenarios]:

  1. Sorted & Unsorted Parts
  2. Mostly Sorted
  3. Unsorted (Descending)
  4. Duplicates
  5. Already Sorted

2.1 Sorted & Unsorted Parts: shift & and insert

arr = vals_to_list_fn(42713)
insert_sort_shift_and_insert(arr)
[4, 2, 7, 1, 3]
    [1]
(idx[0]=4_vs_tmp=2) COMPARE: [4, [], 7, 1, 3] | tmp=2
(idx[0]=[]_vs_tmp=2) SHIFTD: [[], 4, 7, 1, 3] | tmp=2
(idx[0)=tmp=2)       INSERT: [2, 4, 7, 1, 3] | tmp=2
    [2]
SKIPPED: Already sorted from 0 to 2: [2, 4, 7] of [2, 4, 7, 1, 3]
    [3]
(idx[2]=7_vs_tmp=1) COMPARE: [2, 4, 7, [], 3] | tmp=1
(idx[2]=[]_vs_tmp=1) SHIFTD: [2, 4, [], 7, 3] | tmp=1
(idx[1]=4_vs_tmp=1) COMPARE: [2, 4, [], 7, 3] | tmp=1
(idx[1]=[]_vs_tmp=1) SHIFTD: [2, [], 4, 7, 3] | tmp=1
(idx[0]=2_vs_tmp=1) COMPARE: [2, [], 4, 7, 3] | tmp=1
(idx[0]=[]_vs_tmp=1) SHIFTD: [[], 2, 4, 7, 3] | tmp=1
(idx[0)=tmp=1)       INSERT: [1, 2, 4, 7, 3] | tmp=1
    [4]
(idx[3]=7_vs_tmp=3) COMPARE: [1, 2, 4, 7, []] | tmp=3
(idx[3]=[]_vs_tmp=3) SHIFTD: [1, 2, 4, [], 7] | tmp=3
(idx[2]=4_vs_tmp=3) COMPARE: [1, 2, 4, [], 7] | tmp=3
(idx[2]=[]_vs_tmp=3) SHIFTD: [1, 2, [], 4, 7] | tmp=3
(idx[2)=tmp=3)       INSERT: [1, 2, 3, 4, 7] | tmp=3
[1, 2, 3, 4, 7]
[1, 2, 3, 4, 7]

2.2 Mostly Sorted: for-loop

arr = vals_to_list_fn(12354)
insert_sort_shift_and_insert(arr)
[1, 2, 3, 5, 4]
    [1]
SKIPPED: Already sorted from 0 to 1: [1, 2] of [1, 2, 3, 5, 4]
    [2]
SKIPPED: Already sorted from 0 to 2: [1, 2, 3] of [1, 2, 3, 5, 4]
    [3]
SKIPPED: Already sorted from 0 to 3: [1, 2, 3, 5] of [1, 2, 3, 5, 4]
    [4]
(idx[3]=5_vs_tmp=4) COMPARE: [1, 2, 3, 5, []] | tmp=4
(idx[3]=[]_vs_tmp=4) SHIFTD: [1, 2, 3, [], 5] | tmp=4
(idx[3)=tmp=4)       INSERT: [1, 2, 3, 4, 5] | tmp=4
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

2.3 Unsorted (Descending): for-loop

arr = vals_to_list_fn(54321)
insert_sort_shift_and_insert(arr)
[5, 4, 3, 2, 1]
    [1]
(idx[0]=5_vs_tmp=4) COMPARE: [5, [], 3, 2, 1] | tmp=4
(idx[0]=[]_vs_tmp=4) SHIFTD: [[], 5, 3, 2, 1] | tmp=4
(idx[0)=tmp=4)       INSERT: [4, 5, 3, 2, 1] | tmp=4
    [2]
(idx[1]=5_vs_tmp=3) COMPARE: [4, 5, [], 2, 1] | tmp=3
(idx[1]=[]_vs_tmp=3) SHIFTD: [4, [], 5, 2, 1] | tmp=3
(idx[0]=4_vs_tmp=3) COMPARE: [4, [], 5, 2, 1] | tmp=3
(idx[0]=[]_vs_tmp=3) SHIFTD: [[], 4, 5, 2, 1] | tmp=3
(idx[0)=tmp=3)       INSERT: [3, 4, 5, 2, 1] | tmp=3
    [3]
(idx[2]=5_vs_tmp=2) COMPARE: [3, 4, 5, [], 1] | tmp=2
(idx[2]=[]_vs_tmp=2) SHIFTD: [3, 4, [], 5, 1] | tmp=2
(idx[1]=4_vs_tmp=2) COMPARE: [3, 4, [], 5, 1] | tmp=2
(idx[1]=[]_vs_tmp=2) SHIFTD: [3, [], 4, 5, 1] | tmp=2
(idx[0]=3_vs_tmp=2) COMPARE: [3, [], 4, 5, 1] | tmp=2
(idx[0]=[]_vs_tmp=2) SHIFTD: [[], 3, 4, 5, 1] | tmp=2
(idx[0)=tmp=2)       INSERT: [2, 3, 4, 5, 1] | tmp=2
    [4]
(idx[3]=5_vs_tmp=1) COMPARE: [2, 3, 4, 5, []] | tmp=1
(idx[3]=[]_vs_tmp=1) SHIFTD: [2, 3, 4, [], 5] | tmp=1
(idx[2]=4_vs_tmp=1) COMPARE: [2, 3, 4, [], 5] | tmp=1
(idx[2]=[]_vs_tmp=1) SHIFTD: [2, 3, [], 4, 5] | tmp=1
(idx[1]=3_vs_tmp=1) COMPARE: [2, 3, [], 4, 5] | tmp=1
(idx[1]=[]_vs_tmp=1) SHIFTD: [2, [], 3, 4, 5] | tmp=1
(idx[0]=2_vs_tmp=1) COMPARE: [2, [], 3, 4, 5] | tmp=1
(idx[0]=[]_vs_tmp=1) SHIFTD: [[], 2, 3, 4, 5] | tmp=1
(idx[0)=tmp=1)       INSERT: [1, 2, 3, 4, 5] | tmp=1
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

2.4 Duplicates: for-loop

arr = vals_to_list_fn(11111)
insert_sort_shift_and_insert(arr)
[1, 1, 1, 1, 1]
    [1]
SKIPPED: Already sorted from 0 to 1: [1, 1] of [1, 1, 1, 1, 1]
    [2]
SKIPPED: Already sorted from 0 to 2: [1, 1, 1] of [1, 1, 1, 1, 1]
    [3]
SKIPPED: Already sorted from 0 to 3: [1, 1, 1, 1] of [1, 1, 1, 1, 1]
    [4]
SKIPPED: Already sorted from 0 to 4: [1, 1, 1, 1, 1] of [1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]

2.5 Already Sorted: for-loop

arr = vals_to_list_fn(12345)
insert_sort_shift_and_insert(arr)
[1, 2, 3, 4, 5]
    [1]
SKIPPED: Already sorted from 0 to 1: [1, 2] of [1, 2, 3, 4, 5]
    [2]
SKIPPED: Already sorted from 0 to 2: [1, 2, 3] of [1, 2, 3, 4, 5]
    [3]
SKIPPED: Already sorted from 0 to 3: [1, 2, 3, 4] of [1, 2, 3, 4, 5]
    [4]
SKIPPED: Already sorted from 0 to 4: [1, 2, 3, 4, 5] of [1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]