THÔNG TIN CHI TIẾT |
[ Sort ] Thuật toán Quick - Sort [ code C++ ]
Cập nhật :14/12/2013
+ Ý tưởng thuật toán
Xét dãy n phần tử a1, a2, a3, .... an.
Bước 1: chọn khóa pivot (chốt): a(Left + Righ)/ 2.
Bước 2: Phân vùng. Những phần tử nhỏ hơn khóa thì nằm bên trái của khóa, những phần tử lớn hơn khóa thì nằm bên phải của khóa và những phần tử bằng khóa có thể nằm bất cứ chỗ nào trên dãy.
Bước 3: sắp xếp cho cả hai phân vùng mới bên trái và bên phải.
+ Mô tả hoạt động của thuật toán Quick Sort:
+ Cài đặt thuật toán [ Code Tubor C++ ]
#include <iostream.h>
#include <conio.h>
#define max 100
// nhap mang
void NhapMang(int A[],int n) {
for(int i=0; i<n; i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
// in mang
void XuatMang(int A[],int n) {
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
// doi cho 2 so
void Swap(int &a,int &b) {
int temp = a;
a = b;
b = temp;
}
// thuat toan quick-sort
void QuickSort(int A[], int Left, int Right) {
int i = Left, j = Right;
int pivot = A[(Left + Right) / 2];
/* partition */
while (i <= j) {
while (A[i] < pivot)
i++;
while (A[j] > pivot)
j--;
if (i <= j) {
Swap(A[i],A[j]);
i++;
j--;
}
}
/* recursion */
if (Left < j)
QuickSort(A, Left, j);
if (i < Right)
QuickSort(A, i, Right);
}
// ham main
void main() {
int A[max], n;
clrscr();
cout<<"Nhap so phan tu:";
cin>>n;
NhapMang(A,n);
cout<<"\nMang vua nhap la:";
XuatMang(A,n);
cout<<"\nSap xep theo Quick Sort:";
QuickSort(A,0,n-1);
XuatMang(A,n);
getch();
}
|