Sorting Algorithms - Cheatsheet | Last Minute Notes

Sorting algorithms are fundamental algorithms in computer science that are used to arrange the elements of a list or array in a specific order, typically in numerical or lexicographical order. Sorting plays a crucial role in various applications, including searching, data organization, and optimization problems.

Selection Sort

It is a simple comparison-based sorting algorithm. It repeatedly selects the smallest (or largest, depending on sorting order) element from an unsorted portion of the array and swaps it with the first unsorted element. This process continues until the entire array is sorted.

Working Steps

→ Initial Setup: Start with an unsorted array.

→ Select Minimum: Find the smallest element in the unsorted part of the array.

→ Swap: Swap this minimum element with the first element of the unsorted part.

→ Move Boundary: Move the boundary of the sorted part one element to the right.

→ Repeat: Repeat the process for the remaining unsorted part of the array until the entire array is sorted.

Pseudo Code

// Selection Sort in C++
void selectionSort(int array[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        std::swap(array[i], array[minIndex]);
    }
}

Time Complexity:
• Best Case: $O(n^2)$
• Average Case: $O(n^2)$
• Worst Case: $O(n^2)$

Space Complexity: $O(1)$

Use Cases

• Small Lists: Ideal for small datasets where simplicity is more critical than performance.

• Educational: Useful for teaching the basics of sorting algorithms.

• When Memory is a Constraint: It’s beneficial when the additional space for sorting is limited because it uses constant memory.

Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm. It builds the final sorted array one item at a time, by inserting each item into its proper place among the previously sorted items.

Working Steps

→ Initial Setup: Start with the first element as a sorted array and the rest as an unsorted array.

→ Pick Next Element: Select the next element from the unsorted portion.

→ Compare and Shift: Compare this element with the elements in the sorted portion and shift all larger elements one position to the right.

→ Insert Element: Insert the selected element into its correct position in the sorted portion.

→ Repeat: Continue the process for all elements until the entire array is sorted.

Pseudo Code

// Insertion Sort in C++
void insertionSort(int array[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j = j - 1;
        }
        array[j + 1] = key;
    }
}

Time Complexity:
• Best Case: $O(n)$
• Average Case: $O(n^2)$
• Worst Case: $O(n^2)$

Space Complexity: $O(1)$

Use Cases

• Small Lists: Effective for small datasets due to minimal overhead.

• Nearly Sorted Data: Ideal for datasets that are already partially sorted.

• Real-time Sorting: Useful for online sorting where elements are continuously added to the list.

Quick Sort

Quick Sort is an efficient comparison-based sorting algorithm that follows the divide-and-conquer paradigm. It selects a 'pivot' element and partitions the array into sub-arrays that are independently sorted.

Working Steps

→ Choose Pivot: Select a pivot element from the array.

→ Partition: Rearrange the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right.

→ Recursively Sort: Apply the same procedure to the sub-arrays formed by the pivot.

→ Combine: Combine the sorted sub-arrays to produce the final sorted array.

Pseudo Code

// Quick Sort in C++
void quickSort(int array[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(array, low, high);
        quickSort(array, low, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, high);
    }
}

int partition(int array[], int low, int high) {
    int pivot = array[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            i++;
            std::swap(array[i], array[j]);
        }
    }
    std::swap(array[i + 1], array[high]);
    return (i + 1);
}

Time Complexity:
• Best Case: $O(n \log n)$
• Average Case: $O(n \log n)$
• Worst Case: $O(n^2)$

Space Complexity: $O(\log n)$

Use Cases

• Large Datasets: Quick Sort is ideal for large datasets due to its efficient average-case performance.

• General-purpose: Suitable for a wide range of applications.

• In-place Sorting: Requires minimal additional memory.

Merge Sort

Merge Sort is a stable and efficient, comparison-based sorting algorithm. It divides the array into halves, recursively sorts them, and then merges the sorted halves to produce the final sorted array.

Working Steps

→ Divide: Split the array into two halves.

→ Conquer: Recursively sort each half.

→ Combine: Merge the two sorted halves to produce the sorted array.

Pseudo Code

// Merge Sort in C++
void mergeSort(int array[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(array, l, m);
        mergeSort(array, m + 1, r);
        merge(array, l, m, r);
    }
}

void merge(int array[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int left[n1], right[n2];

    for (int i = 0; i < n1; i++)
        left[i] = array[l + i];
    for (int j = 0; j < n2; j++)
        right[j] = array[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            array[k] = left[i];
            i++;
        } else {
            array[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        array[k] = left[i];
        i++;
        k++;
    }

    while (j < n2) {
        array[k] = right[j];
        j++;
        k++;
    }
}

Time Complexity:
• Best Case: $O(n \log n)$
• Average Case: $O(n \log n)$
• Worst Case: $O(n \log n)$

Space Complexity: $O(n)$

Use Cases

• Large Datasets: Ideal for large datasets due to its consistent performance.

• External Sorting: Useful for sorting large datasets that don't fit into memory.

• Stable Sort: Preserves the relative order of equal elements.

Bubble Sort

Bubble Sort is a simple, comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

Working Steps

→ Compare: Compare each pair of adjacent elements.

→ Swap: Swap them if they are in the wrong order.

→ Repeat: Repeat the process until no swaps are needed.

Pseudo Code

// Bubble Sort in C++
void bubbleSort(int array[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // Swap array[j] and array[j+1]
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

Time Complexity:
• Best Case: $O(n)$
• Average Case: $O(n^2)$
• Worst Case: $O(n^2)$

Space Complexity: $O(1)$

Use Cases

• Simple Implementation: Easy to understand and implement.

• Small Datasets: Works well for small datasets.

• Educational: Useful for educational purposes to understand sorting algorithms.

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It builds a heap from the input data, then repeatedly extracts the maximum element from the heap and rebuilds the heap until it is empty.

Working Steps

→ Build Heap: Construct a max heap from the input array.

→ Extract Max: Repeatedly remove the maximum element from the heap.

→ Rebuild: Rebuild the heap after each extraction.

Pseudo Code

// Heap Sort in C++
void heapify(int array[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && array[left] > array[largest])
        largest = left;

    if (right < n && array[right] > array[largest])
        largest = right;

    if (largest != i) {
        int swap = array[i];
        array[i] = array[largest];
        array[largest] = swap;
        heapify(array, n, largest);
    }
}

void heapSort(int array[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(array, n, i);

    for (int i = n - 1; i > 0; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        heapify(array, i, 0);
    }
}

Time Complexity:
• Best Case: $O(n \log n)$
• Average Case: $O(n \log n)$
• Worst Case: $O(n \log n)$

Space Complexity: $O(1)$

Use Cases

• In-Place Sorting: Does not require additional memory.

• Consistent Performance: Reliable performance with guaranteed time complexity.

• Priority Queues: Used in the implementation of priority queues.

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each distinct element in the array. The counts are used to place elements in the correct position in the sorted array.

Working Steps

→ Count: Count the occurrences of each element.

→ Accumulate: Calculate the starting index for each element.

→ Sort: Place the elements in the correct position in the output array.

Pseudo Code

// Counting Sort in C++
void countingSort(int array[], int n) {
    int output[n];
    int max = array[0];
    for (int i = 1; i < n; i++)
        if (array[i] > max)
            max = array[i];

    int count[max + 1] = {0};

    for (int i = 0; i < n; i++)
        count[array[i]]++;

    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    for (int i = 0; i < n; i++)
        array[i] = output[i];
}

Time Complexity:
• Best Case: $O(n + k)$
• Average Case: $O(n + k)$
• Worst Case: $O(n + k)$

Space Complexity: $O(n + k)$

Use Cases

• Small Range: Ideal when the range of input elements is small.

• Non-Comparison Sort: Efficient for specific types of datasets.

• Stable Sort: Preserves the relative order of equal elements.

Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing individual digits. It sorts the numbers by least significant digit (LSD) or most significant digit (MSD) order using a stable subroutine such as Counting Sort.

Working Steps

→ Sort by Digit: Sort numbers by each digit, starting from the least significant digit.

→ Stable Sort: Use a stable sorting algorithm for digit sorting.

→ Repeat: Repeat the process for all digit places.

Pseudo Code

// Radix Sort in C++
int getMax(int array[], int n) {
    int max = array[0];
    for (int i = 1; i < n; i++)
        if (array[i] > max)
            max = array[i];
    return max;
}

void countingSortForRadix(int array[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(array[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(array[i] / exp) % 10] - 1] = array[i];
        count[(array[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++)
        array[i] = output[i];
}

void radixSort(int array[], int n) {
    int m = getMax(array, n);

    for (int exp = 1; m / exp > 0; exp *= 10)
        countingSortForRadix(array, n, exp);
}

Time Complexity:
• Best Case: $O(n \cdot k)$
• Average Case: $O(n \cdot k)$
• Worst Case: $O(n \cdot k)$

Space Complexity: $O(n + k)$

Use Cases

• Large Range: Suitable for sorting numbers with a large range.

• Fixed-Length Keys: Effective for fixed-length integer keys.

• Stable Sort: Maintains the relative order of equal elements.