Amazing-Python-Scripts

1
"""
2
Insertion Sort
3
    Insertion sort is an simple sorting algorithm that builds the final sorted array one item at a time
4
Benefits of Insertion Sort
5
    Simple Implementation
6
    Efficient for quite small data sets
7
    Adaptive: efficient for data sets that are already substantially sorted
8
    Stable: does not change relative order of elements with equal keys
9
    In-Place: only requires a constant amount O(1) of additional extra space
10
    Online: can sort a list as it receives it
11
Traditional Approach
12
    Let unsorted array be Uarr and Sorted array be Sarr
13
    Create a sorted array namely 'Sarr'
14
    Put i(th) element from Uarr to Sarr
15
    put (i+1)th element in Sarr such that the array is still sorted
16
    put(i+2)th element such that array is still sorted by comparing and shuffling the elements, if required
17
Effective Approach
18
    Take a pointer at index[1] {considering index[0] is sorted}
19
    Let everything at left of the pointer be sorted
20
    compare the current pointed element with the elements of sorted side (i.e. left side)
21
        If CurrentElement < elements at sorted array: insert current element at appropriate place of sorted array
22
        If CurrentElement > elements at sorted array: repeat above processes until array is sorted
23

24
    For instance,
25
        Uarr: 2 5 8 1 3 4
26
        2 5 8 1 3 4     2,5
27
        2 5 8 1 3 4     5,8
28
        2 5 8 1 3 4     8,1
29
        1 2 5 8 3 4     8,3
30
        1 2 3 5 8 4     8,4
31
        1 2 3 4 5 8     Sarr
32

33
    Worst-Case Performance          O(n^2)-{Comparisons} and O(n^2)-{Swaps}
34
    Best-Case Performance           O(n)-{Comparisons} and O(1)-{Swaps}
35
    Average Performance             O(n^2)-{Comparisons} and O(n^2)-{Swaps}
36
    Worst-caseSpace Performance     O(n)-{Comparisons} and O(1)-{Auxiliary}
37

38
"""
39

40

41
def InsertionSort(elements):
42
    # starting with the 2nd element {index[1]}
43
    for i in range(1, len(elements)):
44
        pointer = elements[i]  # current element named as pointer
45
        # left element of pointer {index[current] - 1 = elements[left]}
46
        j = i - 1
47
        # compare current element (pointer) to sorted array (j)
48
        # iterate between j to index[0] and continue until elements of j > pointer
49
        while j >= 0 and pointer < elements[j]:
50
            # swapped left element to right element
51
            elements[j + 1] = elements[j]
52
            j = j - 1  # same as j--
53
        # when loop is terminated, pointer will be assigned to next element
54
        # increase pointer value and repeat until array is sorted
55
        elements[j + 1] = pointer
56

57

58
if __name__ == '__main__':
59
    elements = [2, 5, 8, 1, 3, 4]
60
    InsertionSort(elements)
61
    print(elements)
62
    # test cases
63
    tests = [
64
        [11, 9, 29, 7, 2, 15, 28],  # worst-case scenario
65
        [3, 7, 9, 11],  # sorted list
66
        [25, 22, 21, 10],  # DESC-sorted list
67
        [],  # empty list
68
        [6]  # single element list
69
    ]
70

71
    for elements in tests:
72
        InsertionSort(elements)
73
        print(f"Sorted array: {elements}")
74