Post

Quick sort - sắp xếp nhanh

Posted Updated
By TungDaDev 8 min read

1. Giới thiệu

Sắp xếp nhanh (Quick Sort) còn có một tên gọi khác là sắp xếp phân chia (Part Sort) dựa trên ý tưởng thuật toán. Nó được phát minh lần đầu bởi C.A.Hoare vào năm 1960.

Có lẽ đây là thuật toán được nghiên cứu và sử dụng rộng rãi nhất trong các thuật toán sắp xếp. Quick sort cũng là thuật toán đệ quy. Ngược với Mergesort gọi đệ quy rồi mới xử lý, Quick sort xử lý xong mới gọi đệ quy.

Ý tưởng của thuật toán này dựa trên phương pháp chia để trị, nghĩa là chia dãy cần sắp xếp thành 2 phần, sau đó thực hiện việc sắp xếp cho mỗi phần độc lập nhau. Để làm việc này thì ta cần phải làm các bước sau:

  • Chọn ngẫu nhiên một phần tử nào đó của dãy làm phần tử khóa (pivot). Kĩ thuật chọn phần tử khóa rất quan trọng vì nếu không may bạn có thể bị rơi vào vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử ở vị trí trung tâm của dãy. Khi đó sau log2(n) lần phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất khó. Có các cách chọn phần tử khóa như sau:
    • Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử khóa.
    • Chọn phần tử đứng giữa danh sách làm phần tử khóa.
    • Chọn phần tử trung gian trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử khóa.
    • Chọn phần tử ngẫu nhiên làm phần tử khóa. (Cách này có thể dẫn đến khả năng rơi vào các trường hợp đặc biệt)
  • Xếp các phần tử nhỏ hơn phần tử chốt ở phía trước phần tử khóa.
  • Xếp các phần tử lớn hơn phần tử chốt ở phía sau phần tử khóa Để có được sự phân loại này thì ở 2 bước trên, các phần tử sẽ được so sánh với khóa và hoán đổi vị trí cho nhau hoặc cho khóa nếu nó lớn hơn khóa mà lại nằm trước khóa, hoặc nhỏ hơn mà lại nằm sau khóa. Áp dụng kĩ thuật như trên cho mỗi đoạn đó và tiếp tục làm vậy cho đến khi mỗi đoạn chỉ còn 2 phần tử. Khi đó toàn bộ dãy đã được sắp xếp

Quick sort là một thuật toán dễ cài đặt, hiệu quả trong hầu hết các trường hợp và tiêu tốn ít tài nguyên hơn so với các thuật toán khác.

Độ phức tạp trung bình của giải thuật là O(NlogN).

2. Minh hoạ quá trình chia tách mảng

Có thể có nhiều cách để thực hiện phân vùng. Logic rất đơn giản, ta bắt đầu từ phần tử ngoài cùng bên trái và theo dõi chỉ số của các phần tử nhỏ hơn (hoặc bằng) là i. Trong khi duyệt, nếu ta tìm thấy một phần tử nhỏ hơn, ta hoán đổi phần tử hiện tại với arr[i]. Nếu không, bỏ qua phần tử hiện tại.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

quickSort(arr[], low, high) {
    if (low < high) {
        
        // pi  là chỉ mục, arr [pi] là vị trí của chốt       
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // trước pi
        quickSort(arr, pi + 1, high); // sau pi
    }
}

1.	arr[] = {10, 80, 30, 90, 40, 50, 70}
Các chỉ mục tương ứng:  0   1   2   3   4   5   6 

2.	low = 0, high =  6, pivot = arr[h] = 70
Khởi tạo chỉ mục ban đầu, i = -1

3.	Di chuyển các phần tử từ j = low đến high-1
j = 0 : vì arr[j] <= pivot,  i++ và swap(arr[i], arr[j])
i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} --- Không thay đổi vì i và j tương tự nhau

4.	j = 1 : vì arr[j] > pivot --- không làm gì cả - không có thay đổi ở i và arr[]

5.	j = 2 : vì arr[j] <= pivot,  i++ và swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} --- hoán đổi 80 và 30 

6.	j = 3 : vì arr[j] > pivot, không làm gì cả - không có thay đổi ở i và arr[]

7.	j = 4 : vì arr[j] <= pivot,  i++ và swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} --- 80 và 40 được hoán đổi.
j = 5 : vì arr[j] <= pivot,  i++ và swap arr[i] với arr[j] 
i = 3 
arr[] = {10, 30, 40, 50, 80, 90, 70} --- 90 và 50 được hoán đổi.

8.	Đến đấy sẽ thoát ra khỏi vòng lặp vì j = high-1.
Cuối cùng, ta đặt chốt ở vị trí chính xác bằng cách hoán đổi arr[i+1] và arr[high] (hoặc pivot) 
arr[] = {10, 30, 40, 50, 70, 90, 80} --- 80 và 70 được hoán đổi 

9.	Bây giờ, 70 đã ở đúng vị trí của nó. Các phần tử nhỏ hơn 70 đều ở trước và các phần tử lớn hơn đều ở sau nó.

3. Code demo

Từ quá trình minh hoạ bên trên, ta hãy thử chuyển chúng sang code xem như thế nào. Có vẻ vất vả!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

public class QuickSort {

    // Hàm nhận phần tử cuối cùng làm chốt,
    // đặt các phần tử nhỏ hơn chốt ở trước
    // và lớn hơn ở sau nó
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); // index of smaller element
        for (int j = low; j < high; j++) {

            // Nếu phần tử hiện tại nhỏ hơn chốt
            if (arr[j] < pivot) {
                i++;

                // swap arr[i] và arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] và arr[high] (hoặc pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    // arr[] --> Mảng cần được sắp xếp,
    // low --> chỉ mục bắt đầu,
    // high --> chỉ mục kết thúc
    void sort(int arr[], int low, int high) {
        if (low < high) {

            // pi là chỉ mục của chốt, arr[pi] vị trí của chốt
            int pi = partition(arr, low, high);

            // Sắp xếp đệ quy các phần tử
            // trướcphân vùng và sau phân vùng
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }

    // In các phần tử của mảng
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {10, 80, 30, 90, 40, 50, 70};
        int n = arr.length;

        System.out.println("Mảng ban đầu:");
        printArray(arr);

        QuickSort ob = new QuickSort();
        ob.sort(arr, 0, n - 1);

        System.out.println("Mảng sau khi sắp xếp:");
        printArray(arr);
    }
}

Nhược điểm của Quick Sort là không hiệu quả trên những dãy đã được sắp xếp sẵn. Khi đó ta phải mất N lần gọi đệ quy và mỗi lần chỉ loại được 1 phần tử. Thời gian thực hiện thuật toán trong trường hợp xấu nhất này là O(n2).

Trong trường hợp tốt nhất, mỗi lần phân chia sẽ được 2 nửa dãy bằng nhau, khi đó thời gian thực hiện thuật toán là: T(N) = 2T(N/2) + N Khi đó T(N) xấp xỉ bằng NlogN.

Như vậy Quick sort là thuật toán hiệu quả trong đa số các trường hợp. Nhưng đối với các trường hợp việc sắp xếp chỉ phải thực hiện ít và lượng dữ liệu lớn thì nên sử dụng một số thuật toán khác.

Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!

Happy coding! 😎 👍🏻 🚀 🔥

Information Technology, Software Development
Java Data-Structures & Algorithms
This post is licensed under CC BY 4.0 by the author.