[ Sort ] Thuật toán Quick - Sort [ code C++ ]

in , , , , , , , /

Thuật toán sắp xếp nhanh - Quick Sort 


 + Ý 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:

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();
}
//======================================


--------------------------------------------
Xem thêm các thuật toán khác: 
1. Thuật toán tìm kiếm tuần tự
2. Thuật toán tìm kiếm nhị phân
3. Thuật toán sắp xếp đổi trực tiếp - Select sort
4. Thuật toán sắp xếp nổi bọt - Bubble sort
5. Thuật toán sắp xếp chèn trực tiếp - Insert sort
6. Thuật toán sắp xếp nhanh - Quick sort
7. Thuật toán sắp xếp hòa trộn - Merge sort

8. Thuật toán sắp xếp vun đống - Heap sort

------------------------
Tự học lập trình C++:

------------------------

Một số tài liệu và khoá học bổ ích dành cho bạn: 

# Giáo Trình: Kỹ Thuật Lập Trình C/C++ Căn Bản Và Nâng Cao [Click để xem]

# Khoá học online: Học lập trình C/C++ TỪ A - Z [Click để xem]


Bài 1: Chương trình đầu tay