 DESCRIPTION:

Sorting refers to the operation or technique of arranging and rearranging sets of data
in some specific order.

Insertion sort is the sorting mechanism where the sorted array is built, having one item at a time. In this sorting mechanism, the element is inserted at an appropriate place similar to card insertion. Here, the list is divided into two parts, sorted and unsorted sub-lists. In each pass, the first element of the unsorted sub-list is picked up and moved into the sorted sub-list by inserting it in a suitable position. This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort.

ALGORITHM:

The insertion sort algorithm is performed using the following steps...

Step 1Assume that first element in the list is in sorted portion and all the remaining elements are in unsorted portion.
Step 2: Take the first element from the unsorted portion and insert that element into the sorted portion in the order specified.
Step 3: Repeat the above process until all the elements from the unsorted portion are moved into the sorted portion.

EXAMPLE:

Let us now understand working with the following example:

Consider the following array: 78, 23,45, 8, 32, 36 First Iteration: Compare 78 with 23. The comparison shows 23< 78.
Hence swap 23 and 78.

The array now looks like:

23, 78, 45, 8, 32, 36

Second Iteration: Begin with the second element (78), but it was already
swapped on for the correct position, so we move ahead to the next element.

Now hold on to the third element (45) and
compare with the ones preceding it.

Since 45< 78, swap 45 and 78.

Also, 45>23, no swapping takes place and 45 remains in its position.

The array after the Second iteration looks like:

23, 45, 78, 8, 32, 36

Third Iteration: Start the following Iteration with the fourth element (8) and compare it with its preceding elements.

Since 8< 78, we swap the two.

Array now becomes: 23, 45, 8, 78, 32, 36

But there still exist elements we haven't yet compared with 8. Now the comparison
takes place between 45 and 8. Since 8 < 45, we swap the two.

The array becomes 23, 8, 45, 78, 32, 36

The last comparison for the iteration is now between 23 and 8.

Since 8 < 23, we swap the two.

The array now becomes 8, 23, 45, 78, 32, 36

Fourth Iteration: Start the following Iteration with the fifth element (32) and compare it with its preceding elements.

Since 32< 78, we swap the two.

Array now becomes: 8, 23, 45, 32, 78, 36

But there still exist elements we haven%u2019t yet compared with 32. Now the comparison takes place between 45 and 32.

Since 32 < 45, we swap the two.

The array becomes 8, 23, 32, 45, 78, 36

The comparison for the iteration is now between 23 and 32. Since 23 < 32, no swapping takes place and 32 remains in its position.

The array now becomes 8, 23, 32, 45, 78, 36

Fifth Iteration: The last iteration calls for the comparison of the last element (36), with all the preceding elements, and makes the swapping between elements.

Since, 36< 78. Swap 36 and 78.

Array now becomes: 8, 23, 32, 45, 36, 78

Compare 36 with 45.

Since, 36< 45. Swap 45 and 36.

Array now becomes: 8, 23, 32, 36, 45, 78.

Compare 36 with 32.

Since 32<36. no swapping takes place and 36 remains at its position.

Array now becomes: 8, 23, 32, 36, 45, 78.

This is the final array after all the
corresponding iterations and swapping of elements.

PROGRAM:

# importing random module for generating random values
import random

class Sort:
def __init__(self):
self.list_of_elements = []
print(
"Number of elements:")
self.N = int(input())
for i in range(self.N):
# Generating random values between 50 and 100
element = random.randint(
50, 100)
self.list_of_elements.append(element)
print(
"Given array is :", self.list_of_elements)

def __call__(self):
# Count : For counting the number of iterations
Count =
1
print(
"Iteration " + str(Count) + ":", self.list_of_elements)
# Traverse through 1 to len(list_of_elements)
for i in range(1, len(self.list_of_elements)):
key = self.list_of_elements[i]
j = i -
1
""" Move elements of a list_of_elements[0..i-1], that are greater than key, to one position ahead
of their current position"""

while j >= 0 and self.list_of_elements[j] > key:
self.list_of_elements[j +
1] = self.list_of_elements[j]
j = j -
1
self.list_of_elements[j +
1] = key
Count +=
1
print(
"Iteration " + str(Count) + ":", self.list_of_elements)

obj = Sort()
obj()

OUTPUT:

Number of elements: 7
Given array
is: [59, 81, 54, 90, 57, 97, 95]
Iteration
1: [59, 81, 54, 90, 57, 97, 95]
Iteration
2: [59, 81, 54, 90, 57, 97, 95]
Iteration
3: [54, 59, 81, 90, 57, 97, 95]
Iteration
4: [54, 59, 81, 90, 57, 97, 95]
Iteration
5: [54, 57, 59, 81, 90, 97, 95]
Iteration
6: [54, 57, 59, 81, 90, 97, 95]
Iteration
7: [54, 57, 59, 81, 90, 95, 97]

Time Complexity Analysis:
Worst Case Time Complexity [Big-O]: O(n2) comparisons and swaps

Best Case Time Complexity [Big-omega]: O(n) comparisons, O(1) swaps

Average Time Complexity [Big-theta]: O(n2) comparisons and swaps

Space Complexity Analysis:

Worst Case space Complexity [Big-O]: O(n) total, O(1) auxiliary

Uses:  Insertion sort is used when the number of elements is small. It can also be useful when the input array is almost sorted, only a few elements are misplaced in complete big array. 