Posted by : Nguyễn Văn Tuấn 30 March 2014

Sắp xếp nhanh (Quicksort), còn được gọi là sắp xếp kiểu phân chia (part sort) là một thuật toán sắp xếp phát triển bởi C.A.R. Hoare, dựa trên phép phân chia danh sách được sắp thành hai danh sách con. Khác với sắp xếp trộn, chia danh sách cần sắp xếp a[1..n] thành hai danh sách con có kích thước tương đối bằng nhau nhờ chỉ số đứng giữa danh sách, sắp xếp nhanh chia nó thành hai danh sách bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn được gọi là phần tử chốt. Những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau và thuộc danh sách đứng sau. Cứ tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1.

Thuật toán:
Sau khi phần tử chốt được chọn giải thuật phân chia nên tiến hành như thế nào?

  • Một giải pháp đơn giản nhất cho vấn đề này là duyệt từ đầu đến cuối lần lượt so sánh các phần tử của danh sách với phần tử chốt. Theo cách này, ta phải tiến hành n phép so sánh, ngoài ra còn phải dành n đơn vị bộ nhớ để lưu giữ các giá trị trung gian.
  • Một giải pháp khác được đề nghị là duyệt theo hai đường. Một đường từ đầu danh sách, một đường từ cuối danh sách. Theo cách này, ta tìm phần tử đầu tiên tính từ trái lớn hơn phần tử chốt và phần tử đầu tiên phía phải nhỏ hơn hoặc bằng phần tử chốt rồi đổi chỗ cho nhau. Tiếp tục như vậy cho đến khi hai đường gặp nhau.
  • Để có thể gọi đệ quy ta xét bài toán phân chia một danh sách con của a: a[k_1,k_2] thành hai danh sách.
Tập tin:Sorting quicksort anim.gif
  Code:
#include <iostream>
using namespace std;
void qs(int a[], int left,int right)
{
int i,j, x,y;
i=left; j=right;
x= a[(left+right)/2];
do
    {
    while(a[i]<x && i<right) i++;
    while(a[j]>x && j>left) j--;
    if(i<=j)
        {
        y=a[i];a[i]=a[j];a[j]=y;
        i++;j--;
        }
    }
while (i<=j);
if (left<j) qs(a,left,j);
if (i<right) qs(a,i,right);
}
void quick_sort(int a[], int n)
{
qs(a,0,n-1);
}

int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    quick_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}
 

{ 2 nhận xét... read them below or Comment }

  1. This comment has been removed by the author.

    ReplyDelete
  2. gọi hàm hình như bị sai rồi đúng không ạ ?

    ReplyDelete

- Copyright © Kiến thức tổng quan - Kiến Thức Tổng Quan - Powered by Blogger - Designed by SnowBlack -