Sorting Algorithms- Insertion Sort, Selection Sort, Quick Sort, Merge Sort, Bubble Sort

Sorting:

Arranging the elements in ascending order or in descending order is called Sorting. Sorting techniques are broadly categorized into two.

1. Internal Sorting and
2. External Sorting.

1. Internal Sorting : All the records that are to be sorted are in main memory.

2. External Sorting: Some sorts that cannot be performed in main memory and must be done on disk or tape. This type of sorting is known as External Sorting.

Efficiency: One of the major issues in the sorting algorithms is its efficiency. If we can efficiently sort the records then that adds value to the sorting algorithm. We usually denote the efficiency of sorting algorithm in terms of time complexity. The time complexities are given in terms of big-oh notation.

Commonly there are O(n2) and O(n log n ) time complexities for various algorithms. Quick sort is the fastest algorithm and bubble sort is the slowest one.

Sorting Method — — — — — — — — — — — — — - Efficiency

Bubble sort/Selection sort/Insertion sort — — — — 0(n2)

Quick / Merge — — — — — — — — — — — — — — — 0(n log n)

Insertion Sort Algorithm:

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.

Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Time Complexity of InsertionSort

Best Case : O(n) #Means array is already sorted.

Average Case : O(n²) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Example:

Let us sort the following numbers using Insertion sort mechanism,
12, 11, 13, 5, 15

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 15

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 15

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 15

i = 4. 15 will be at position 5 as all the elements are smaller than 15.
5, 11, 12, 13,15

Implementation

def insertion_sort(array):
for i in range(len(array)):
        for j in range(0,i+1):
            if array[i] < array[j]:
                array[i],array[j] = array[j] ,array[i]
    for val in array:
        print(val,end = " ")
print("Enter elements into the array")
array = [int(n) for n in input().split()]
insertion_sort(array)

Output:

1.
Enter elements into the array
1 5 3 2 4
Elements After Sorting
1 2 3 4 5
2.
Enter elements into the array
12 11 13 5 15
Elements After Sorting
5 11 12 13 15

Selection Sort Algorithm

Selection Sort: The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

Time Complexity of InsertionSort

Best Case : O(n²) #Means array is already sorted.

Average Case : O(n²) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Following example explains the above steps:

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

Implementation:

def selection_sort(array):
    sorted_array = []
    #Initializing the second array with spaces in it
    for i in range(len(array)):
        sorted_array.append(" ")
    for i in range(len(array)):
        #Take minimum element in the array
        ele = min(array)
        #taking the index of the minimum element
        index = array.index(min(array))
        #Removing the minimum element in the array
        del array[index]
        #Adding the minimum element to second array
        sorted_array[i] = ele
        print("Elements After Sorting")
        for val in sorted_array:
            print(val,end = " ")
print("Enter elements into array")
array = [int(n) for n in input().split()]
selection_sort(array)

Output:

1.
Enter elements into array
7 1 4 2 0 76
Elements After Sorting
0 1 2 4 7 76
2.
Enter elements into array
12 11 13 5 15
Elements After Sorting
5 11 12 13 15

Quick Sort Algorithm:

Quick Sort: This is the best sort Technique. QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot
3. Pick a random element as pivot.
4. Pick median as pivot.

Time Complexity :

Best Case : O(nlogn) #Means array is already sorted.

Average Case : O(nlogn) #Means array with random numbers.

Worst Case : O(n^2) #Means array with descending order.

Algorithm:

1. First element is considered as pivot in the implemented code below.
2. Then we should move all the elements which are less than pivot to one side and greater than pivot to other side.
3. We divide the array into two arrays in such a way that elements > pivot and elements < pivot.

Implementation:

def quick_sort(arr,first_index,last_index):
    if first_index < last_index:
        
         pivot = first_index
         i = first_index + 1
         j = last_index
         while i < j:
           #Incrementing i till element is greater than element at pivot
           while arr[i] < arr[pivot] and i < last_index:
                 i+=1
        
           #Decrementing j till element is less than element at pivot
           while arr[j] > arr[pivot]:
                 j-=1
           if i < j:
                 arr[i], arr[j] = arr[j],arr[i]
         arr[pivot], arr[j] = arr[j],arr[pivot]
         
         #Sorting Elements Before Swaping the pivot elements
         quick_sort(arr,first_index,j-1)
         quick_sort(arr,j+1,last_index)
print("Enter size of array")
N = int(input())
print("Enter Elements into the array")
arr = [int(n) for n in input().split()]
quick_sort(arr,0,N-1)

print("Elements After Sorting")
for i in range(N):
    print(arr[i],end=" ")

Output:

Enter size of array
9
Enter Elements into the array
16 75 19 12 33 23 10 45 54
After Sorting
10 12 16 19 23 33 45 54 75 

Merge Sort Algorithm:

Merge Sort: One of the best sorting technique. If n value is large, it follows divide and conquer approach.

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.

Time Complexity :

Best Case : O(nlogn) #Means array is already sorted.

Average Case : O(nlogn) #Means array with random numbers.

Worst Case : O(nlogn) #Means array with descending order.

Algorithm:

1. Find the middle point to divide the array into two halves:  
        middle m = (l+r)/2
2. Call mergeSort for first half:   
        Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
        Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
        Call merge(arr, l, m, r)

Example:

Let us take an array of elements 16,75,19,12,33,2,310,45,54

Partition Mechanism :

Merging Mechanism:

Implementation:

# Python program for implementation of MergeSort 
# Merges two subarrays of array[]. 
# First subarray is arr1[low..mid] 
# Second subarray is arr2[mid+1..high] 
def mergeSort(array, low, mid, high): 
    n1 = mid - low + 1
    n2 = high - mid 
  
    # create temp arrays 
    arr1 = [0] * (n1) 
    arr2 = [0] * (n2) 
  
    # Copy data to temp arrays arr1[] and arr2[] 
    for i in range(0 , n1): 
        arr1[i] = array[low + i] 
  
    for j in range(0 , n2): 
        arr2[j] = array[mid + 1 + j] 
  
    # Merge the temp arrays back into arr[l..r] 
    i = 0     # Initial index of first subarray 
    j = 0     # Initial index of second subarray 
    k = low   # Initial index of merged subarray 
  
    while i < n1 and j < n2 : 
        if arr1[i] <= arr2[j]: 
            array[k] = arr1[i] 
            i += 1
        else: 
            array[k] = arr2[j] 
            j += 1
        k += 1
  
    # Copy the remaining elements of arr1[], if there are any 
    while i < n1: 
        array[k] = arr1[i] 
        i += 1
        k += 1
  
    # Copy the remaining elements of arr2[], if there are any 
    while j < n2: 
        array[k] = arr2[j] 
        j += 1
        k += 1
def partition(array,low,high): 
    if low < high: 
  
       #Same as (low+high)//2, but avoids overflow for large low and high 
       mid = (low+(high-1))//2
  
        # Sort first and second halves 
        partition(array, low, mid) 
        partition(array, mid+1, high) 
        mergeSort(array, low, mid, high) 
  
  
print("Enter Elements into array")
array = [int(n) for n input().split()] 
n = len(array) 
  
partition(array,0,n-1) 
print ("\n\nSorted array is") 
for i in range(n): 
    print ("%d" %array[i])

Output:

Enter Elements into array
16 75 19 12 33 23 10 45 54
Sorted array is
10 12 16 19 23 33 45 54 75

Bubble Sort:

A well known algorithm called Bubble sort, is easy to understand. Probably this is the least efficient. The basic idea underlying the bubble sort is to pass through the array left to right several times. Each pass consists of comparing each element in the array with its successor and interchanging the two elements if they are not in proper order. At the end of each pass we can observe that the largest element of the list is moved to its final position.

Explanation:

Time Complexity :

Best Case : O(n²) #Means array is already sorted.

Average Case : O(n²) #Means array with random numbers.

Worst Case : O(n²) #Means array with descending order.

Implementation:

def bubble_sort(array,n):
    for i in range(n):
        for j in range(n):
            if j+1 < n:
                if array[j] > array[j+1]:
                    array[j],array[j+1] = array[j+1],array[j]
print("Enter Elements into array")
array = [int(n) for n in input().split()]
n = len(array)
bubble_sort(array,n)
print("After Sorting")
for val in array:
    print(val,end = " ")

Output

Enter Elements into array
16 75 19 12 33 23 10 45 54
After Sorting
10 12 16 19 23 33 45 54 75