Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là QuickSort, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về QuickSort thông qua các phần sau.
Tóm Tắt
1. Giới thiệu
Giống như Merge Sort, QuickSort là một thuật toán Chia và Chinh phục. Nó chọn một phần tử làm trục và phân vùng mảng đã cho xung quanh trục đã chọn. Có nhiều phiên bản khác nhau của QuickSort chọn pivot theo những cách khác nhau.
Bạn đang đọc: Thuật toán QuickSort – Giới thiệu chi tiết và code ví dụ trên nhiều ngôn ngữ lập trình » https://final-blade.com
- Luôn chọn phần tử đầu tiên làm trục.
- Luôn chọn phần tử cuối cùng làm trụ (được triển khai bên dưới)
- Chọn một phần tử ngẫu nhiên làm trục quay.
- Chọn trung vị làm trục.
Quá trình quan trọng trong quickSort là partition ( ). Mục tiêu của phân vùng là, cho một mảng và một thành phần x của mảng làm trụ, đặt x vào đúng vị trí của nó trong mảng đã sắp xếp và đặt tổng thể những thành phần nhỏ hơn ( nhỏ hơn x ) trước x và đặt toàn bộ những thành phần lớn hơn ( lớn hơn x ) sau x. Tất cả điều này nên được thực thi trong thời hạn tuyến tính .
Mã giả hàm QuickSort đệ quy:
/ * thấp -> Chỉ số bắt đầu, cao -> Chỉ số kết thúc * /
quickSort(arr[], low, high)
{
if (low < high)
{
/ * pi là chỉ mục phân vùng, arr[pi] bây giờ là ở đúng nơi * /
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
Thuật toán phân vùng
Có thể có nhiều cách để thực thi phân vùng, sau mã giả vận dụng giải pháp được đưa ra trong sách CLRS. Logic rất đơn thuần, chúng tôi khởi đầu từ thành phần ngoài cùng bên trái và theo dõi chỉ số của những thành phần nhỏ hơn ( hoặc bằng ) là i. Trong khi duyệt, nếu chúng tôi tìm thấy một thành phần nhỏ hơn, chúng tôi hoán đổi thành phần hiện tại với arr [ i ]. Nếu không, tất cả chúng ta bỏ lỡ thành phần hiện tại .
/ * thấp -> Chỉ số bắt đầu, cao -> Chỉ số kết thúc * /
quickSort(arr[], low, high)
{
if (low < high)
{
/ * pi là chỉ mục phân vùng, arr [pi] bây giờ là ở đúng nơi * /
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
Mã giả cho partition()
/ * Hàm này nhận phần tử cuối cùng làm trục, vị trí
phần tử xoay ở vị trí chính xác của nó trong mảng được sắp xếp và đặt tất cả nhỏ hơn (nhỏ hơn pivot) ở bên trái của trục và tất cả các phần tử lớn hơn ở bên phải
trong tổng số trục * /
partition (arr[], low, high)
{
// pivot (Element to be placed at right position)
pivot = arr[high];
i = (low - 1) // Index of smaller element
for (j = low; j <= high- 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}Hình minh họa partition():
arr [] = {10, 80, 30, 90, 40, 50, 70}
Chỉ số: 0 1 2 3 4 5 6
low = 0, high = 6, pivot = arr [h] = 70
Khởi tạo chỉ mục của phần tử nhỏ hơn, i = -1
Di chuyển các phần tử từ j = low đến high-1
j = 0: Vì arr [j] <= pivot, do i ++ và hoán đổi (arr [i], arr [j])
i = 0
arr [] = {10, 80, 30, 90, 40, 50, 70} // Không thay đổi vì i và j
// là tương tự nhau
j = 1: Vì arr [j]> pivot, không làm gì cả
// Không thay đổi trong i và arr []
j = 2: Vì arr [j] <= pivot, do i ++ và hoán đổi (arr [i], arr [j])
i = 1
arr [] = {10, 30, 80, 90, 40, 50, 70} // Chúng ta hoán đổi 80 và 30
j = 3: Vì arr [j]> pivot, không làm gì cả
// Không thay đổi trong i và arr []
j = 4: Vì arr [j] <= pivot, do i ++ và hoán đổi (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, do i ++ và hoán đổi arr [i] với arr [j]
i = 3
arr [] = {10, 30, 40, 50, 80, 90, 70} // 90 và 50 được hoán đổi
Chúng ta đi ra khỏi vòng lặp vì j bây giờ bằng high-1.
Cuối cùng, chúng ta đặt trục ở 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
Bây giờ 70 đã ở đúng vị trí của nó. Tất cả các phần tử nhỏ hơn
70 ở trước nó và tất cả các phần tử lớn hơn 70 là sau nó.2. Code ví dụ trên nhiều ngôn từ
C++
/* C++ implementation of QuickSort */
#include
using namespace std;
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
} C
/* C implementation QuickSort */
#include
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Java
// Java program for implementation of QuickSort
class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
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 Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i Python
# Python program for implementation of Quicksort Sort
# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr,low,high):
i = ( low-1 ) # index of smaller element
pivot = arr[high] # pivot
for j in range(low, high):
# If current element is smaller than the pivot
if arr[j] < pivot:
# increment index of smaller element
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index
# Function to do Quick sort
def quickSort(arr,low,high):
if low < high:
# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr,low,high)
# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
# Driver code to test above
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]), C#
// C# program for implementation of QuickSort
using System;
class GFG {
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int []arr, int low,
int high)
{
int pivot = arr[high];
// index of smaller element
int i = (low - 1);
for (int j = low; j < high; j++)
{
// If current element is smaller
// than the pivot
if (arr[j] < pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp1 = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp1;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void quickSort(int []arr, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
// A utility function to print array of size n
static void printArray(int []arr, int n)
{
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver program
public static void Main()
{
int []arr = {10, 7, 8, 9, 1, 5};
int n = arr.Length;
quickSort(arr, 0, n-1);
Console.WriteLine("sorted array ");
printArray(arr, n);
}
}
Kết quả
Sorted array:
1 5 7 8 9 103. Độ phức tạp
Thời gian triển khai bởi QuickSort nói chung hoàn toàn có thể được viết như sau .
T(n) = T(k) + T(n-k-1) + θ(n)Hai thuật ngữ tiên phong dành cho hai cuộc gọi đệ quy, thuật ngữ sau cuối dành cho tiến trình phân vùng. k là số thành phần nhỏ hơn pivot .
Thời gian thực thi bởi QuickSort phụ thuộc vào vào mảng nguồn vào và kế hoạch phân vùng. Sau đây là ba trường hợp .
Trường hợp xấu nhất: Trường hợp xấu nhất xảy ra khi quá trình phân vùng luôn chọn phần tử lớn nhất hoặc nhỏ nhất làm pivot. Nếu chúng ta xem xét chiến lược phân vùng ở trên, nơi phần tử cuối cùng luôn được chọn làm trục, trường hợp xấu nhất sẽ xảy ra khi mảng đã được sắp xếp theo thứ tự tăng hoặc giảm. Sau đây là tái diễn cho trường hợp xấu nhất.
T(n) = T(0) + T(n-1) + θ(n)
tương đương với
T(n) = T(n-1) + θ(n)Giải pháp của sự tái diễn ở trên là : θ ( n2 ) .
Trường hợp tốt nhất: Trường hợp tốt nhất xảy ra khi quá trình phân vùng luôn chọn phần tử ở giữa làm trục. Sau đây là tái diễn cho trường hợp tốt nhất.
T(n) = 2T(n/2) + θ(n)Giải pháp của sự tái diễn ở trên là θ ( nLogn ). Nó hoàn toàn có thể được xử lý bằng cách sử dụng trường hợp 2 của Định lý Master .
Trường hợp trung bình:
Để thực thi nghiên cứu và phân tích trường hợp trung bình, tất cả chúng ta cần xem xét tổng thể những hoán vị hoàn toàn có thể có của mảng và thống kê giám sát thời hạn thực thi cho mọi hoán vị, điều này có vẻ như không thuận tiện .
Chúng ta hoàn toàn có thể có sáng tạo độc đáo về trường hợp trung bình bằng cách xem xét trường hợp khi phân hoạch đặt O ( n / 9 ) thành phần trong một tập hợp và O ( 9 n / 10 ) thành phần trong tập hợp khác. Sau đây là tái diễn cho trường hợp này .
T(n) = T(n/9) + T(9n/10) + θ(n)Giải pháp của sự tái diễn trên cũng là O ( nLogn )
Mặc dù độ phức tạp thời hạn trong trường hợp xấu nhất của QuickSort là O ( n2 ), cao hơn nhiều thuật toán sắp xếp khác như Merge Sort và Heap Sort, QuickSort trên thực tiễn nhanh hơn, vì vòng lặp bên trong của nó hoàn toàn có thể được tiến hành hiệu suất cao trên hầu hết những kiến trúc và hầu hết những - tài liệu quốc tế. QuickSort hoàn toàn có thể được triển khai theo nhiều cách khác nhau bằng cách đổi khác sự lựa chọn của trục, do đó trường hợp xấu nhất hiếm khi xảy ra so với một loại tài liệu nhất định. Tuy nhiên, sắp xếp hợp nhất thường được coi là tốt hơn khi tài liệu lớn và được tàng trữ trong bộ nhớ ngoài .
QuickSort có ổn định không?
Việc tiến hành mặc định không không thay đổi. Tuy nhiên, bất kể thuật toán sắp xếp nào cũng hoàn toàn có thể không thay đổi bằng cách coi những chỉ mục là tham số so sánh .
QuickSort có tại chỗ không?
Theo định nghĩa rộng của thuật toán tại chỗ, nó đủ điều kiện kèm theo là thuật toán sắp xếp tại chỗ vì nó chỉ sử dụng thêm khoảng trống để tàng trữ những lệnh gọi hàm đệ quy chứ không phải để thao tác nguồn vào .
QuickSort 3 cách là gì?
Trong thuật toán QuickSort đơn thuần, chúng tôi chọn một thành phần làm pivot, phân vùng mảng xung quanh pivot và tái diễn cho những mảng con ở bên trái và bên phải của pivot .
Hãy xem xét một mảng có nhiều thành phần dư thừa. Ví dụ : { 1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4 }. Nếu 4 được chọn làm trụ trong QuickSort đơn thuần, tất cả chúng ta chỉ sửa một 4 và giải quyết và xử lý đệ quy những lần Open còn lại. Trong QuickSort 3 cách, một mảng arr [ l .. r ] được chia thành 3 phần :
a ) arr [ l .. i ] thành phần nhỏ hơn pivot .
b ) arr [ i + 1 .. j-1 ] thành phần bằng pivot .
c ) arr [ j .. r ] thành phần lớn hơn pivot .
Xem điều này để thực thi .
Làm thế nào để triển khai QuickSort cho Danh sách được Liên kết?
QuickSort trên list link Singly
QuickSort trên list được link kép
Chúng ta có thể triển khai QuickSort lặp lại theo cách thức không?
Có, vui vẻ tìm hiểu thêm Sắp xếp nhanh lặp lại .
Tại sao Sắp xếp Nhanh được ưu tiên hơn Merge Sort để sắp xếp Mảng
Sắp xếp nhanh ở dạng chung là sắp xếp tại chỗ ( tức là không nhu yếu thêm dung tích ) trong khi sắp xếp hợp nhất nhu yếu thêm O ( N ) bộ nhớ, N biểu lộ size mảng hoàn toàn có thể khá đắt. Việc phân chia và vô hiệu khoảng trống thừa được sử dụng để sắp xếp hợp nhất làm tăng thời hạn chạy của thuật toán. So sánh độ phức tạp trung bình, chúng tôi thấy rằng cả hai kiểu sắp xếp đều có độ phức tạp trung bình O ( NlogN ) nhưng những hằng số khác nhau. Đối với mảng, sắp xếp hợp nhất bị mất do sử dụng thêm khoảng trống tàng trữ O ( N ) .
Hầu hết những tiến hành trong thực tiễn của Sắp xếp nhanh đều sử dụng phiên bản ngẫu nhiên. Phiên bản ngẫu nhiên có độ phức tạp thời hạn dự kiến là O ( nLogn ). Trường hợp xấu nhất cũng hoàn toàn có thể xảy ra trong phiên bản ngẫu nhiên, nhưng trường hợp xấu nhất không xảy ra so với một mẫu đơn cử ( như mảng được sắp xếp ) và Sắp xếp nhanh ngẫu nhiên hoạt động giải trí tốt trong trong thực tiễn .
Quick Sort cũng là một thuật toán sắp xếp thân thiện với bộ nhớ cache vì nó có vị trí tham chiếu tốt khi được sử dụng cho những mảng .
Sắp xếp nhanh cũng là đệ quy đuôi, do đó tối ưu hóa cuộc gọi đuôi được thực thi .
Tại sao MergeSort được ưa thích hơn QuickSort cho các Danh sách được Liên kết?
Trong trường hợp list link, trường hợp này khác nhau hầu hết do sự độc lạ trong phân chia bộ nhớ của mảng và list link. Không giống như mảng, những nút list link hoàn toàn có thể không liền kề trong bộ nhớ. Không giống như mảng, trong list link, tất cả chúng ta hoàn toàn có thể chèn những mục vào giữa trong O ( 1 ) khoảng trống thừa và O ( 1 ) thời hạn. Do đó hoạt động giải trí hợp nhất của sắp xếp hợp nhất hoàn toàn có thể được triển khai mà không có thêm dung tích cho list được link .
Trong mảng, tất cả chúng ta hoàn toàn có thể thực thi truy vấn ngẫu nhiên vì những thành phần liên tục trong bộ nhớ. Giả sử tất cả chúng ta có một mảng A số nguyên ( 4 byte ) và đặt địa chỉ của A [ 0 ] là x thì để truy vấn A [ i ], tất cả chúng ta hoàn toàn có thể truy vấn trực tiếp vào bộ nhớ tại ( x + i * 4 ). Không giống như mảng, tất cả chúng ta không hề thực thi truy vấn ngẫu nhiên trong list link. Sắp xếp nhanh nhu yếu rất nhiều loại truy vấn. Trong list link để truy vấn chỉ mục thứ i, tất cả chúng ta phải vận động và di chuyển từng nút từ đầu đến nút thứ i vì tất cả chúng ta không có khối bộ nhớ liên tục. Do đó, ngân sách tăng lên để sắp xếp nhanh gọn. Sắp xếp hợp nhất truy vấn tài liệu một cách tuần tự và nhu yếu truy vấn ngẫu nhiên thấp .
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
Nếu bạn thấy hay và hữu dụng, bạn hoàn toàn có thể tham gia những kênh sau của cafedev để nhận được nhiều hơn nữa :
Chào thân ái và quyết thắng !
Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!
Source: https://final-blade.com
Category: Kiến thức Internet
