Quick Sort Algorithm

1. Algorithm Explanation

Quick Sort is a divide-and-conquer, comparison-based sorting algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Steps:

  1. Choose a pivot (e.g., first element, last element, or median-of-three).
  2. Partition: Rearrange elements so that those less than the pivot come before it and those greater come after it.
  3. Recursively apply Quick Sort to the sub-array of elements less than the pivot and the sub-array of elements greater than the pivot.

Time Complexity

  • Average case: O(n × log n)
  • Worst case: O(n2) (when the smallest or largest element is always chosen as pivot)

Memory Complexity

  • In-place partitioning: O(log n) for recursion stack (average)
  • Worst-case stack depth: O(n)

2. Easy Problems

  1. 2.1 Sort an Array of Integers

    Given an array of integers, sort it in ascending order.

    #include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; ++j) {
            if (arr[j] < pivot) {
                std::swap(arr[++i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        int pi = i + 1;

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {3, 6, 8, 10, 1, 2, 1};
    quickSort(arr, 0, arr.size() - 1);
    for (int x : arr) std::cout << x << " ";
    return 0;
}

  2. 2.2 Sort an Array of Strings

    Given an array of strings, sort them lexicographically.

    #include <iostream>
#include <vector>
#include <string>

void quickSort(std::vector<std::string>& arr, int low, int high) {
    if (low < high) {
        std::string pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; ++j) {
            if (arr[j] < pivot) {
                std::swap(arr[++i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        int pi = i + 1;

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<std::string> arr = {"apple", "orange", "banana", "pear"};
    quickSort(arr, 0, arr.size() - 1);
    for (const auto& s : arr) std::cout << s << " ";
    return 0;
}

3. Intermediate Problems

  1. 3.1 Find the k-th Smallest Element (Quickselect)

    Given an unsorted array, find the k-th smallest element.

    #include <iostream>
#include <vector>

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) std::swap(arr[i++], arr[j]);
    }
    std::swap(arr[i], arr[high]);
    return i;
}

int quickSelect(std::vector<int>& arr, int low, int high, int k) {
    if (low == high) return arr[low];
    int pi = partition(arr, low, high);
    int count = pi - low + 1;
    if (count == k) return arr[pi];
    if (k < count) return quickSelect(arr, low, pi - 1, k);
    return quickSelect(arr, pi + 1, high, k - count);
}

int main() {
    std::vector<int> arr = {7, 10, 4, 3, 20, 15};
    int k = 3;
    std::cout << "The " << k << "-th smallest element is "
              << quickSelect(arr, 0, arr.size() - 1, k);
    return 0;
}

  2. 3.2 Sort 2D Points by X-coordinate

    Given a list of 2D points, sort them by their x-coordinate.

    #include <iostream>
#include <vector>
#include <utility>

void quickSort(std::vector<std::pair<int,int>>& pts, int low, int high) {
    if (low < high) {
        auto pivot = pts[high];
        int i = low - 1;
        for (int j = low; j < high; ++j) {
            if (pts[j].first < pivot.first) {
                std::swap(pts[++i], pts[j]);
            }
        }
        std::swap(pts[i + 1], pts[high]);
        int pi = i + 1;

        quickSort(pts, low, pi - 1);
        quickSort(pts, pi + 1, high);
    }
}

int main() {
    std::vector<std::pair<int,int>> pts = {{3,4}, {1,2}, {5,0}, {2,3}};
    quickSort(pts, 0, pts.size() - 1);
    for (auto& p : pts)
        std::cout << "(" << p.first << "," << p.second << ") ";
    return 0;
}

4. Hard Problem

4.1 Sort a Singly Linked List

Implement in-place Quick Sort for a singly linked list.

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

Node* partition(Node* head, Node* end, Node** newHead, Node** newEnd) {
    Node* pivot = end;
    Node *prev = nullptr, *cur = head, *tail = pivot;

    while (cur != pivot) {
        if (cur->data < pivot->data) {
            if (!*newHead) *newHead = cur;
            prev = cur;
            cur = cur->next;
        } else {
            if (prev) prev->next = cur->next;
            Node* tmp = cur->next;
            cur->next = nullptr;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }
    if (!*newHead) *newHead = pivot;
    *newEnd = tail;
    return pivot;
}

Node* quickSortRecur(Node* head, Node* end) {
    if (!head || head == end) return head;

    Node *newHead = nullptr, *newEnd = nullptr;
    Node* pivot = partition(head, end, &newHead, &newEnd);

    if (newHead != pivot) {
        Node* tmp = newHead;
        while (tmp->next != pivot) tmp = tmp->next;
        tmp->next = nullptr;
        newHead = quickSortRecur(newHead, tmp);
        tmp = getTail(newHead);
        tmp->next = pivot;
    }

    pivot->next = quickSortRecur(pivot->next, newEnd);
    return newHead;
}

Node* getTail(Node* cur) {
    while (cur && cur->next) cur = cur->next;
    return cur;
}

int main() {
    Node* head = new Node(30);
    head->next = new Node(3);
    head->next->next = new Node(4);
    head->next->next->next = new Node(20);
    head->next->next->next->next = new Node(5);

    head = quickSortRecur(head, getTail(head));
    for (Node* cur = head; cur; cur = cur->next) std::cout << cur->data << " ";
    return 0;
}