Insertion Sort?

Insertion sort is a simple and efficient comparison sort. In this algorithm, each iteration removes an element from the input list and inserts it into the sorted sublist.

Implementation

def insertionSort(A):
    for i in range(1, len(A)):
        temp = A[i]
        k = i
        while k > 0 and temp < A[k - 1]:
            A[k] = A[k - 1]
            k -= 1
        A[k] = temp

A = [10,4,43,5,57,91,45,9,7]
insertionSort(A)
print(A)

Performance

• Worst-case complexity: O(n^2)
• Best case complexity: O(n)
• Average case complexity: O(n^2)
• Worst-case space complexity: O(n^2) total, O(1) auxiliary

Advantages

• Easy to implement
• Efficient for small data
• Adaptive: If the input list is presorted [may not be complete] then insertions sort takes O(n+d), where is the number of inversions
• Practically more efficient than selection and bubble sorts, even though all of them have O(n^2) worst-case complexity
• Stable: Maintains relative order of input data if the keys are the same
• In-place: It requires only a constant amount of O(1) of additional memory space
• Online: Insertion sort can sort the list as it receives it

Shell Sort?

Shell Sort (also called diminishing increment sort)was invented by Donald Shell. This sorting algorithm is a generalization of insertion sort. Insertion sort works efficiently on input that is already almost sorted. The shell sort is also known as the n-gap insertion sort.

Implementation

def ShellSort(A):
    sublistcount = len(A) // 2
    while sublistcount > 0:
        for startposition in range(sublistcount):
            gapInsertionSort(A, startposition, sublistcount)
        print ('After increments of size', sublistcount, 'The list is',
               A)
        sublistcount = sublistcount // 2


def gapInsertionSort(A, start, gap):
    for i in range(start + gap, len(A), gap):
        currentvalue = A[i]
        position = i
        while position >= gap and A[position - gap] > currentvalue:
            A[position] = A[position - gap]
            position = position - gap
        A[position] = currentvalue
A = [534,246,933,127,277,321,454,565,220]
ShellSort(A)
print(A)

Performance

• Worst-case complexity: O(nlog²n)
• Best case complexity: O(n)
• Average case complexity depends on gap sequence
• Worst-case space complexity: O(n)

Merge Sort?

Merge sort is an example of the divide and conquer strategy. Merge sort first divides the array into equal halves and then combines them in a sorted manner. It is a recursive algorithm that continually splits an array in half. If the array is empty or has one element, it is sorted by definition (the base case).

Implementation

def mergeSort(A):
    if len(A) > 1:
        mid = len(A) // 2
        lefthalf = A[:mid]
        righthalf = A[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i = j = k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                A[k] = lefthalf[i]
                i = i + 1
            else:
                A[k] = righthalf[j]
                j = j + 1
            k = k + 1
        while i < len(lefthalf):
            A[k] = lefthalf[i]
            i = i + 1
            k = k + 1
        while j < len(righthalf):
            A[k] = righthalf[j]
            j = j + 1
            k = k + 1
A = [534,246,933,127,277,321,454,565,220]
mergeSort(A)
print(A)

Performance

• Worst-case complexity: O(nlogn)
• Best case complexity: O(nlogn)
• Average case complexity: O(nlogn)
• Worst-case space complexity: O(nlogn) for runtime stack space and O(݊) for the auxiliary space

Quick Sort?

Quicksort is a famous algorithm among comparison-based sorting algorithms. Like merge sort, quick sort uses the divide-and-conquer technique, and so it's a recursive algorithm. The way that quicksort uses divide-and-conquer is a little different from how merge sort does. The quicksort uses the divide-and-conquer technique to gain the same advantages as the merge sort, while not using additional storage. As a trade-off, however, it is possible that the list may not be divided into half.

Implementation

def quick_sort(A, low, high):
    if low < high:
        partition_point = partition(A, low, high)
        quick_sort(A, low, partition_point - 1)
        quick_sort(A, partition_point + 1, high)


def partition(A, low, high):
    pivot = A[low]
    left = low + 1
    right = high
    done = False
    while not done:
        while left <= right and A[left] <= pivot:
            left = left + 1
        while A[right] >= pivot and right >= left:
            right = right - 1
            if right < left:
                done = True
            else:
                temp = A[left]
                A[left] = A[right]
                A[right] = temp
    temp = A[low]
    A[low] = A[right]
    A[right] = temp
    return right
A = [50,25,92,16,76,30,43,54,19]
quick_sort(A,0,len(A)-1)
print(A)

Performance

• Worst-case complexity: O(n^2)
• Best case complexity: O(nlogn)
• Average case complexity: O(nlogn)
• Worst-case space complexity: O(1)

If you enjoyed this article, share it with your friends and colleagues! And we will discuss interesting techniques in the upcoming blog........