Insertion Sort

In [1]:
%pprint
Pretty printing has been turned OFF
In [16]:
from random import sample
nums = sample(range(1000), k=20)
nums
Out[16]:
[19, 425, 768, 179, 445, 712, 738, 94, 941, 790, 189, 715, 442, 51, 985, 638, 16, 191, 751, 1]
In [21]:
num_comparisons = 0
num_shifts = 0

def insertion_sort(alist):
    global num_comparisons, num_shifts
    
    for index in range(1, len(alist)):
        current_value = alist[index]
        position = index
        
        while position > 0 and alist[position-1] > current_value:
            num_shifts += 1
            num_comparisons += 1
            #print(alist)
            alist[position] = alist[position-1]
            position -= 1 
            
        alist[position] = current_value
In [22]:
nums_copy = nums.copy()
insertion_sort(nums_copy)
In [10]:
nums_copy
Out[10]:
[29, 73, 95, 127, 131, 149, 178, 189, 225, 263, 265, 307, 607, 644, 678, 742, 824, 928, 945, 989]
In [23]:
num_comparisons, num_shifts
Out[23]:
(99, 99)