Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán sắp xếp nhanh (Quick Sort)
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.
Chúng ta sẽ cùng nhau tìm hiểu về sắp xếp nhanh là gì? Cũng như cách thức nó hoạt động và triển khai 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. Để các bạn áp dụng được thuật toán trong các bài tập thực 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).
Bài viết này được đăng tại [free tuts .net]
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ố 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ố 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 phù hợp.
Các bạn có thể xem hình minh họa dưới đây để có thể hiểu hơn.
Khi 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 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 các bước viết thuật toán. Để chi tiết hơn mình đã có chú thích rõ ràng, cụ thể 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ụ áp dụng thuật toán sắp xếp nhanh (Quick Sort). Sắp xếp các phần tử trong mảng arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3} theo thứ tự tăng dần.
Code mẫu:
#include<stdio.h>
#include<iostream>
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à chúng ta đã thực hiện xong chương trình sắp xếp mảng bằng phương pháp 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 các bạn thực hiện thành công!!!
