Thuật toán Quick Sort – Java Example

Quay trở lại với series thuật toán của VNTALKING. Hôm nay, mình sẽ giới thiệu tới các bạn một thuật toán rất phổ biến, đó là thuật toán sắp xếp nhanh (Quick Sort).

Thuật toán QuickSort là một trong những thuật toán sắp xếp được sử dụng nhiều nhất, đặc biệt là để sắp xếp các lists/arrays có nhiều phần tử.

Thuật toán sắp xếp quick sort là một thuật toán chia để trị (Divide and Conquer algorithm). Nghĩa là, mảng ban đầu được chia thành 2 mảng, mỗi mảng được sắp xếp riêng lẻ. Sau đó, đầu ra đã sắp xếp được hợp nhất để tạo mảng đã sắp xếp cuối cùng.

Độ phức tạp của thuật toán là O(n log n). Do đó, Quick Sort phù hợp để sắp xếp các mảng có dữ liệu lớn.

Nói một cách chính xác hơn, thuật toán Quicksort thực hiện nhiều lần chia mảng bằng cách so sánh với phần tử đánh dấu (gọi là pivot). Khi kết thúc đệ quy, mảng đã được sắp xếp. Điều khiến cho thuật toán thực hiện nhanh đó chính là “sắp xếp tại chỗ”. Nghĩa là, việc sắp xếp được thực hiện ngay trong mảng mà không cần tạo mảng mới.

Ý tưởng thuật toán Quicksort

Ý tưởng cơ bản của thuật toán Quicksort có thể được mô tả theo các bước sau:

Nếu Array chỉ có một phần tử hoặc Array rỗng thì coi như đây là mảng đã được sắp xếp. Kết thúc thuật toán.

Nếu Array chưa nhiều hơn một phần tử thì:

• Chọn một phần tử làm pivot
• Thực hiện chia Array thành 2 phần: phần thứ nhất gồm những phần tử có thứ tự thấp hơn pivot, phần còn lại là những phần tử có thứ tự cao hơn pivot.
• Sắp xếp cả hai phần riêng biệt bằng cách lặp lại bước 1 và 2.

Hình dưới đây minh họa cách thuật toán quicksort phân chia Array thành 2 phần:

Kỹ thuật chọn phần tử làm pivot ảnh hưởng khá nhiều tới tốc độ sắp xếp. Việc chọn phần tử pivot thường sẽ là do bạn quyết định. Dưới đây là một số cách để chọn pivot thường dùng:

• Chọn phần tử đầu tiên hoặc cuối cùng của Array làm pivot
• Chọn phần tử ngẫu nhiên
• Chọn phần tử ở giữa mảng (được sử dụng trong code minh họa bài viết này)

Minh họa thuật toán sắp xếp Quick Sort bằng Java

Dưới đây là mã nguồn Java để minh họa cho thuật toán sắp xếp quick sort. Các bạn có thể dễ dàng chuyển sang C#, C++… nếu cần. Tham khảo thêm: Viết Quicksort bằng C++

public class QuickSortExample {
    public static void main(String[] args) {
        // Đây là mảng chưa được sắp xếp.
        Integer[] array = new Integer[] {12,13,24,10,3,6,90,70};

        // Gọi hàm sắp xếp mảng
        quickSort(array, 0, array.length - 1);

        // Hiển thị kết quả sau khi thực hiện sắp xếp
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(Integer[] arr, int low, int high) {
        //Kiểm tra xem mảng có null hay rỗng không
        if (arr == null || arr.length == 0) {
            return;
        }

        if (low >= high) {
            return;
        }

        //Chọn phần tử ở giữa mảng làm pivot
        int middle = low + (high - low) / 2;
        int pivot = arr[middle];

        // Tiến hành phân chia mảng
        int i = low, j = high;
        while (i <= j) {
            //Kiểm tra cho đến khi tất cả giá trị trong mảng bên trái nhỏ hơn pivot
            while (arr[i] < pivot) {
                i++;
            }
            // Kiểm tra cho đến khi tất cả các giá trị trong mảng bên phải lớn hơn pivot            
            while (arr[j] > pivot) {
                j--;
            }
            //Tiến hành so sánh giá trị từ cả hai phía xem có cần đổi chỗ hay không
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        //Thực hiện đệ quy để sắp xếp các mảng con
        if (low < j) {
            quickSort(arr, low, j);
        }
        if (high > i) {
            quickSort(arr, i, high);
        }
    }

    public static void swap(Integer array[], int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}

//Output: [3, 6, 10, 12, 13, 24, 70, 90]

Trên đây là toàn bộ code thực hiện sắp xếp một mảng. Trong Java, bạn có thể sử dụng ngay hàm Arrays.sort() để sắp xếp mà không cần viết đoạn code dài như trên. Bản chất hàm Arrays.sort() cũng sử dụng thuật toán quicksort. Không tin, bạn cứ thử mà xem.