Trong bài này mình sẽ giới thiệu thuật toán Quick Sort (sắp xếp nhanh), đây là thuật toán sắp xếp được xem là nhành nhất trong các thuật toán mình đã giới thiệu trước đây.
Bài viết này được đăng tại
freetuts.net
Bạn đang đọc: Thuật toán sắp xếp nhanh (Quick Sort) – Freetuts
, không được copy dưới mọi hình thức.
Chúng ta sẽ cùng nhau tìm hiểu và khám phá về sắp xếp nhanh là gì ? Cũng như phương pháp nó hoạt động giải trí và tiến hành trong C + + như thế nào .
Ở cuối bài viết mình sẽ có một ví dụ sắp xếp trong mảng. Để những bạn vận dụng được thuật toán trong những bài tập trong thực tiễn .
Tóm Tắt
1. Sắp xếp nhanh (Quick Sort) là gì?
Về cơ bản thuật toán sắp xếp Quick Sort khá giống như Merge Sort. Đây là một thuật toán áp dụng cách thức chia để trị (Divide and Conquer).
Thuật toán sẽ chọn mốt phần tử trong mảng làm điểm đánh dấu (pivot). Khi chọn được điểm đánh dấu, nó sẽ chia mảng thành hai mảng con bằng cách so sánh với pivot đã chọn. Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng pivot và mảng còn lại sẽ lớn hơn hoặc bằng pivot.
Tốc độ sắp xếp của thuật toán tùy thuộc vào việc lựa chọn pivot, có một số ít cách chọn như sau :
- Chọn phần tử đầu tiên của mảng.
- Chọn phần tử cuối cùng của mảng.
- Chọn phần tử có giá trị nằm giữa mảng.
- Chọn Random một phần tử của mảng.
Trên đây là một số ít cách chọn thông dụng, được sử dụng nhiều nhất. Tùy thuộc vào bài toán mà ta chọn pivot cho tương thích .
Các bạn hoàn toàn có thể xem hình minh họa dưới đây để hoàn toàn có thể hiểu hơn .
Khi tất cả chúng ta chọn số 3 làm pivot, thì mảng được chia làm hai phần. Phần bên trái nhỏ hơn hoặc bằng 3, phần bên phải lớn hơn hoặc bằng 3, cả hai phần đều được sắp xếp tằng dần .
Tiếp tục chọn pivot cho mỗi phần. Phần bên trái có pivot là số 1 và phần bên phải có pivot là số 6.
Cứ như vậy tất cả chúng ta sẽ chia phần ra cho đến khi không chia được nữa và sắp xếp theo đúng thứ tự .
2. Thuật toán Quick Sort trong C++
Giải thích thuật toán
Trong phần này chúng ta có hai giai đoạn. Giai đoạn một là giai đoạn phân đoạn mảng (partition()) và giai đoạn hai là giai đoạn sắp xếp (quickSort()).
- Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số cuối cùng của mảng.
- Tạo hai biến là left và right để trỏ tới bên trái và bên phải của danh sách.
- Thực hiện so sánh các phần tử với pivot. Nếu phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
- Sau khi dịch chuyển thực hiện công việc sắp xếp các phần tử trong mảng con mới, trước khi tiếp tục phân đoạn tiếp theo.
Thuật toán Quick Sort trong C++
Ở phần trên mình đã nêu ra những bước viết thuật toán. Để cụ thể hơn mình đã có chú thích rõ ràng, đơn cử trong từng dòng code trong thuật toán dưới đây. Các bạn hãy đọc thật kỹ nhé :
Hàm partition()
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // khai báo phần tử đánh dâu pivot
int left = low; //khai báo biến bên trái
int right = high - 1; //khai báo biến bên phải
while(true){
while(left <= right && arr[left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng
while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng
if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp
swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi.
left++; // Vì left hiện tại đã xét, nên cần tăng
right--; // Vì right hiện tại đã xét, nên cần giảm
}
swap(arr[left], arr[high]);
return left; // Trả về chỉ số sẽ dùng để chia đôi mảng
}
Hàm quicksort()
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* index là chỉ số nơi phần tử này đã đứng đúng vị trí
và đây là phần tử chia mảng làm 2 mảng con trái & phải */
int index = partition(arr, low, high);
// Gọi đệ quy sắp xếp 2 mảng con trái và phải
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
Hàm swap()
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
3. Ví dụ sắp xếp Quick Sort trong mảng
Để minh họa cho hình ảnh ở trên, mình sẽ làm ví dụ vận dụng thuật toán sắp xếp nhanh ( Quick Sort ). Sắp xếp những thành phần trong mảng arr [ ] = { 9, - 3, 5, 2, 6, 8, - 6, 1, 3 } theo thứ tự tăng dần .
Code mẫu:
#include#include using namespace std; //tạo hàm swap để tráo đổi các vị trí void swap(int &a, int &b) { int t = a; a = b; b = t; } // phân đoạn trong mảng int partition (int arr[], int low, int high) { int pivot = arr[high]; // khai báo phần tử đánh dâu pivot int left = low; //khai báo biến bên trái int right = high - 1; //khai báo biến bên phải while(true){ while(left <= right && arr[left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi. left++; // Vì left hiện tại đã xét, nên cần tăng right--; // Vì right hiện tại đã xét, nên cần giảm } swap(arr[left], arr[high]); return left; // Trả về chỉ số sẽ dùng để chia đôi mảng } /* Hàm thực hiện giải thuật quick sort */ void quickSort(int arr[], int low, int high) { if (low < high) { // index là chỉ số nơi phần tử này đã đứng đúng vị trí và đây là phần tử chia mảng làm 2 mảng con trái & phải int index = partition(arr, low, high); // Gọi đệ quy sắp xếp 2 mảng con trái và phải quickSort(arr, low, index - 1); quickSort(arr, index + 1, high); } } /* Hàm xuất mảng */ void printArray(int arr[], int size) { int i; for (i=0; i < size; i++){ cout << arr[i]; cout<<"\t"; } } int main() { int arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3}; int n = sizeof(arr)/sizeof(arr[0]); quickSort(arr, 0, n-1); cout<<"Mảng sau khi được sắp xếp: \n"; printArray(arr, n); cout<<"\n---------------------------------------\n"; cout<<"Chương trình này được đăng tại Freetuts.net"; }
Kết quả:
Như vậy là tất cả chúng ta đã thực thi xong chương trình sắp xếp mảng bằng chiêu thức Quick Sort. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nhanh ( Quick Sort ) trong C + +. Chúc những bạn triển khai thành công xuất sắc ! ! !
Source: https://final-blade.com
Category: Kiến thức Internet
