Có thể nói Quick Sort là thuật toán sắp xếp được coi là nhanh nhất hiện nay bên cạnh MegaSort, Sắp xếp nổi bọt,..... . Thuật toán Quick Sort được phát triển bởi phát triển bởi C.A.R.
| Sắp xếp nhanh | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
 Quicksort thực hiện trên danh sách các số. Đường nằm ngang là các giá trị làm phần tử chốt. | ||||||||||
| Thông tin chung | ||||||||||
|
Thuật toán Quick Sort là thuật toán sắp xếp tối ưu vì thế nó được sử dụng để giải các bài toán cần sử dụng đến thuật toán sắp xếp. Trong Pascal, Quicksort cần phải cài đặt thuật toán nhưng trong C++ chúng ta không cần nhờ hàm sort trong thư viện algorithm.
>> Xem thêm: Sort trong C++
1. Hàm Sort trong C++
Nguồn: http://ntucoder.net+ Cú pháp: sort(a+k, a+n+k , kt);
Sắp xếp mảng là một thao tác thường được dùng rất nhiều trong các thuật toán như tìm kiếm nhị phân, tìm cặp gần nhất, tìm các giá trị lớn nhất, nhỏ nhất (ví dụ như các bài NHGA, CASO, LUTA, ...). Thuật toán đơn giản nhất để sắp xếp một mảng n phần tử là:for(i=1; i<n; i++)
for(j=i+1; j<=n; j++)
if(a[i]> a[j]) swap(a[i], a[j]);
Thuật toán sắp xếp trên, cũng như một số thuật toán sắp xếp khác như SelectionSort, InsertionSort, BubbleSort có độ phức tạp là O(n2) - khoảng n(n+1)/2 bước thực hiện. Nếu n= 1.000 thì số bước thực hiện là 500.000, máy tính có thể thực hiện nhanh. Tuy nhiên, nếu n = 100.000 thì số bước thực hiện là 5.000.000.000, máy tính không thể thực hiện được trong khoảng vài giây.
Tuy nhiên có những thuật toán khác giúp cho việc sắp xếp có độ phức tạp O(nlog2n) như QuickSort, HeapSort, MergeSort. Nếu n = 100.000 thì số bước sắp xếp khoảng 1.700.000, máy tính hoàn toàn có thể thực hiện dưới 1 giây.
Trong C++, người ta cung cấp sẵn một hàm sort trong thư viện algorithm để sắp xếp mảng với độ phức tạp O(nlog2n). Sử dụng như sau:
#include<algorithm>
#include<functional> // std::greater
using namespace std;
long long a[100005];
long long n;
int main()
{
sort(a, a+n); // sắp xếp mảng a tăng dần từ phần tử 0 đến phần tử n-1
sort(a+1, a+1+n); // sắp xếp mảng a tăng dần từ phần tử 1 đến phần tử n
sort(a, a+n, greater<int>()); // sắp xếp mảng a giảm dần từ p.tử 0 đến p.tử n-1
}
Nếu cần sắp một mảng các phần tử có kiểu struct thì cần viết thêm hàm so sánh. Ví dụ sắp xếp mảng PhanSo:
#include<algorithm>
using namespace std;
struct PhanSo
{
long long ts;
long long ms;
};
PhanSo a[100005];
long long n;
bool SoSanh(const PhanSo &x, const PhanSo &y)
{
return (double)x.ts/x.ms < (double)y.ts/y.ms;
}
int main()
{
sort(a, a+n, SoSanh); // sắp xếp mảng phân số từ phần tử 0 đến phần tử n-1
sort(a+1, a+1+n, SoSanh); // sắp xếp mảng phân số từ phần tử 1 đến phần tử n
}
Biến bool sosanh dùng để tìm điều kiện đổi các phần tử của mảng a.
2. Một số bài toán sử dụng Quicksort
1. STABLE (Sắp xếp ổn định)
1.1. Đề bài:
Xem pdf: STABLE (pass: toank27)
1.2. Thuật toán
Ở bài toán này ta nhận thấy phải sử dụng đến hàm sort. Ở đây ta không đổi chỗ các phần tử của mảng a mà ta lại đổi chỗ mảng chỉ số của các phần tử bằng cách tạo ra mảng mới là cs. Điều kiện so sánh trong trường hợp này là nếu như a[i]<a[j] hoặc a[i]==a[j] và i
1.3. Code thuật toán:
Thuật toán được code bằng ngôn ngữ C++
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
long long a[100020],n,i,cs[100020];
bool kt(long long i,long long j){
return (a[i]<a[j])||((a[i]==a[j])&&(i<j));
}
int main(){
freopen("STABLE.INP","r",stdin);
freopen("STABLE.OUT","w",stdout);
cin>>n;
for (i=1;i<=n;i++){cin>>a[i];cs[i]=i;}
sort(cs+1,cs+n+1,kt);
for (i=1;i<=n;i++) cout<<cs[i]<<" ";
}
Tải file chương trình:
2. SZERO (Đoạn 0)
2.1. Đề bài:
Không có nhận xét nào:
Đăng nhận xét