Code C/C++: Thuật toán sắp xếp nhanh (QuickSort)

Ý tưởng thuật toán: xét dãy n phần tử a_0, a_{1, …,}a_n-1
Bước 1: Chọn khóa pivot = a(left+right)/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:

#include<math.h>

#include<iostream>

#include<conio.h>

#define max 100

using namespace std;

//Nhập mảng

void NhapMang(int A[],int n){

for(int i=0; i<n;  i++) {

cout<<"nhap Phan tu thu A["<<i<<"] =";

cin>>A[i];

}

}

//Xuất mảng

void XuatMang(int A[],int n){

cout<<endl;

for(int i=0; i<n;  i++)

cout<<A[i]<<"\t";

} 

//Hoán vị 2 phần tử

void Swap(int &a,int &b){

int temp = a;

a = b;

b =  temp;

}

//Sắp xếp các phần tử

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);

}

//Chương trình chính

int main(){

int A[max],n;

cout<<"Nhap so phan tu:";

cin>>n;

NhapMang(A,n);

cout<<"\nMang vua nhap la:";

XuatMang(A,n);

cout<<"\nSap xep theo QuickSort:";

QuickSort(A,0,n-1);

XuatMang(A,n);

getch();

return 0;

}

Kết quả chạy chương trình:

Từ khóa: Sắp xếp, thuật toán, chèn, insert, insertion sort, sắp xếp chèn, giải thuật, cấu trúc dữ liệu và giải thuật, sắp xếp nhanh, quick sort

Related Posts