Thuật toán QuickSort trong lập trình C

[playboy]

Mình đã cài đặt chương trình ứng dụng QuickSort,sau khi chạy thì chương trình bị đứng.
Mong mọi người giúp đỡ !!
Đây là code:

#include<stdio.h>#include<conio.h>#define max 100void quicksort(int a[], int n) ;void main()                   {    int a[],n;    printf("\nNhap so phan tu mang:") ;    scanf("%d", &n);    for(int i=0 ; i<n; i++)    {   printf("Nhap so:") ;        scanf("%d", &a[i]) ;        }    printf("\nMang truoc khi sap xep:\t") ;    for(i=0 ; i<n; i++)    {   printf("%d", a[i]) ;    }    printf("\nMang sau khi sap xep:\t");    quicksort(a, n);        getch();}void quicksort(int a[],int n){    int l,r,i,j,t,x,stack[max],top=-1;        stack[++top]=n-1;stack[++top]=0;    do    {       l=stack[top--];r=stack[top--];        i=l;j=r;x=a[(l+r)/2];        do        {            while(a[i]<x) i++;            while(a[j]>x) j--;            if(i>=j){t=a[i];a[i]=a[j];t=a[j];i++;j--;}         }while(i<=j);        if(i<r){stack[++top]=r;stack[++top]=i;}        if(j>l){stack[++top]=j;stack[++top]=l;}      }while(top!=-1);  }

[zkday2686]

chưa xét tới vội thuật toán của bạn như thế nào phần cài đặt đã bị die rùi

while(top!=-1);

lặp chết ở đây là do nguyên nhân chẳng khi nào top == -1 để mà thoát cả

[zkday2686]

Trước hết mình đưa cho bạn hàm QuickSort viết bằng đệ qui.

do các hàm của nó hơi dài nên zkday sẽ chia ra thành từng hàm nhỏ và post lên cho các bạn tiện theo dõi.

 void quickSortRecursive(int a[], int n){  q_sort(a, 0, n - 1);} void q_sort(int a[], int left, int right){    int pivot, iLeft, iRight;    iLeft = left; // lưu lại các giá trị left và right để tính toán    iRight = right;     pivot = a[left]; // lấy vị trí của pivot là left    while (left < right) // trong khi left còn nhỏ hơn right thì làm    {        while ((a[right] >= pivot) && (left < right)) // nếu a[right]>=pivot và left còn nhỏ hơn right thì làm            right--; // giảm right        if (left != right) // nếu left != right thì làm        {            a[left] = a[right]; //gán giá trị cho left            left++; // tăng left lên        }        //tương tự        while ((a[left] <= pivot) && (left < right))            left++;        if (left != right)        {            a[right] = a[left];            right--;        }    }    a[left] = pivot; // gán a[left] lại giá trị pivot      pivot = left;// dùng biến pivot để lưu lại giá trị của left    left = iLeft; // đưa left lại giá trị của iLeft để gọi lại đệ qui    right = iRight; // đưa right lại giá trị của iRight để gọi lại đệ qui      if (left < pivot)        q_sort(a, left, pivot-1);// gọi đệ qui q_sort với nửa mảng đầu của mảng cần sort    if (right > pivot)         q_sort(a, pivot+1, right); // gọi đệ qui q_sort với nửa mảng đầu của mảng cần sort}

[zkday2686]

Còn đây là hàm QuickSort viết không đệ qui.
Lưu ý trong chương trình có dùng lớp stack của STL. chi tiết tham khảo tại MSDN .

 void QuickSortUnRecursive(int a[],int n){    int left,right,iLeft,iRight;    // khai báo 2 đối tượng thuộc lớp stack với mỗi phần tử là kiểu int.    stack<int> stackLeftIndex;    stack<int> stackRightIndex;        stackLeftIndex.push(0); //Push phần tử thứ 0: left vào stackLeft    stackRightIndex.push(n-1); // Push phần tử thứ n-1: right vào stackRight        do     {        left = stackLeftIndex.top(); // lấy phần tử đầu ra        right = stackRightIndex.top(); // lấy phần tử đầu ra                int pivot;// phần tử pivot         iLeft = left;        iRight = right;         pivot = a[left];         while (left < right)        {            while ((a[right] >= pivot) && (left < right))                right--;            if (left != right)            {              a[left] = a[right];              left++;            }            while ((a[left] <= pivot) && (left < right))                left++;            if (left != right)            {              a[right] = a[left];              right--;            }        }        a[left] = pivot;         pivot = left;        left = iLeft;        right = iRight;         //Xóa phần tử trên cùng của Stack ra.        stackRightIndex.pop();        stackLeftIndex.pop();         if (left < pivot)            q_sort(a, left, pivot-1);        if (right > pivot)            q_sort(a, pivot+1, right);         if(left<pivot){// đẩy 2 vị trí tuơng ứng vào Stack để xét sau.            stackLeftIndex.push(left);            stackRightIndex.push(pivot-1);        }        if(right>pivot)        {//Đẩy 2 vị trí tương ứng vào Stack để xét sau            stackLeftIndex.push(pivot+1);            stackLeftIndex.push(right);        }     } while(!stackRightIndex.empty()); // Nếu 1 trong 2 Stack còn khác rỗng thì còn làm}

[zkday2686]

Các hàm còn lại để tạo thành một chương trình hoàn chỉnh

 //khai báo các thư viện cần thiết#include<iostream>#include <stack>  #define max 100 //Khai báo các Prototype của các hàm sử dụng trong chương trình. void QuickSortRecursive(int a[], int n);void QuickSortUnRecursive(int a[],int n);void NhapMang(int a[],int &n);void XuatMang(int a[], int n);void q_sort(int a[], int left, int right); using namespace std; // viết hàm chínhint main()                   {      int a[max],n;      NhapMang(a,n);      cout<<"Mang truoc khi xuat phat";    XuatMang(a,n);    cout<<"\nMang truoc khi sap xep:\t";    XuatMang(a,n);    cout<<endl<<"Mang sau khi sap xep:";            QuickSortUnRecursive(a, n);    //QuickSortRecursive(a,n);    XuatMang(a,n);    return 0;} //viết hàm Nhập mảngvoid NhapMang(int a[],int &n){    cout<<"Nhap so phan tu cua mang:";    cin>>n;     for(int i=0 ; i<n; i++)    {        cout<<"Nhap pha tu a[" << i <<"]";        cin >> a[i];            }}//Viết hàm xuất mảngvoid XuatMang(int a[], int n){    cout<<endl;    for(int i=0 ; i<n; i++)        cout<<"\t"<<a[i] ;}

Lưu ý: dùng các compiler hỗ trợ C++ (tốt nhất nên dùng VSC++).

[playboy]

Cảm ơn Zk đã nhiệt tình giúp đỡ !!