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

Thuật toán sắp xếp nhanh - Quick Sort [ Xem clip hướng dẫn và demo]

+ Ý 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();
}
//======================================
[Tải Code Chương trình tại đây (Lưu ý: Sau 5s, click Bỏ qua quảng cáo - Skin Ad)]

0 nhận xét:

Cảm ơn bạn đã quan tâm tới bài viết này!

Tags

Android ASP Assembly Bài giảng lập trình C và Cpp Bài viết hay Biểu diễn thuật toán Bubble-Sort C C sharp C++ Cây (tree) Cây quyết định CDSL phân tán Công nghệ điện toán đám mây Công nghệ lập trình Cơ sở dữ liệu CSS Danh ngôn lập trình Danh sách liên kết (list) Datamining Đệ quy Đồ họa Độ phức tạp của thuật toán Giải hệ phương trình tuyến tính Góc học tập Góc suy ngẫm Google App Engine Heap-Sort Hệ quản trị CSDL Học lập trình Học lập trình C và CPP qua ví dụ học lập trình Java HTML Insert-sort iOS Java Java Căn bản java core Java GUI JavaScript Kiếm tiền online Kỹ thuật đồ họa máy tính Kỹ thuật lập trình Lập trình căn bản Lập trình Cơ sở dữ liệu Lập trình hướng đối tượng Lập trình hướng đối tượng với Java Lập trình mạng Lập trình mobile lập trình viên Lập trình viên độc lập Luyện thi IC3 Lý thuyết Cơ sở dữ liệu Lý thuyết đồ thị Mạng máy tính Mẹo tìm kiếm trên Google Merge-Sort MS Access Ngôn ngữ lập trình Nhúng code Assembly trong C\C++ Oracle phần cứng máy tính PHP Queue (hàng đợi) Quick-Sort Seclection-sort SQL Stack (ngăn xếp) Thiết kế Web Thủ thuật máy tính Thuật toán Thuật toán di truyền Thuật toán Đệ quy Thuật toán K-Mean Thuật toán khác Thuật toán leo đồi Thuật toán ma trận Thuật toán Sắp Xếp -Sort Thuật toán Tìm kiếm - Search Tiện ích máy tính Tìm kiếm nhị phân Tìm kiếm tuần tự (Line search) Tin học văn phòng Tin tức công nghệ Tính định thức của ma trận Toán rời rạc Trí tuệ nhân tạo Tự học lập trình Android Tự học lập trình C và CPP Tự học lập trình java qua các ví dụ Ứng dụng cơ sở dữ liệu VB XML Xử lý ma trận (mảng 2 chiều) Xử lý mảng 1 chiều Xử lý ngoại lệ