Đã bao giờ bạn nghe về thuật toán Sắp xếp nhanh (Quick sort) chưa? Đây là một giải thuật sắp xếp mạnh mẽ, được sử dụng rộng rãi trong ngôn ngữ lập trình C++. Hôm nay, chúng ta sẽ cùng tìm hiểu và ứng dụng Quick sort một cách dễ dàng và đơn giản. Bài viết này sẽ giúp bạn nắm vững Quick sort để áp dụng vào công việc một cách hiệu quả nhất.
Ý nghĩa và công đoạn của Quick sort
Quick sort – Sắp xếp nhanh chóng
Quick sort là một giải thuật sắp xếp mạnh mẽ. Nó hoạt động bằng cách chọn một phần tử làm điểm chốt, sau đó chia mảng thành hai phần: một phần nhỏ hơn hoặc bằng và một phần lớn hơn điểm chốt. Điều này tạo ra một quy trình lặp, giúp sắp xếp mảng một cách hiệu quả.
Quick sort – Thuật toán phân đoạn và chinh phục
Vậy làm sao để chọn phần tử làm điểm chốt? Dưới đây là một số cách bạn có thể thử:
- 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ử ở giữa mảng.
- Chọn ngẫu nhiên một phần tử của mảng.
Bí quyết sắp xếp nhanh chóng
Mô tả thuật toán Quick sort như sau:
- Chọn điểm đánh dấu cho mảng, ví dụ như số cuối cùng của mảng.
- Tạo hai biến trái và phải để trỏ tới bên trái và bên phải của danh sách.
- So sánh các phần tử với điểm đánh dấu. Nếu nhỏ hơn thì dịch chuyển sang bên trái và ngược lại.
- Sau khi dịch chuyển, 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.
Chớ bỏ lỡ cơ hội sở hữu ốp lưng siêu xịn cho điện thoại với giá chỉ từ 10k. bfstc.edu.vn cung cấp những sản phẩm chất lượng, đảm bảo sự bảo vệ tốt nhất cho điện thoại của bạn.
Phác thảo thuật toán Quick sort
Để kích hoạt Quick sort, ta cần tích hợp thêm những hàm sau:
- Hàm Phân đoạn:
- Hàm hoán đổi:
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
Để làm ví dụ cho hình ảnh trên, chúng ta sẽ á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.
Mã nguồn ví dụ:
#include <iostream>
using namespace std;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int left = low;
int right = high - 1;
while (true) {
while (left <= right && arr[left] < pivot) {
left++;
}
while (right >= left && arr[right] > pivot) {
right--;
}
if (left >= right) {
break;
}
swap(&arr[left], &arr[right]);
left++;
right--;
}
swap(&arr[left], &arr[high]);
return left;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
}
int main() {
int arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Danh sach ban dau: ";
printArray(arr, n);
quickSort(arr, 0, n - 1);
cout << "nDanh sach sau khi sap xep: ";
printArray(arr, n);
return 0;
}
Nhập và Xuất:
Hi vọng bài viết này đã giúp bạn hiểu rõ về Quick sort và cách áp dụng vào công việc của mình. Hãy thử áp dụng thuật toán này trong các dự án của bạn và chia sẻ kết quả với chúng tôi!