Rate this post

Quicksort là một thuật toán sắp xếp tốt nhất với trung bình. Nó là một thuật toán sắp xếp đệ quy và sử dụng phương pháp chia để sắp xếp dữ liệu.

Thuật toán Quicksort sử dụng một phần tử trong dãy dữ liệu làm “pivot” và chia dãy dữ liệu thành hai phần: một phần có các phần tử nhỏ hơn pivot và một phần có các phần tử lớn hơn pivot. Sau đó, nó sắp xếp hai phần này đệ quy bằng cùng cách.

Các bài viết liên quan

Quicksort là một thuật toán rất hiệu quả vì nó chỉ mất O(n log n) bước để sắp xếp một dãy dữ liệu bất kỳ với điều kiện trung bình. Nó là một trong những thuật toán sắp xếp phổ biến nhất và được sử dụng rộng rãi trong các ngôn ngữ lập trình khác nhau.

Thuật toán Quicksort trong C++

#include <iostream>
using namespace std;

#include<bits/stdc++.h> 
using namespace std;

// hàm chia mảng
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // chỉ số lớn hơn pivot
  
    for (int j = low; j <= high - 1; j++)
    {
        // Nếu phần tử hiện tại nhỏ hơn pivot
        if (arr[j] < pivot)
        {
            i++;    // tăng i
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

/* hàm sắp xếp quick sort */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi là vị trí pivot */
        int pi = partition(arr, low, high);
  
        // Sắp xếp các phần tử trước và sau pivot
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Hàm in mảng
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout<<endl;
}


int main()
{
    cout<<"quickSort"<<endl;
    int a[9] = {6,7,8,3,5,1,4,11,15};
    quickSort(a,0,9);
    printArray(a,9);
    return 0;
}

Trong ví dụ trên, hàm quickSort() chấp nhận một mảng “arr”, vị trí bắt đầu và kết thúc của mảng để sắp xếp. Trong hàm, chúng ta chọn một phần tử trung tâm trong mảng làm pivot và sử dụng vòng lặp để chia mảng thành hai phần: một phần có các phần tử nhỏ hơn pivot và một phần có các phần tử lớn hơn pivot. Sau đó, chúng ta sắp xếp hai phần này đệ quy bằng cùng cách. Cần lưu ý rằng Quicksort có thể gặp phải vấn đề với trường hợp dữ liệu đã được sắp xếp hoặc có một số giá trị trùng lặp, điều này sẽ dẫn đến thuật toán chạy với O(n^2) và không tối ưu. Để giải quyết vấn đề này, có thể sử dụng các giải thuật khác nhau như chọn ngẫu nhiên một pivot hoặc chia đều các phần tử trong mảng.

Quicksort là một thuật toán rất hiệu quả và được sử dụng rộng rãi trong các ngôn ngữ lập trình khác nhau. Tuy nhiên, nó có thể gặp phải vấn đề với trường hợp dữ liệu đã được sắp xếp hoặc có một số giá trị trùng lặp, điều này sẽ dẫn đến thuật toán chạy với O(n^2) và không tối ưu. Để giải quyết vấn đề này, có thể sử dụng các giải thuật khác như chọn ngẫu nhiên một pivot hoặc chia đều các phần tử trong mảng.

Cần lưu ý rằng Quicksort cần sử dụng bộ nhớ để lưu trữ các giá trị của pivot và các giá trị trong quá trình sắp xếp.

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 *

Contact Me on Zalo
Call now