Sorting Algorithms

Sorting algorithms are fundamental in computer science and are widely used in Leetcode problems. They arrange elements in a specific order (ascending or descending). Here, we cover the most common sorting algorithms and their applications.

Table of Contents
Sorting Basics
Common Sorting Algorithms
Time and Space Complexity
Related Leetcode Questions
- Easy
- Medium
- Hard

Sorting Basics

Definition: Sorting is the process of arranging elements in a specific order (e.g., ascending or descending).
Key Characteristics:
- In-place Sorting: Sorting algorithms that use constant extra space.
- Stable Sorting: Sorting algorithms that maintain the relative order of equal elements.
- Comparison-based Sorting: Sorting algorithms that compare elements to determine their order.

Common Sorting Algorithms

1. Bubble Sort

Algorithm: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Example:

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Time Complexity: O(n^2)
Space Complexity: O(1)

2. Selection Sort

Algorithm: Repeatedly selects the smallest (or largest) element from the unsorted portion and swaps it with the first unsorted element.

Example:

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Time Complexity: O(n^2)
Space Complexity: O(1)

3. Insertion Sort

Algorithm: Builds the final sorted array one element at a time by repeatedly inserting the next element into the correct position.

Example:

public void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Time Complexity: O(n^2)
Space Complexity: O(1)

4. Merge Sort

Algorithm: Divides the array into two halves, recursively sorts them, and then merges the two sorted halves.

Example:

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
private void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Time Complexity: O(n log n)
Space Complexity: O(n)

5. Quick Sort

Algorithm: Picks a pivot element, partitions the array into two halves (elements less than the pivot and elements greater than the pivot), and recursively sorts the two halves.

Example:

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Time Complexity: O(n log n) (average), O(n^2) (worst case)
Space Complexity: O(log n) (due to recursion)

6. Heap Sort

Algorithm: Builds a max-heap from the array, repeatedly extracts the maximum element from the heap, and places it at the end of the array.

Example:

public void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}
private void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

Time Complexity: O(n log n)
Space Complexity: O(1)

Time and Space Complexity

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Bubble Sort	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Selection Sort	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Merge Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`
Quick Sort	`O(n log n)`	`O(n log n)`	`O(n^2)`	`O(log n)`
Heap Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`

Sorting Algorithms

Table of Contents

Sorting Basics

Common Sorting Algorithms

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Merge Sort

5. Quick Sort

6. Heap Sort

Time and Space Complexity

Related Leetcode Questions

Easy

Medium

Hard