Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Sắp xếp quicksort khử đệ quy trong lập trình C

  1. #1
    Ngày gia nhập
    01 2007
    Bài viết
    412

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

    Đọ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:
    1. void QuickSort(int a[], int n)
    2. {
    3. StackType stack;
    4. int L, R, i, j;
    5. int x;
    6. stack = NULL; Push(0,n-1, Stack);
    7. do
    8. {
    9.         P = Pop(Stack); L = P->L; R = P->R;
    10.         do
    11.         {     /*Phan hoach aL..aR */
    12.                     i = L,
    13.                     j = R;
    14.                     x = a[(L+R)/2];
    15.                     do
    16.                     {
    17.                             while (a[i] < x) i++;
    18.                             while (a[j] > x) j--;
    19.                              if (i <= j)
    20.                              {    
    21.                                        HoanVi(&a[i], &a[j]);
    22.                                        i++;
    23.                                        j--;
    24.                              }
    25.                   } while (i <= j);
    26.                 if ( i < R) Push(i, R, Stack);
    27.                 R = j;
    28.      } while (L<R);
    29. } while (Stack != NULL);
    30. }

  2. #2
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    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:
    1. #include <stack>
    2. void quickSort(int a[], int n)
    3. {
    4.     std::stack< std::pair<int, int> > stack;
    5.  
    6.     stack.push(std::make_pair(0, n - 1));
    7.     do
    8.     {
    9.         std::pair<int, int> top = stack.top();
    10.         stack.pop();
    11.         int L = top.first;
    12.         int R = top.second;
    13.         do
    14.         {
    15.             /*Phan hoach aL..aR */
    16.             int i = L;
    17.             int j = R;
    18.             int x = a[(L + R) / 2];
    19.             do
    20.             {
    21.                 while (a[i] < x) i++;
    22.                 while (a[j] > x) j--;
    23.                 if (i <= j)
    24.                     std::swap(a[i++], a[j--]);
    25.             }while (i <= j);
    26.  
    27.             if ( i < R)
    28.                 stack.push(std::make_pair(i, R));
    29.             R = j;
    30.         }while (L < R);
    31.  
    32.     }while (!stack.empty());
    33. }
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

Các đề tài tương tự

  1. Đếm sô phép gán và so sánh trong QuickSort
    Gửi bởi thuan199 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 5
    Bài viết cuối: 20-02-2012, 07:11 PM
  2. Lập trình C Dãy số 9 2 4 10 12 1 5 3 8 11, nhờ ae giải bằng Sắp xếp nhanh, QuickSort trong C
    Gửi bởi phongchuoi trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 20-04-2011, 11:47 PM
  3. Rắc rối trong cài đặt Quicksort
    Gửi bởi huyson trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 24-03-2010, 11:05 PM
  4. Thuật toán QuickSort trong lập trình C
    Gửi bởi playboy trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 15-10-2008, 10:41 PM
  5. Trả lời: 6
    Bài viết cuối: 04-05-2008, 08:04 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn