Tìm hiểu thuật toán sắp xếp nhanh trong lập trình với ví dụ bằng lập trình c++

Thuật toán sắp xếp là một giải thuật quan trọng trong lập trình. Bài viết này Stanford sẽ chia sẻ cho các bạn hiểu rõ hơn về thuật toán sắp xếp nhanh (quick sort) cũng như cài đặt bằng lập trình c++.

Thuật toán sắp xếp nhanh (Quick Sort)

Quick Sort là một thuật toán sắp xếp chia để trị (divide and conquer) với độ phức tạp thời gian trung bình là O(nlogn). Thuật toán này hoạt động bằng cách chọn một phần tử làm chốt (pivot), sau đó phân chia mảng thành hai phần: một phần chứa các phần tử nhỏ hơn chốt và phần còn lại chứa các phần tử lớn hơn chốt. Quá trình này được lặp lại đệ quy cho đến khi mảng được sắp xếp.

Các bước thực hiện:

  • Chọn chốt (pivot): Chọn một phần tử trong mảng làm chốt.
  • Phân chia mảng: Sắp xếp lại mảng sao cho tất cả các phần tử nhỏ hơn chốt nằm bên trái và các phần tử lớn hơn chốt nằm bên phải.
  • Đệ quy: Áp dụng thuật toán sắp xếp nhanh cho hai phần mảng con.


Minh họa bằng lập trình C++

Sau khi đã hiểu rõ ý tưởng của thuật toán sắp xếp nhanh, chúng ta bắt đầu thực hiện cài đặt mô tả thuật toán này bằng lập trình c++ như dưới đây:

#include <vector>
using namespace std;
int partition(vector<int> &vec, int low, int high) {
    //Chọn phần tử làm chốt
    int pivot = vec[high];
    //Vị trí sử dụng để hoán đổi
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        // Nếu phần tử hiện tại nhỏ hơn hoặc bằng chốt
        if (vec[j] <= pivot) {
            i++;
            swap(vec[i], vec[j]);
        }
    }
 
    //Thực hiện hoán đổi
    swap(vec[i + 1], vec[high]);
    //Trả về vị trí
    return (i + 1);
}
 
void quickSort(vector<int> &vec, int low, int high) {
    //Nếu vị trí thập nhỏ hơn vị trí cao
    if (low < high) {
        // pi là vị trí của phần tử của chốt
        int pi = partition(vec, low, high);
        //Sắp xếp phần tử trước và sau pi
        quickSort(vec, low, pi - 1);
        quickSort(vec, pi + 1, high);
    }
}
 
int main() {
    vector<int> vec = {20, 2, 9, 7, 12, 15, 1, 6, 8};
    int n = vec.size();
   //Gọi hàm sắp xếp
    quickSort(vec, 0, n - 1); 
    cout <<"Danh sách mảng sau khi sắp xếp: "<<endl;
    for (auto i : vec) {
        cout << i << " ";
    }
    cout <<endl;
    return 0;
}
Đầu ra sau khi sắp xếp là:

1   2  6  7  9  12  15  20
Phân tích độ phức tạp của Quick Sort

  • Độ phức tạp thời gian: O(n log n) trung bình và O(n^2) trong trường hợp xấu nhất
  • Không gian phụ trợ: O(log n) trung bình và O(n) trong trường hợp xấu nhất.

Như vậy qua bài viết này, Stanford đã giúp các bạn học lập trình hiểu hơn về thuật toán sắp nhanh (quick sort) cũng như cài đặt thuật toán bằng lập trình c++. Để hiểu rõ hơn thuật toán này bạn có thể lập trình theo hướng dẫn trong bài viết này nhé. Bạn có thể tìm hiểu các thuật toán sắp xếp trong lập trình ở đây. Chúc các bạn thành công !

Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé.

==========🎬 🎬 🎬==========
☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ
Hotline: 0963 723 236 - 0866 586 366
Website: https://stanford.com.vn
Facebook: https://www.facebook.com/Stanford.com.vn
Youtube: http://bit.ly/2TkKT7I

Tags: thuật toán sắp nhanh (quick sort), thuật toán sắp xếp