Thứ Năm, 1 Tháng Mười Hai 2022
Trang chủLập trìnhCTDL & Thuật toánThuật toán sắp xếp nhanh (Quick Sort)

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

Trong bài viết này Blog tuicocach.com sẽ giới thiệu tới các bạn thuật toán sắp xếp nhanh(Quick Sort). Đây là một trong các thuật toán sắp xếp căn bản thường dùng.

Ý tưởng của thuật toán sắp xếp nhanh Quick sort

Minhh họa thuật toán sắp xếp nhanh(Nguồn wikipedia)
Minhh họa thuật toán sắp xếp nhanh(Nguồn wikipedia)

Cũng giống như Merge sort, thuật toán sắp xếp nhanh quick sort là một thuật toán chia để trị. Nó chọn một phần tử trong mảng làm điểm đánh dấu(pivot). Thuật toán sẽ thực hiện tìm vị trí đúng cho phần tử pivot trong mảng, sau đó dựa vào pivot chia mảng thành 2 mảng con. Việc lựa chọn pivot ảnh hưởng rất nhiều tới tốc độ sắp xếp. Nhưng máy tính lại không thể biết khi nào thì nên chọn theo cách nào.

Phần tử pivot thường chọn theo 4 cách:

  • Luôn chọn phần tử đầu tiên của mảng
  • Luôn chọn phần tử cuối cùng của mảng
  • Chọn phần tử nằm giữa mảng
  • Chọn một phần tử random.
XÊM THÊM
Thuật toán sắp xếp chọn(Selection Sort)
Thuật toán sắp xếp chèn (Insertion sort)
Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán phân đoạn

Minh họa dưới đây minh họa cho quá trình phân đoạn với phần tử pivot chọn là phần tử cuối cùng của dãy arr.

Minh họa quá trình phân đoạn trong thuật toán quick sort
Minh họa quá trình phân đoạn trong thuật toán quick sort

Đặt pivot là phần tử cuối cùng của dãy số arr. Chúng ta bắt đầu từ phần tử trái nhất của dãy số có chỉ số là left, và phần tử phải nhất của dãy số có chỉ số là right -1(bỏ qua phần tử pivot). Chừng nào left < right mà arr[left] > pivot và arr[right] < pivot thì đổi chỗ hai phần tử left và right. Sau cùng, ta đổi chỗ hai phần tử left và pivot cho nhau. Khi đó, phần tử pivot đã đứng đúng vị trí và chia dãy số làm đôi(bên trái và bên phải).

Code minh họa thuật toán phân đoạn:

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int left = low;
    int right = high - 1;
    while(true){
        while(left <= right && arr[left] < pivot) left++; // Tìm phần tử >= arr[pivot]
        while(right >= left && arr[right] > pivot) right--; // Tìm phần tử <= arr[pivot]
        if (left >= right) break; // Đã duyệt xong thì thoát vòng lặp
        swap(arr[left], arr[right]); // Nếu chưa xong, đổi chỗ.
        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]); //Đổi chỗ phần từ left với pivot, khi đó pivot đứng đúng vị trí
    return left; // Trả về chỉ số sẽ dùng để chia đổi mảng
}

Quy trình của thuật toán sắp xếp nhanh quick sort

Bước 1: Lấy phần tử chốt là phần tử cuối cùng(có thể chọn phần tử đầu tiên, giữa hoặc random).

Bước 2: Chia mảng theo phần tử chốt.

Bước 3: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái.

Bước 4: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải.

Code minh họa:

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

Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
Top những App kiếm tiền online trên điện thoại tốt nhất hiện nay

Cài đặt thuật toán quick sort trên C/C++

#include <stdio.h>
void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int left = low;
    int right = high - 1;
    while(true){
        while(left <= right && arr[left] < pivot) left++; // Tìm phần tử >= arr[pivot]
        while(right >= left && arr[right] > pivot) right--; // Tìm phần tử <= arr[pivot]
        if (left >= right) break; // Đã duyệt xong thì thoát vòng lặp
        swap(arr[left], arr[right]); // Nếu chưa xong, đổi chỗ.
        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]); //Đổi chỗ phần từ left với pivot, khi đó pivot đứng đúng vị trí
    return left; // Trả về chỉ số sẽ dùng để chia đổi mảng
}
 
/* Hàm giải thuật quicksort */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi là chỉ số nơi phần tử này đã đứng đúng vị trí
         và là phần tử chia mảng làm 2 mảng con trái & phải */
        int pi = partition(arr, low, high);
 
        // Gọi đệ quy sắp xếp 2 mảng con trái và phải
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
 
int main()
{
    int arr[] = {1, 8, 3, 9, 4, 5, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);

    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Kết quả chạy thử:

Kết quả chạy thử chương trình minh họa
Kết quả chạy thử chương trình minh họa

Đánh giá thuật toán sắp xếp quick sort

Độ  phức tạp thuật toán của quick sort

  • Trường hợp tốt: O(nlog(n))
  • Trung bình: O(nlog(n))
  • Trường hợp xấu: O(n^2)

Cảm ơn đã theo dõi bài viết, nếu có bất kỳ thắc mắc hay góp ý comment bên dưới nhé.

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x