Đọ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.
C Code:
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); }
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.
C++ Code:
#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()); }
Kết bạn với tôi <3
Skype: giautm
Facebook: https://fb.com/giautm.duongntt
Email: giau.tmg@gmail.com