Bước 1: Chọn khóa pivot = a(left+right)/2
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
5 comments
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
ReplyBạn Trần Chính liên hệ mr Thanh để được trợ giúp nhé :D
Replybạn ơi bạn có code chưa cho mình xin với
Replylàm sao để liên hệ vs mrThanh vậy admin
Replybạn ơi bạn có code chưa cho mình xin với
Reply