Thuật toán QuickSort

Trong hướng dẫn này, bạn sẽ học cách hoạt động của quicksort. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của quicksort trong C, C ++ Python và Java.

Quicksort là một thuật toán dựa trên cách tiếp cận chia và chinh phục, trong đó mảng được chia thành các mảng con và các mảng con này được gọi đệ quy để sắp xếp các phần tử.

QuickSort hoạt động như thế nào?

1. Một phần tử tổng hợp được chọn từ mảng. Bạn có thể chọn bất kỳ phần tử nào từ mảng làm phần tử tổng hợp.
   Ở đây, chúng tôi đã sử dụng ngoài cùng bên phải (tức là phần tử cuối cùng) của mảng làm phần tử trụ. Chọn một phần tử xoay
2. Các phần tử nhỏ hơn phần tử pivot được đặt ở bên trái và các phần tử lớn hơn phần tử pivot được đặt ở bên phải. Đặt tất cả các phần tử nhỏ hơn ở bên trái và lớn hơn ở bên phải của phần tử pivot
   Việc sắp xếp trên được thực hiện theo các bước sau.
   1. Một con trỏ được cố định tại phần tử pivot. Phần tử pivot được so sánh với các phần tử bắt đầu từ chỉ mục đầu tiên. Nếu đạt đến phần tử lớn hơn phần tử tổng hợp, con trỏ thứ hai được đặt cho phần tử đó.
   2. Bây giờ, phần tử pivot được so sánh với các phần tử khác (con trỏ thứ ba). Nếu đạt đến phần tử nhỏ hơn phần tử tổng hợp, phần tử nhỏ hơn sẽ được hoán đổi với phần tử lớn hơn được tìm thấy trước đó. So sánh phần tử trục với các phần tử khác
   3. Quá trình tiếp tục cho đến khi đạt được phần tử cuối cùng thứ hai.
      Cuối cùng, phần tử pivot được hoán đổi với con trỏ thứ hai. Hoán đổi phần tử pivot với con trỏ thứ hai
   4. Bây giờ các phần con bên trái và bên phải của phần tử xoay này được thực hiện để xử lý thêm trong các bước bên dưới.
3. Các phần tử tổng hợp lại được chọn cho các phần phụ bên trái và bên phải riêng biệt. Trong các phần phụ này, các phần tử trục được đặt ở đúng vị trí của chúng. Sau đó, bước 2 được lặp lại. Chọn phần tử xoay trong mỗi nửa và đặt vào đúng vị trí bằng cách sử dụng đệ quy
4. Các phần con lại được chia thành các phần con nhỏ hơn cho đến khi mỗi phần con được tạo thành từ một phần tử duy nhất.
5. Tại thời điểm này, mảng đã được sắp xếp.

Quicksort sử dụng đệ quy để sắp xếp các phần con.

Trên cơ sở của cách tiếp cận Chia và chinh phục, thuật toán nhanh chóng có thể được giải thích là:

• Chia
  Mảng được chia thành các phần con lấy pivot làm điểm phân vùng. Các phần tử nhỏ hơn trục được đặt ở bên trái của trục và các phần tử lớn hơn trục được đặt ở bên phải.
• Chinh phục
  Các phần con bên trái và bên phải lại được phân vùng bằng cách chọn các phần tử xoay cho chúng. Điều này có thể đạt được bằng cách chuyển đệ quy các phần con vào thuật toán.
• Kết hợp
  Bước này không đóng một vai trò quan trọng trong nhanh. Mảng đã được sắp xếp ở cuối bước chinh phục.

Bạn có thể hiểu hoạt động của quicksort với sự trợ giúp của các hình minh họa bên dưới.

Sắp xếp các phần tử ở bên trái của trục bằng cách sử dụng đệ quy Sắp xếp các phần tử ở bên phải của trục bằng cách sử dụng đệ quy

Thuật toán sắp xếp nhanh

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- phân vùng (mảng, bên tráiIndex, bên phảiIndex) quickSort (mảng, bên tráiIndex, pivotIndex) nhanh chóng ) đặt rightmostIndex dưới dạng pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 thành rightmostIndex if element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) return storeIndex 1

Ví dụ về Python, Java và C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Độ phức tạp Quicksort

Thời gian phức tạp

• Độ phức tạp của trường hợp xấu nhất (Big-O) : Nó xảy ra khi phần tử xoay được chọn là phần tử lớn nhất hoặc nhỏ nhất. Điều kiện này dẫn đến trường hợp phần tử pivot nằm ở cuối cực của mảng đã sắp xếp. Một mảng con luôn trống và một mảng con khác chứa các phần tử. Do đó, quicksort chỉ được gọi trên mảng con này. Tuy nhiên, thuật toán sắp xếp nhanh có hiệu suất tốt hơn cho các trục phân tán.O(n2)
n - 1

• Độ phức tạp của trường hợp tốt nhất (Big-omega) : O(n*log n)
  Nó xảy ra khi phần tử xoay luôn là phần tử ở giữa hoặc gần với phần tử giữa.
• Độ phức tạp trường hợp trung bình (Big-theta) : O(n*log n)
  Xảy ra khi các điều kiện trên không xảy ra.

Không gian phức tạp

Không gian phức tạp cho quicksort là O(log n).

Ứng dụng Quicksort

Quicksort được triển khai khi

• ngôn ngữ lập trình tốt cho đệ quy
• vấn đề thời gian phức tạp
• vấn đề phức tạp không gian