Thuật toán C/C++

Quick Sort

Quick sort đặt pivot vào vị trí cuối rồi đệ quy sort hai partition.

Quick Sort là gì?

Quick sort đặt pivot vào vị trí cuối rồi đệ quy sort hai partition.

Partition dữ liệu quanh pivot.

Điểm quan trọng

Test input rỗng, một phần tử, trùng lặp và đã sắp xếp.
Tách correctness khỏi optimization.
Ưu tiên standard library trong code production.

Mô phỏng Quick Sort

O(n log n)

Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.

Code ví dụ bằng C và C++

Chạy code →

main.c

#include <stdio.h>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}

Output dự kiến

3 4 5 7 9 10

C++

Chạy code →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}

Output dự kiến

3 4 5 7 9 10

So sánh C và C++

Trung bình O(n log n), pivot xấu thành O(n²). C++ dùng std::partition để biểu diễn bước partition.

Loop, pointer, length và buffer tạm được viết tường minh.

C++

Iterator và standard algorithm tách operation khỏi cách lưu dữ liệu.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Trace từng phép so sánh trên giấy.
Test duplicate và extreme value.
Benchmark code tự viết với standard library.