DSA 9: Insertion Sort - With Test Scenarios

Equivalent Implementations Using for & while-loops
data structures
algorithms
Author

Tony Phung

Published

January 18, 2025

1. Introduction

  • I’m currently mostly comfortable using for-loops. So I implemented that first then converted it into a while-loop.
    • I used >= rather than > purely for debugging and printing purposes to capture already-sorted SKIP iterations.
    • The equivalence is not necessary because the code will reach the end of that particular iteration and go to next decrement (l--) (if any), which is the same as skipping the UPDATE part.
  • My learnings and opinions are at the end.

1.1 CODE-1: for-loop

def insertion_sort_for(arr: list[int]):
    for r in range(1,len(arr)):
        print(f"\tidx: {[r]}")
        for l in range(r,0,-1):
            if arr[l]>=arr[l-1]:
                print(f"SKIP:\t\t{(l-1,l)},{arr} ")
                break
            arr[l-1],arr[l]=arr[l],arr[l-1]
            print(f"UPDATED:\t{(l-1,l)},{arr} ")
    # print(arr)
    return arr

1.2 CODE-2: while-loop

def insertion_sort_while(arr: list[int]):
    for r in range(1,len(arr)):
        print(f"\tidx: {[r]}")
        l=r
        # for l in range(r,0,-1):
        while l>0 and arr[l]<arr[l-1]:
            arr[l-1],arr[l]=arr[l],arr[l-1]
            print(f"UPDATED:\t{(l-1,l)},{arr} ")
            l-=1
        if l>0 and arr[l]>=arr[l-1]:
            print(f"SKIP:\t\t{(l-1,l)},{arr} ")
    # print(arr)
    return arr

1.3 Helper Function

Because I am too lazy to make the lists manually each time.

def vals_to_list(vals:int): 
    return [int(val) for val in str(vals)]

2. Five Test Scenarios

I’ll run both versions for 5 test-scenarios:

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

2.1 TEST-1: Sorted & Unsorted Parts - for-loop

arr = vals_to_list(42713)
insertion_sort_for(arr)
    idx: [1]
UPDATED:    (0, 1),[2, 4, 7, 1, 3] 
    idx: [2]
SKIP:       (1, 2),[2, 4, 7, 1, 3] 
    idx: [3]
UPDATED:    (2, 3),[2, 4, 1, 7, 3] 
UPDATED:    (1, 2),[2, 1, 4, 7, 3] 
UPDATED:    (0, 1),[1, 2, 4, 7, 3] 
    idx: [4]
UPDATED:    (3, 4),[1, 2, 4, 3, 7] 
UPDATED:    (2, 3),[1, 2, 3, 4, 7] 
SKIP:       (1, 2),[1, 2, 3, 4, 7] 
[1, 2, 3, 4, 7]

2.1 TEST-1: Sorted & Unsorted Parts - while-loop

arr = vals_to_list(42713)
insertion_sort_while(arr)
    idx: [1]
UPDATED:    (0, 1),[2, 4, 7, 1, 3] 
    idx: [2]
SKIP:       (1, 2),[2, 4, 7, 1, 3] 
    idx: [3]
UPDATED:    (2, 3),[2, 4, 1, 7, 3] 
UPDATED:    (1, 2),[2, 1, 4, 7, 3] 
UPDATED:    (0, 1),[1, 2, 4, 7, 3] 
    idx: [4]
UPDATED:    (3, 4),[1, 2, 4, 3, 7] 
UPDATED:    (2, 3),[1, 2, 3, 4, 7] 
SKIP:       (1, 2),[1, 2, 3, 4, 7] 
[1, 2, 3, 4, 7]

2.2 TEST-2: Mostly Sorted - for-loop

arr = vals_to_list(12354)
insertion_sort_for(arr)
    idx: [1]
SKIP:       (0, 1),[1, 2, 3, 5, 4] 
    idx: [2]
SKIP:       (1, 2),[1, 2, 3, 5, 4] 
    idx: [3]
SKIP:       (2, 3),[1, 2, 3, 5, 4] 
    idx: [4]
UPDATED:    (3, 4),[1, 2, 3, 4, 5] 
SKIP:       (2, 3),[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5]

2.2 TEST-2: Mostly Sorted - while-loop

arr = vals_to_list(12354)
insertion_sort_while(arr)
    idx: [1]
SKIP:       (0, 1),[1, 2, 3, 5, 4] 
    idx: [2]
SKIP:       (1, 2),[1, 2, 3, 5, 4] 
    idx: [3]
SKIP:       (2, 3),[1, 2, 3, 5, 4] 
    idx: [4]
UPDATED:    (3, 4),[1, 2, 3, 4, 5] 
SKIP:       (2, 3),[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5]

2.3 TEST-3: Unsorted (Descending) - for-loop

arr = vals_to_list(54321)
insertion_sort_for(arr)
    idx: [1]
UPDATED:    (0, 1),[4, 5, 3, 2, 1] 
    idx: [2]
UPDATED:    (1, 2),[4, 3, 5, 2, 1] 
UPDATED:    (0, 1),[3, 4, 5, 2, 1] 
    idx: [3]
UPDATED:    (2, 3),[3, 4, 2, 5, 1] 
UPDATED:    (1, 2),[3, 2, 4, 5, 1] 
UPDATED:    (0, 1),[2, 3, 4, 5, 1] 
    idx: [4]
UPDATED:    (3, 4),[2, 3, 4, 1, 5] 
UPDATED:    (2, 3),[2, 3, 1, 4, 5] 
UPDATED:    (1, 2),[2, 1, 3, 4, 5] 
UPDATED:    (0, 1),[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5]

2.3 TEST-3: Unsorted (Descending) - while-loop

arr = vals_to_list(54321)
insertion_sort_while(arr)
    idx: [1]
UPDATED:    (0, 1),[4, 5, 3, 2, 1] 
    idx: [2]
UPDATED:    (1, 2),[4, 3, 5, 2, 1] 
UPDATED:    (0, 1),[3, 4, 5, 2, 1] 
    idx: [3]
UPDATED:    (2, 3),[3, 4, 2, 5, 1] 
UPDATED:    (1, 2),[3, 2, 4, 5, 1] 
UPDATED:    (0, 1),[2, 3, 4, 5, 1] 
    idx: [4]
UPDATED:    (3, 4),[2, 3, 4, 1, 5] 
UPDATED:    (2, 3),[2, 3, 1, 4, 5] 
UPDATED:    (1, 2),[2, 1, 3, 4, 5] 
UPDATED:    (0, 1),[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5]

2.4 TEST-4: Duplicates - for-loop

arr = vals_to_list(88888)
insertion_sort_for(arr)
    idx: [1]
SKIP:       (0, 1),[8, 8, 8, 8, 8] 
    idx: [2]
SKIP:       (1, 2),[8, 8, 8, 8, 8] 
    idx: [3]
SKIP:       (2, 3),[8, 8, 8, 8, 8] 
    idx: [4]
SKIP:       (3, 4),[8, 8, 8, 8, 8] 
[8, 8, 8, 8, 8]

2.4 TEST-4: Duplicates - while-loop

arr = vals_to_list(88888)
insertion_sort_while(arr)
    idx: [1]
SKIP:       (0, 1),[8, 8, 8, 8, 8] 
    idx: [2]
SKIP:       (1, 2),[8, 8, 8, 8, 8] 
    idx: [3]
SKIP:       (2, 3),[8, 8, 8, 8, 8] 
    idx: [4]
SKIP:       (3, 4),[8, 8, 8, 8, 8] 
[8, 8, 8, 8, 8]

2.5 TEST-5: Already Sorted - for-loop

arr = vals_to_list(12345)
insertion_sort_for(arr)
    idx: [1]
SKIP:       (0, 1),[1, 2, 3, 4, 5] 
    idx: [2]
SKIP:       (1, 2),[1, 2, 3, 4, 5] 
    idx: [3]
SKIP:       (2, 3),[1, 2, 3, 4, 5] 
    idx: [4]
SKIP:       (3, 4),[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5]

2.5 TEST-5: Already Sorted - while-loop

arr = vals_to_list(12345)
insertion_sort_while(arr)
    idx: [1]
SKIP:       (0, 1),[1, 2, 3, 4, 5] 
    idx: [2]
SKIP:       (1, 2),[1, 2, 3, 4, 5] 
    idx: [3]
SKIP:       (2, 3),[1, 2, 3, 4, 5] 
    idx: [4]
SKIP:       (3, 4),[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5]

3. Ending Comments

Results are the same which is a good sign.

This algorithm took me a while to get my head around:

  • Easier: I have rarely used while-loops in my career, and thus lacking in confidence using them, but the while implementation seems to be:
    • easier to read
    • easier to debug
    • easier to write (perhaps, I’ll need to practice a bit more)
  • Looping both ways: Conceptually new to me is:
    • An outer loop or r to count forward and an
    • Inner-loop or l and to backward .
    • I’ve always counted forwards when using nested-loops.
  • Other Learnings: This algorithm has helped me to:
    • Better understand and
    • Implement the conversion between for to while loops.