Python Program to sort an array using Insertion Sort

Program

def insertionSort(arr, n):
    for i in range(n):
        temp = arr[i]
        j = i - 1
        while (temp < arr[j]) and (j >= 0):
            arr[j+1] = arr[j]
            j = j - 1
        arr[j + 1] = temp
    print("Sorted array:")
    for i in range(n):
        print("%d" % arr[i])
print("Enter the size of the array:")
n = int(input())
arr = []
print("Enter array elements:")
for i in range(n):
    x = int(input())
    arr.append(int(x))
insertionSort(arr, n)

This program sorts an array using the Insertion Sort algorithm, which is a simple and efficient sorting technique.

1. Function Definition (insertionSort)

   • The function takes an array arr and its size n.
   • It sorts the array using the Insertion Sort algorithm.

2. Insertion Sort Logic

   • Iterate through each element (i) in the array.
   • Store the current element in temp.
   • Compare it with the previous elements (j), shifting them if necessary to insert temp at the correct position.

3. User Input for Array

   • The user enters the array size.
   • Elements are read and stored in the list arr.

4. Sorting and Printing

   • The insertionSort() function is called to sort the array.
   • The sorted array is displayed.

Key Takeaways

• Insertion Sort works by inserting elements into their correct position one by one.
• Best-case time complexity is O(n) when the array is already sorted.
• Worst-case time complexity is O(n²) when the array is in reverse order.
• Stable sorting algorithm, meaning equal elements retain their relative order.

Output

Enter the size of the array:
6
Enter array elements:
-43
0
-8
856
12
96
Sorted array:
-43
-8
0
12
96
856