Code tham khảo và ý tưởng Giải thuật sắp xếp nhanh Quick Sort
Ý tưởng của giải thuật này là chọn một phần tử đóng vai trò là khoá chốt (còn gọi là điểm mốc), các phần tử nhỏ hơn khoá chốt sẽ phải chuyển lên đứng trước khoá chốt. Các phần tử lớn hơn khoá chốt thì phải chuyển xuống đứng sau khoá chốt. Các bước cụ thể như sau:
• Chọn một phần tử (bất kì) làm khoá chốt.
• Đi từ đầu mảng đến cuối mảng, tìm phần tử đầu tiên lớn hơn khoá chốt, đánh dấu nó là phần tử thứ i.
• Đi từ cuối mảng lên đầu mảng, tìm phần tử đầu tiên nhỏ hơn khoá chốt, đánh dấu nó là phần tử thứ j.
• Nếu i<j, đổi chỗ phần tử thứ i và thứ j.
• Sau đó, đi tiếp theo hai chiều, và đổi chỗ, nếu có, cho đến khi i=j.
• Đổi chỗ phần tử thứ i (cũng là j vào thời điểm này) với phần tử chốt. Khi đó, phần tử chốt là đúng vị trí của nó trong mảng sắp xếp.
• Lặp lại giải thuật trên với hai đoạn của mảng: đoạn trước chốt và đoạn sau chốt.
• Quá trình sẽ dừng khi mỗi đoạn chỉ còn hai phần tử.
Code :
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void QuickSort(float a[],int l,int r)
{
int i,j;
int x;
i=l;
j=r;
x=a[(l+r)/2];
do
{
while (a[i]<x)i++;
while(a[j]>x)j--;
if(j<=j)
{
if(i<j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
i++;
j--;
}
}
while(i<j);
if(l<j)QuickSort(a,l,j);
if(i<r)QuickSort(a,i,r);
}
void input(float a[],int n)
{
int i;
for (i = 1; i <= n; i++)
{
cout<<"a["<<i<<"]= ";
cin>>a[i];
}
}
void output(float a[],int n)
{
int i;
for (i = 1; i <= n; i++)
cout<<a[i]<<" ";
}
void main()
{
cout<<"Nhap n : ";cin>>n;
if(n>0)
{
cout<<"Day ban dau: ";
input(a,n);
cout<<endl;
cout<<"\nSap xep theo PP QuickSort:"<<endl;
cout<<endl;
QuickSort(a,1,n);
output(a,n);
}
getch();
}
0 Response to "Code tham khảo và ý tưởng Giải thuật sắp xếp nhanh Quick Sort"
Đăng nhận xét