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

Post a Comment

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

Tags

Android ASP Assembly Bidvertiser Biểu diễn thuật toán Bubble-Sort Bài giảng lập trình C và Cpp Bài viết hay Bản đồ tư duy C C Plus Plus C sharp CSS Cây (tree) Cây quyết định Công nghệ điện toán đám mây Cơ sở dữ liệu Danh sách liên kết (list) Datamining Exceptions Giáo trình Giải hệ phương trình tuyến tính Google App Engine Heap-Sort HPH HTML Học lập trình Học lập trình C và CPP qua ví dụ Insert-sort iOS Java Java GUI JavaScript Kiếm tiền online Kỹ thuật lập trình Kỹ thuật đồ họa máy tính Lý thuyết Cơ sở dữ liệu Lý thuyết đồ thị 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 mobile Lập trình mạng Merge-Sort MS Access Mẹo tìm kiếm trên Google Ngôn ngữ lập trình Nhúng code Assembly trong C\C++ Những lỗi thường gặp khi lập trình Oracle Pascal people-group PHP Queue (hàng đợi) Quick-Sort Seclection-sort SQL Stack (ngăn xếp) Thiết kế Web Thuật toán Thuật toán di truyền 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 Thuật toán Đệ quy Toán rời rạc Trí tuệ nhân tạo Tìm kiếm nhị phân Tìm kiếm tuần tự (Line search) Tính định thức của ma trận 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ụ VB XML Xử lý ma trận (mảng 2 chiều) Xử lý mảng 1 chiều Xử lý ngoại lệ Đồ họa Độ phức tạp của thuật toán Ứng dụng cơ sở dữ liệu
 
Copyright © . Lập trình máy tính - Posts · Comments
Theme Template by BTDesigner · Powered by Blogger