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

Trong bài này mình sẽ giới thiệu thuật toán Quick Sort (sắp xếp nhanh), đây là thuật toán sắp xếp được xem là nhành nhất trong các thuật toán mình đã giới thiệu trước đây.

Chúng ta sẽ cùng nhau tìm hiểu về sắp xếp nhanh là gì? Cũng như cách thức nó hoạt động và triển khai trong C++ như thế nào.

Ở cuối bài viết mình sẽ có một ví dụ sắp xếp trong mảng. Để các bạn áp dụng được thuật toán trong các bài tập thực tế.

1. Sắp xếp nhanh (Quick Sort) là gì?

Về cơ bản thuật toán sắp xếp Quick Sort khá giống như Merge Sort. Đây là một thuật toán áp dụng cách thức chia để trị (Divide and Conquer).

Bài viết này được đăng tại [kiso.vn]

Thuật toán sẽ chọn mốt phần tử trong mảng làm điểm đánh dấu (pivot). Khi chọn được điểm đánh dấu, nó sẽ chia mảng thành hai mảng con bằng cách so sánh với pivot đã chọn. Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng pivot và mảng còn lại sẽ lớn hơn hoặc bằng pivot.

Tốc độ sắp xếp của thuật toán tùy thuộc vào việc lựa chọn pivot, có một số cách chọn như sau:

  1. Chọn phần tử đầu tiên của mảng.
  2. Chọn phần tử cuối cùng của mảng.
  3. Chọn phần tử có giá trị nằm giữa mảng.
  4. Chọn Random một phần tử của mảng.

Trên đây là một số cách chọn thông dụng, được sử dụng nhiều nhất. Tùy thuộc vào bài toán mà ta chọn pivot cho phù hợp.

Các bạn có thể xem hình minh họa dưới đây để có thể hiểu hơn.

thuat toan sap xep quick sort png

Khi chúng ta chọn số 3 làm pivot, thì mảng được chia làm hai phần. Phần bên trái nhỏ hơn hoặc bằng 3, phần bên phải lớn hơn hoặc bằng 3, cả hai phần đều được sắp xếp tằng dần.

Tiếp tục chọn pivot cho mỗi phần. Phần bên trái có pivot là số 1 và phần bên phải có pivot là số 6.

Cứ như vậy chúng ta sẽ chia phần ra cho đến khi không chia được nữa và sắp xếp theo đúng thứ tự.

2. Thuật toán Quick Sort trong C++

Giải thích thuật toán

Trong phần này chúng ta có hai giai đoạn. Giai đoạn một là giai đoạn phân đoạn mảng (partition()) và giai đoạn hai là giai đoạn sắp xếp (quickSort()).

  • Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số cuối cùng của mảng.
  • Tạo hai biến là left và right để trỏ tới bên trái và bên phải của danh sách.
  • Thực hiện so sánh các phần tử với pivot. Nếu phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
  • Sau khi dịch chuyển thực hiện công việc sắp xếp các phần tử trong mảng con mới, trước khi tiếp tục phân đoạn tiếp theo.

Thuật toán Quick Sort trong C++

Ở phần trên mình đã nêu ra các bước viết thuật toán. Để chi tiết hơn mình đã có chú thích rõ ràng, cụ thể trong từng dòng code trong thuật toán dưới đây. Các bạn hãy đọc thật kỹ nhé:

Hàm partition()

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // khai báo phần tử đánh dâu pivot
    int left = low;   //khai báo biến bên trái
    int right = high - 1; //khai báo biến bên phải
    while(true){
        while(left <= right && arr[left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng
        while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng
        if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp
        swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi.
        left++; // Vì left hiện tại đã xét, nên cần tăng
        right--; // Vì right hiện tại đã xét, nên cần giảm
    }
    swap(arr[left], arr[high]);
    return left; // Trả về chỉ số sẽ dùng để chia đôi mảng
}

Hàm quicksort()

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* index là chỉ số nơi phần tử này đã đứng đúng vị trí
         và đây là phần tử chia mảng làm 2 mảng con trái & phải */
        int index = partition(arr, low, high);
 
        // Gọi đệ quy sắp xếp 2 mảng con trái và phải
        quickSort(arr, low, index - 1);
        quickSort(arr, index + 1, high);
    }
}

Hàm swap()

void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

3. Ví dụ sắp xếp Quick Sort trong mảng

Để minh họa cho hình ảnh ở trên, mình sẽ làm ví dụ áp dụng thuật toán sắp xếp nhanh (Quick Sort). Sắp xếp các phần tử trong mảng arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3} theo thứ tự tăng dần.

Code mẫu:

#include<stdio.h>
#include<iostream>
using namespace std;

//tạo hàm swap để tráo đổi các vị trí
void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}
 
//  phân đoạn trong mảng
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // khai báo phần tử đánh dâu pivot
    int left = low;   //khai báo biến bên trái
    int right = high - 1; //khai báo biến bên phải
    while(true){
        while(left <= right && arr[left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng
        while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng
        if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp
        swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi.
        left++; // Vì left hiện tại đã xét, nên cần tăng
        right--; // Vì right hiện tại đã xét, nên cần giảm
    }
    swap(arr[left], arr[high]);
    return left; // Trả về chỉ số sẽ dùng để chia đôi mảng
}
 
/* Hàm thực hiện giải thuật quick sort */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        // index là chỉ số nơi phần tử này đã đứng đúng vị trí và đây là phần tử chia mảng làm 2 mảng con trái & phải 
        int index = partition(arr, low, high);
 
        // Gọi đệ quy sắp xếp 2 mảng con trái và phải
        quickSort(arr, low, index - 1);
        quickSort(arr, index + 1, high);
    }
}
 
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++){
        cout << arr[i];
        cout<<"t";
      }
}
  
int main()
{
    int arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
  
    cout<<"Mảng sau khi được sắp xếp: n";
    printArray(arr, n);
  
    cout<<"n---------------------------------------n";
    cout<<"Chương trình này được đăng tại Kiso.vn";
}

Kết quả:

sap xep quick sort PNG

Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp mảng bằng phương pháp Quick Sort. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nhanh (Quick Sort) trong C++. Chúc các bạn thực hiện thành công!!!

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *