Thuật Toán Quick Sort

Chào mừng các bạn đến với chủ đề thuật toán lập trình.

Hôm nay chúng ta cùng tìm hiểu về thuật toán Quick Sort.

1. Nguyên lý cơ bản của Quick Sort.

– Cũng dựa trên nguyên lý chia để trị, nó chia mảng thành nhiều vùng nhỏ rồi mới thực hiện việc sắp xếp.

– Đạt được tốc độ rất nhanh cho việc sắp xếp một mảng, hiệu quả và tiêu tốn ít tài nguyên.

– Độ phức tạp thời gian là: O(nLog2(n)) với n là số lượng phần tử của tập. xấu nhất sẽ là: O(n²)

– Nguyên lý thực hiện đó là phải chọn được một phần tử ngẫu nhiên gọi là: pivot. (có thể là đầu, cuối giữa…)

– Sắp xếp các phần tử < pivot sang bên trái, còn các phần tử > pivot sang bên phải.

– Sau đó chia nó thành hai tập, một tập trái và một tập phải.

=> Mỗi tập con lúc này lại như một tập ban đầu, lại cần được sắp xếp lại => lại thực hiện chọn chốt, lại phân chia, cho đến khi số lượng phần tử chỉ còn 1. => Tính chất đệ quy.

 

2 Thực hành Thuật toán Quick Sort

– Mấu chốt của thuật toán đó là chọn được phần tử chốt hợp lý nhất, và sau đó là cách chia tệp thành 2 phần, một phần nhỏ hơn chốt và một phần lớn hơn chốt. Sau đó sử dụng tính chất đệ quy để hoàn thành quá trình sắp xếp

// Phattrienphanmem123az.com
#include <iostream>
#include <conio.h>

void Swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
int ImpDiv(int arr[], int left, int right)
{
    // Chose pivot is last element
    int pivot = arr[right];  
    int i = (left - 1);
 
    for (int j = left; j <= right- 1; ++j)
    {
     
        if (arr[j] <= pivot)
        {
            i++;
            Swap(arr[i], arr[j]);
        }
    }
    Swap(arr[i + 1], arr[right]);
    return (i + 1);
}
 
void ImpQuickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int pos = ImpDiv(arr, left, right);
        ImpQuickSort(arr, left, pos - 1);
        ImpQuickSort(arr, pos + 1, right);
    }
}
 
void Show(int arr[], int size)
{
    for (int i = 0; i < size; ++i)
      std::cout << arr[i] << " ";
}
 
int main()
{
    int arr[] = {20, 17, 18, 19, 11, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    ImpQuickSort(arr, 0, n-1);
    std::cout << "Sorted List: ";
    Show(arr, n);

    _getch();
    return 0;
}

TPham