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ử a0, a1, …,an-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 3Sắ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
Previous
« Prev Post

5 comments

March 10, 2015 at 12:30 PM

bác ơi bài này làm trên turbo c và nhúng assembly vào dc không bác. bác có code thì cho em xin với. em đang làm bài tập lớn mà khó quá không làm dc. cảm ơn bác trước nha

Reply
avatar
March 12, 2015 at 4:21 PM

Bạn Trần Chính liên hệ mr Thanh để được trợ giúp nhé :D

Reply
avatar
October 13, 2016 at 10:15 AM

bạn ơi bạn có code chưa cho mình xin với

Reply
avatar
October 13, 2016 at 10:15 AM

làm sao để liên hệ vs mrThanh vậy admin

Reply
avatar
October 13, 2016 at 10:18 AM

bạn ơi bạn có code chưa cho mình xin với

Reply
avatar