Sắp xếp quicksort khử đệ quy trong lập trình C

[neverland87]

Đọc trong tài liệu cấu trúc dữ liệu của KHTN, mình thấy người ta mô phỏng Quick Sort bằng stack, mọi người tham khảo nhé
-----------------------------------------------------------
Xây dựng thủ tục sắp xếp bằng Quicksort không dùng đệ quy.
Thuật toán: QuickSort(int a[], int n)
b1: Khởi tạo Stack Rỗng
b2: Dãy đang xét từ 0 đến n-1. Cất 2 L=0 và R=n-1 vào Stack
b3: Lấy (L, R) từ Stack
b4: Phân hoạch dãy A[L] .. A[R] thành 2 dãy A[L]..A[j] và A[i]..A[R]
b5: Nếu (i<R) cất (i,R) vào Stack
b6: R = j
b7: Nếu (L<R) Quay lại b4 để phân hoạch dãy A[L] ..A[j] ngược lại chuyển sang b8
b8: Nếu Stack <> rỗng quay lại b3 phân hoạch các dãy bên phải ngược lại kết thúc.

void QuickSort(int a[], int n){StackType stack;int L, R, i, j;int x;stack = NULL; Push(0,n-1, Stack);do{        P = Pop(Stack); L = P->L; R = P->R;         do         {     /*Phan hoach aL..aR */                    i = L,                     j = R;                     x = a[(L+R)/2];                    do                     {                            while (a[i] < x) i++;                            while (a[j] > x) j--;                             if (i <= j)                              {                                           HoanVi(&a[i], &a[j]);                                       i++;                                        j--;                             }                  } while (i <= j);                if ( i < R) Push(i, R, Stack);                R = j;     } while (L<R);} while (Stack != NULL);}

[doicanhden]

Cài đặt thuật toán trên C++ với một ít trợ giúp từ STL. Hôm nay tôi thích đi đào mộ, đào code lên.

#include <stack>void quickSort(int a[], int n){    std::stack< std::pair<int, int> > stack;     stack.push(std::make_pair(0, n - 1));    do    {        std::pair<int, int> top = stack.top();        stack.pop();        int L = top.first;        int R = top.second;        do        {            /*Phan hoach aL..aR */            int i = L;            int j = R;            int x = a[(L + R) / 2];            do            {                while (a[i] < x) i++;                while (a[j] > x) j--;                if (i <= j)                    std::swap(a[i++], a[j--]);            }while (i <= j);             if ( i < R)                stack.push(std::make_pair(i, R));            R = j;        }while (L < R);     }while (!stack.empty());}