Thuật toán Quick Sort là gì?

Thuật toán Quick Sort là một thuật toán sắp xếp, còn được gọi là sắp xếp kiểu phân chia (Part Sort). Là một thuật toán hiệu quả dựa trên việc phân chia mảng tài liệu thành các nhóm thành phần nhỏ hơn.

Bạn Đang Xem: Thuật toán Quick Sort là gì?

Phân loại: Giải thuật sắp xếp Phức tạp thời kì: Trung bình O(n log n) Xấu nhất: O(n2) Phức tạp tài liệu: Khác nhau tùy vào cách hiện thực Tối ưu: Thỉnh thoảng

Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng phương pháp so sánh từng thành phần của mảng với một thành phần được gọi là thành phần chốt. Một mảng gồm có các thành phần nhỏ hơn hoặc bằng thành phần chốt và một mảng gồm các thành phần to ra nhiều thêm thành phần chốt.

Xem Thêm : Vật phẩm phong thủy là gì? Ý nghĩa của vật phẩm phong thủy trong đời sống

Quá trình phân chia này diễn ra cho đến lúc độ dài của không ít mảng con đều bằng 1. Với phương pháp đệ quy ta có thể sắp xếp nhanh các mảng con sau khoản thời gian kết thúc lớp học ta được một mảng đã sắp xếp hoàn chỉnh.

Kỹ thuật chọn thành phần chốt

Kỹ thuật chọn thành phần chốt ảnh hưởng tác động khá nhiều đến khả năng rơi vào các vòng lặp vô hạn khi đối chiếu với các trường hợp đặc biệt quan trọng. Tốt nhất chọn thành phần chốt nằm ở trung vị của list. Khi đó, sau log2(n) lần chia ta đạt được kích thưởng mảng con bằng 1.

Trong tương lai là một số phương pháp chọn thành phần chốt:

• Chọn thành phần đứng đầu hoặc đứng cuối làm thành phần chốt.
• Chọn thành phần đứng giữa list làm thành phần chốt.
• Chọn thành phần trung vị trong ba thành phần đứng đầu, đứng giữa và đứng cuối làm thành phần chốt.
• Chọn thành phần tình cờ làm thành phần chốt. Tuy nhiên cách này rất dễ dẫn đến khả năng rơi vào các trường hợp đặc biệt quan trọng.

Ý tưởng thuật toán Quick Sort

1. Chọn thành phần chốt.
2. Khai báo 2 biến con trỏ để trỏ để duyệt 2 phía của thành phần chốt.
3. Biến bên trái trỏ đến từng thành phần mảng con bên trái của thành phần chốt.
4. Biến bên phải trỏ đến từng thành phần mảng con bên phải của thành phần chốt.
5. Khi biến bên trái nhỏ hơn thành phần chốt thì vận chuyển sang phải.
6. Khi biến bên phải nhỏ hơn thành phần chốt thì vận chuyển sang trái.
7. Nếu không xẩy ra trưởng hợp 5 và 6 thì tráo đổi giá trị 2 biến trái và phải.
8. Nếu trái to ra nhiều thêm phải thì đây là giá trị chốt mới.

Giải thuật

Trong tương lai là lớp học mô phỏng thuật toán đệ quy viết trên tiếng nói lập trình java:

Xem Thêm : Người có căn tu là gì? Nhận biết gương mặt người có căn tu

public class QuickSort { public static void main(String[] args) { int[] x = {6, 2, 3, 4, 5, 9, 1}; printArray(x); int left = 0; int right = x.length – 1; quickSort(x, left, right); printArray(x); } public static void quickSort(int[] arr, int left, int right) { if (arr == null || arr.length == 0) return; if (left >= right) return; int middle = left + (right – left) / 2; int pivot = arr[middle]; int i = left, j = right; while (i <= j) { while (arr[i] < pivot) { i++; } while (arr[j] > pivot) { j-; } if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j-; } } if (left < j) quickSort(arr, left, j); if (right > i) quickSort(arr, i, right); } public static void printArray(int[] arr) { for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + ” “); } System.out.println(); } }

Lượt dịch từ:

• https://en.wikipedia.org/wiki/Quicksort
• http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html

Có thể bạn muốn xem thêm:

• Các thuật toán sắp xếp lập trình viên phải ghi nhận
• Thuật toán trong lập trình – Vài nét tản mạn
• Tầm quan trọng của giải thuật trong việc xử lý các bài toán

Xem thêm Software Developers hot nhất trên TopDev

TopDev via viblo