Code tham khảo và ý tưởng Giải thuật sắp xếp nhanh Quick Sort
• 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