Sorting

Sorting Algorithms

Sl No.

Algorithm

Worst Time

Average Time

Best Time

Memory

Stability

1

Bubble Sort

\[n^2\]
\[n^2\]
\[n\]
\[1\]

Stable

2

Selection Sort

\[n^2\]
\[n^2\]
\[n^2\]
\[1\]

Unstable

3

Insertion Sort

\[n^2\]
\[n^2\]
\[n^2\]
\[1\]

Stable

4

Merge Sort

\[n * log(n)\]
\[n * log(n)\]
\[n * log(n)\]
\[n\]

Stable

5

Quick Sort

\[n * log(n)\]
\[n * log(n)\]
\[n^2\]
\[n * log(n)\]

Unstable

Note

  • Stable : Relative position of equal elements after sorting remains same.

  • In-place Sorting : Sorting Input elements without having backup, thus unsorted form is lost.

Bubble Sort

class bubbleSort[source]

Bases: object

bubble_sort(data)[source]

Description

Important

TIme Complexity
  • Worst Case: \(n^2\)

  • Average Case: \(n^2\)

  • Best Case: \(n\)

Space Complexity: \(O(1)\)
In Place Sorting
Stable Sorting

Python

def bubble_sort(data):
    for i in range(len(data) - 1):
        for j in range(0, len(data) - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data

Implementation

Selection Sort

class selectionSort[source]

Bases: object

selection_sort(data)[source]

Description

Important

TIme Complexity
  • Worst Case: \(n^2\)

  • Average Case: \(n^2\)

  • Best Case: \(n^2\)

Space Complexity: \(O(1)\)
In Place Sorting
Unstable Sorting

Python

def selection_sort(data):
    for i in range(len(data)):
        min_index = i
        for j in range(i + 1, len(data)):
            if data[min_index] > data[j]:
                min_index = j
        data[i], data[min_index] = data[min_index], data[i]
    return data

Implementation

Insertion Sort

class insertionSort[source]

Bases: object

insertion_sort(data)[source]

Description

Tip

  • Insertion sort is used when number of elements is small.

  • It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

Important

TIme Complexity
  • Worst Case: \(n^2\)

  • Average Case: \(n^2\)

  • Best Case: \(n^2\)

Space Complexity: \(O(1)\)
In Place Sorting
Stable Sorting

Python

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and key < data[j]:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

Implementation

Merge Sort

class MergeSort[source]

Bases: object

merge_sort(data)[source]

Description

Important

TIme Complexity
  • Worst Case: \(n * log(n)\)

  • Average Case: \(n * log(n)\)

  • Best Case: \(n * log(n)\)

Space Complexity: \(O(n)\)
In Place Sorting
Stable Sorting

Python

def merge_sort(data):
    if len(data) > 1:
        mid = len(data) // 2
        left = data[:mid]
        right = data[mid:]

        merge_sort(left)
        merge_sort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                data[k] = left[i]
                i += 1
            else:
                data[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            data[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            data[k] = right[j]
            j += 1
            k += 1

Implementation

Quick Sort

class QuickSort[source]

Bases: object

partition(data, low, high)[source]
quick_sort(data, low, high)[source]

Description

Important

TIme Complexity
  • Worst Case: \(n * log(n)\)

  • Average Case: \(n * log(n)\)

  • Best Case: \(n^2\)

Space Complexity: \(O(n * log(n))\)
In Place Sorting
Unstable Sorting

Python

Algorithm for partition

def partition(data, low, high):
    pivot = data[high]
    i = low  # To keep the index of element smaller than pivot
    j = low  # To keep the index of element greater than pivot

    while j < high:
        if data[j] < pivot:
            data[j], data[i] = data[i], data[j]
            i += 1
        j += 1

    data[i], data[high] = data[high], data[i]

    return i

Recursive Algorithm for quicksort

def quick_sort(data, low, high):
    if low < high:
        pivot = partition(data, low, high)
        quick_sort(data, low, pivot - 1)
        quick_sort(data, pivot + 1, high)

Implementation