Chuyển đến nội dung chính

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

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:


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

BÀI ĐỌC NHIỀU

[Java] Hướng dẫn lập trình Java với NetBean [Clip hướng dẫn]

[Đồ họa trong C\C++] Sử dụng các hàm đồ họa thông dụng trong C\C++ [C\C++]

[ C++ ] Tính đa hình, phương thức ảo, lớp trừu tượng trong C++ [Lập trình hướng đối tượng với C++]

[ Sort ] Thuật toán Heap-Sort [Code C++]

[Algorithm] Thuật toán Đệ quy và một số bài toán Đệ quy cơ bản

[Assembly] Tính tổng 2 số nguyên nhỏ hơn 10 [Lập trình hợp ngữ]

[Assembly] Hướng dẫn sử dụng Emu8086 [Lập trình hợp ngữ]

Bài tập +đáp án Lý thuyết đồ họa máy tính

[Thuật toán đồ thị / code C++] Thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị G

[ C++ ] Kế thừa trong C++ [Lập trình hướng đối tượng với C++]