Sorting Algorithms

Insertion Sort

Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Characteristics of Insertion Sort

  • This algorithm is one of the simplest algorithm with simple implementation

  • Basically, Insertion sort is efficient for small data values

  • Insertion sort is adaptive in nature, i.e. it is appropriate for data sets which are already partially sorted.

Insertion Sort

https://www.swtestacademy.com/wp-content/uploads/2021/11/insertion-sort.gif

Implmentation

procedure insertionSort(A: list of sortable items)
   n = length(A)
   for i = 1 to n - 1 do
       j = i
       while j > 0 and A[j-1] > A[j] do
           swap(A[j], A[j-1])
           j = j - 1
       end while
   end for
end procedure
def insertion_sort(data: list):
    
    print(f"Unsorted List: {data}")

    for i in range(1, len(data)):
        print("===" * 10)
        print(f"Iteration: {i} & Current Element: {data[i]}")
        
        key = data[i]
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1

        while j >= 0 and key < data[j] :
                print(f"j = {j}")
                print(f"Swapping {data[j]} with {data[j + 1]}")
                data[j + 1] = data[j]
                j -= 1
                print(f"Swapped List: {data}")
        
        print(f"Inserting {key} at position {j + 1}")
        data[j + 1] = key
        print(f"New List: {data}")
        print("===" * 10)
    
    return data
 
insertion_sort([12, 11, 13, 5, 6])

print("####" * 10)

insertion_sort([6, 11, 6, 44, 6,7,9,22,0])
 
# This code is contributed by Mohit Kumra
Unsorted List: [12, 11, 13, 5, 6]
==============================
Iteration: 1 & Current Element: 11
j = 0
Swapping 12 with 11
Swapped List: [12, 12, 13, 5, 6]
Inserting 11 at position 0
New List: [11, 12, 13, 5, 6]
==============================
==============================
Iteration: 2 & Current Element: 13
Inserting 13 at position 2
New List: [11, 12, 13, 5, 6]
==============================
==============================
Iteration: 3 & Current Element: 5
j = 2
Swapping 13 with 5
Swapped List: [11, 12, 13, 13, 6]
j = 1
Swapping 12 with 13
Swapped List: [11, 12, 12, 13, 6]
j = 0
Swapping 11 with 12
Swapped List: [11, 11, 12, 13, 6]
Inserting 5 at position 0
New List: [5, 11, 12, 13, 6]
==============================
==============================
Iteration: 4 & Current Element: 6
j = 3
Swapping 13 with 6
Swapped List: [5, 11, 12, 13, 13]
j = 2
Swapping 12 with 13
Swapped List: [5, 11, 12, 12, 13]
j = 1
Swapping 11 with 12
Swapped List: [5, 11, 11, 12, 13]
Inserting 6 at position 1
New List: [5, 6, 11, 12, 13]
==============================
########################################
Unsorted List: [6, 11, 6, 44, 6, 7, 9, 22, 0]
==============================
Iteration: 1 & Current Element: 11
Inserting 11 at position 1
New List: [6, 11, 6, 44, 6, 7, 9, 22, 0]
==============================
==============================
Iteration: 2 & Current Element: 6
j = 1
Swapping 11 with 6
Swapped List: [6, 11, 11, 44, 6, 7, 9, 22, 0]
Inserting 6 at position 1
New List: [6, 6, 11, 44, 6, 7, 9, 22, 0]
==============================
==============================
Iteration: 3 & Current Element: 44
Inserting 44 at position 3
New List: [6, 6, 11, 44, 6, 7, 9, 22, 0]
==============================
==============================
Iteration: 4 & Current Element: 6
j = 3
Swapping 44 with 6
Swapped List: [6, 6, 11, 44, 44, 7, 9, 22, 0]
j = 2
Swapping 11 with 44
Swapped List: [6, 6, 11, 11, 44, 7, 9, 22, 0]
Inserting 6 at position 2
New List: [6, 6, 6, 11, 44, 7, 9, 22, 0]
==============================
==============================
Iteration: 5 & Current Element: 7
j = 4
Swapping 44 with 7
Swapped List: [6, 6, 6, 11, 44, 44, 9, 22, 0]
j = 3
Swapping 11 with 44
Swapped List: [6, 6, 6, 11, 11, 44, 9, 22, 0]
Inserting 7 at position 3
New List: [6, 6, 6, 7, 11, 44, 9, 22, 0]
==============================
==============================
Iteration: 6 & Current Element: 9
j = 5
Swapping 44 with 9
Swapped List: [6, 6, 6, 7, 11, 44, 44, 22, 0]
j = 4
Swapping 11 with 44
Swapped List: [6, 6, 6, 7, 11, 11, 44, 22, 0]
Inserting 9 at position 4
New List: [6, 6, 6, 7, 9, 11, 44, 22, 0]
==============================
==============================
Iteration: 7 & Current Element: 22
j = 6
Swapping 44 with 22
Swapped List: [6, 6, 6, 7, 9, 11, 44, 44, 0]
Inserting 22 at position 6
New List: [6, 6, 6, 7, 9, 11, 22, 44, 0]
==============================
==============================
Iteration: 8 & Current Element: 0
j = 7
Swapping 44 with 0
Swapped List: [6, 6, 6, 7, 9, 11, 22, 44, 44]
j = 6
Swapping 22 with 44
Swapped List: [6, 6, 6, 7, 9, 11, 22, 22, 44]
j = 5
Swapping 11 with 22
Swapped List: [6, 6, 6, 7, 9, 11, 11, 22, 44]
j = 4
Swapping 9 with 11
Swapped List: [6, 6, 6, 7, 9, 9, 11, 22, 44]
j = 3
Swapping 7 with 9
Swapped List: [6, 6, 6, 7, 7, 9, 11, 22, 44]
j = 2
Swapping 6 with 7
Swapped List: [6, 6, 6, 6, 7, 9, 11, 22, 44]
j = 1
Swapping 6 with 6
Swapped List: [6, 6, 6, 6, 7, 9, 11, 22, 44]
j = 0
Swapping 6 with 6
Swapped List: [6, 6, 6, 6, 7, 9, 11, 22, 44]
Inserting 0 at position 0
New List: [0, 6, 6, 6, 7, 9, 11, 22, 44]
==============================
[0, 6, 6, 6, 7, 9, 11, 22, 44]

Merge sort

Merge sort is a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.

Merge Sort

The “Merge Sort” uses a recursive algorithm to achieve its results.

Advantages of the Merge Sort

  • Merge sort can efficiently sort a list in O(n*log(n)) time.

  • Merge sort can be used with linked lists without taking up any more space.

  • A merge sort algorithm is used to count the number of inversions in the list.

  • Merge sort is employed in external sorting.

Drawbacks of the Merge Sort

  • For small datasets, merge sort is slower than other sorting algorithms.

  • For the temporary array, mergesort requires an additional space of O(n).

  • Even if the array is sorted, the merge sort goes through the entire process.

Python implementation of MergeSort

def mergeSort(arr):
	if len(arr) > 1:

		# Finding the mid of the array
		mid = len(arr)//2

		# Dividing the array elements
		L = arr[:mid]

		# into 2 halves
		R = arr[mid:]

		# Sorting the first half
		mergeSort(L)

		# Sorting the second half
		mergeSort(R)

		i = j = k = 0

		# Copy data to temp arrays L[] and R[]
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1

		# Checking if any element was left
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1

		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

arr = [12, 11, 13, 5, 6, 7]
print(arr)
mergeSort(arr)
print(arr)
[12, 11, 13, 5, 6, 7]
[5, 6, 7, 11, 12, 13]