[Wiki] Sort cơ bản 3 - Quick Sort - Sắp xếp nhanh

Xem video về Quick Sort ở đây

Đây là code

/*
QuickSort is a Divide and Conquer algorithm.
It picks an element as pivot and partitions the given array around the picked pivot.
There are many different versions of quickSort that pick pivot in different ways.

Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The key process in quickSort is partition().
Target of partitions is, given an array and an element x of array as pivot,
put x at its correct position in sorted array and put all smaller elements (smaller than x) before x,
and put all greater elements (greater than x) after x.
All this should be done in linear time.
*/

#include <iostream>
using namespace std;

void PrintArray(int * arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void Swap(int * a, int * b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int Partition(int * arr, int left, int right)
{
    int pivot = right;

    int curIndex = left;
    for (int i = left; i < right; i++)
    {
        if (arr[i] < arr[pivot])
        {
            Swap(&arr[curIndex], &arr[i]);
            curIndex++;
        }
    }

    Swap(&arr[curIndex], &arr[pivot]);
    return curIndex;
}

void QuickSort(int * arr, int left, int right)
{
    if (left < right)
    {
        int P = Partition(arr, left, right);
        QuickSort(arr, left, P - 1);
        QuickSort(arr, P + 1, right);
    }
}

void QuickSort(int * arr, int n)
{
    QuickSort(arr, 0, n - 1);
}

int main()
{
    int arr[] = { 1, 5, 2, 3, 7, 4, 9 };
    int n = sizeof(arr) / sizeof(int);

    PrintArray(arr, n);
    QuickSort(arr, n);
    PrintArray(arr, n);

    return 0;
}

Độ phức tạp:

  • Best case: O(n log n)
  • Worst case: O(n^2)
  • Average: O(n log n)
3 Likes

@minh_vu_03 có mã giả của bài này không? Post lên cho mọi người xem luôn.

1 Like

Mã giả của quick sort mọi người xem ở cái video em mới đổi lại ở trên.

Quick sort quan trọng ở phần phân vùng (partition) nên em giải thích ý tưởng của nó vậy (Cái này không phải ý tưởng của em)

  • Chọn pivot là phần tử cuối cùng trong mảng con (array[left] … array[right) để so sánh.
  • Đặt L là chỉ số các phần tử nhỏ hơn pivot. Khởi tạo cho nó là left.
    for(i <— left to right-1)
    • Nếu array[i] <= phần tử cuối cùng, swap với A[L] (đưa nó qua phía bên trái mảng con). Tăng L lên 1 đơn vị.
    • Như thế thì những phần tử nằm sau chỉ số L (không tính pivot (array[right]) thì sẽ lớn hơn pivot) sẽ lớn hơn pivot. Nghĩa là lúc này ta hoán vị phần tử ngay sau chỉ số L với phần tử cuối cùng (pivot) thì sẽ tách mảng con ra thành 2 phần, phần trước pivot nhỏ hơn hoặc bằng pivot, phần sau pivot lớn hơn pivot.

Trả về chỉ số L để dùng trong việc đệ quy quick sort.

Mọi người có thể dùng cách chọn pivot là array[(left+right)/2] cũng được nhưng dùng mấy cái vòng while như người ta thường làm rắc rối hơn.

2 Likes

interchange sort à anh! e chưa xem nữa

1 Like

Không dùng đệ quy thì sao ta :smiley:

2 Likes

Em tưởng sizeof để đo kích thước của kiểu dữ liệu ? sizeof(array) ở đây là gì thế ạ

1 Like

Trả lời cho câu hỏi trên của @nhatlonggunz

I moved 3 posts to an existing topic: Sizeof(array) ở đây là gì thế ạ?

Bên javascript có luôn array.length :cry: hay mốt viết thêm cho compiler của C++ luôn : :wink:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?