Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 18 kết quả

Đề tài: Code Quick Sort không đệ qui viết bằng C??

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

    Question Code Quick Sort không đệ qui viết bằng C??

    bác nào có code qsort ko đệ qui ko cho em với..hĩhix..em kiếm hoài mà ko dc

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

    Code đây:
    PHP Code:
    void QuickSort(int a[],int l,int r)
    {
        
    int i,j,x,tam;
        do
         {
             do
             {
                 
    a[(l+r)/2];
                 
    l;
                 
    r;
                 do
                 {
                     while (
    a[i]<xi++;
                     while (
    a[j]>xj--;
                     if (
    i<=jHoanVi(a[i],a[j]);
                     
    i++;
                     
    j--;
                 } while (
    i<j);
                 
    tam r;
                 
    j;
             } while (
    l<j);
             
    tam;
             
    i;
         } while (
    i<r);


  3. #3
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    không thể được, nếu không đệ qui thì bạn phải dùng thêm 1 stack, tuy nhiên như vậy thì có khác gì đệ qui

    Chỉ có các giải thuật đệ qui đuôi mới có thể khử đệ qui được

    @neverland87: mình không tin là nó đơn giản như thế, cậu tham khảo qsort trong thư viện C chuẩn có trong VC thì biết, nó dùng thêm 1 mảng vai trò là 1 stack

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

    Trích dẫn Nguyên bản được gửi bởi nguyentuan2 Xem bài viết
    không thể được, nếu không đệ qui thì bạn phải dùng thêm 1 stack, tuy nhiên như vậy thì có khác gì đệ qui

    Chỉ có các giải thuật đệ qui đuôi mới có thể khử đệ qui được

    @neverland87: mình không tin là nó đơn giản như thế, cậu tham khảo qsort trong thư viện C chuẩn có trong VC thì biết, nó dùng thêm 1 mảng vai trò là 1 stack
    Đây là phép khử đệ quy quick sort mình đã được học trong trường, mình đã thử nghiệm và thấy nó chạy cũng chính xác lắm.
    Bạn nói đúng ý đầu, trong trường mình cũng được học quick sort bằng cách cài đặt bằng Stack (danh sách liên kết).

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Chà chà mấy huynh giỏi quá chắc em còn phải học nhiều !
    Trong C nó có cái hàm qsort ấy , mình có thể dùng nó được không ?( Tại chưa thử ) Với lại nếu mình có hàm ấy để dùng thì tại sao lại học cài đặt qsort nhỉ ? Có gì bổ ích à ?

  6. #6
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    Mặc định Code Quick Sort không đệ qui viết bằng C??

    bạn thử giải thuật ở trên chưa, thử lại xem

    quicksort không phải là đệ qui đuôi => không khử được đệ qui (được hiểu là không dùng thêm stack riêng)

    chỉ khử được đệ qui nếu dùng thêm 1 biến như stack

    qsort() có sẵn trong C là tốt lắm rồi, ở trong đó nó không đệ qui, nhưng có dùng thêm 1 mảng là stack riêng
    Đã được chỉnh sửa lần cuối bởi nguyentuan2 : 18-04-2007 lúc 04:16 PM.

  7. #7
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    hãy thử với test case của mình xem, chỉ cần lưu file này rồi build

    main.cpp
    C++ Code:
    1. //#include<new.h>
    2. #include<iostream.h>
    3. #include<stdlib.h>
    4. //#include<conio.h>
    5.  
    6. template <class T>
    7. void Swap(T &x, T &y) {
    8.     T tmp = x;
    9.     x = y;
    10.     y = tmp;
    11. }
    12.  
    13. [B]void QuickSort(int a[],int l,int r)[/B]
    14. {
    15.     int i,j,x,tam;
    16.     do
    17.      {
    18.          do
    19.          {
    20.              x = a[(l+r)/2];
    21.              i = l;
    22.              j = r;
    23.              do
    24.              {
    25.                  while (a[i]<x) i++;
    26.                  while (a[j]>x) j--;
    27.                  if (i<=j) Swap(a[i],a[j]);
    28.                  i++;
    29.                  j--;
    30.              } while (i<j);
    31.              tam = r;
    32.              r = j;
    33.          } while (l<j);
    34.          r = tam;
    35.          l = i;
    36.      } while (i<r);
    37. }
    38.  
    39. template <class T>
    40. void PrintArray(T arr[], int num) {
    41.     cout<<"--- begin PrintArray ---"<<endl;
    42.     int i;
    43.     for (i=0; i<num; ++i) {
    44.         cout<<arr[i]<<" ";
    45.     }
    46.     cout<<endl;
    47. }
    48.  
    49. int CompareInt (const void * a, const void * b)
    50. {
    51.   return ( *(int*)a - *(int*)b );
    52. }
    53.  
    54. void main() {
    55.     const int ARR_NUM = 10;
    56.     int arr[ARR_NUM];
    57.    
    58.     int i;
    59.     for (i=0; i<ARR_NUM; ++i) {
    60.         arr[i] = ((i+1)*1001 % 97);
    61.     }
    62.    
    63.     PrintArray(arr, ARR_NUM);
    64.  
    65.     [B]QuickSort(arr, 0, ARR_NUM - 1);[/B]
    66.  
    67.     PrintArray(arr, ARR_NUM);
    68.  
    69.     [B]qsort(arr, ARR_NUM, sizeof arr[0], CompareInt);[/B]
    70.  
    71.     PrintArray(arr, ARR_NUM);
    72.     //getch();
    73. }

    output
    Code:
    --- begin PrintArray ---
    31 62 93 27 58 89 23 54 85 19
    --- begin PrintArray ---
    19 23 27 31 54 89 58 93 85 62
    --- begin PrintArray ---
    19 23 27 31 54 58 62 85 89 93
    Đã được chỉnh sửa lần cuối bởi nguyentuan2 : 18-04-2007 lúc 04:32 PM.

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

    Ừh, đoạn code của mình chạy sai thiệt rồi ta ơi. Theo mình nghĩ thì từ nay hễ có cái sắp xếp mảng nào cứ lấy qsort(..) được xây dựng sẵn ra mà xài, khỏi mất công cài đặt

  9. #9
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Tui xin ké vô 1 chút:

    Đệ qui đuôi thì có thể đưa về dạng vòng lặp (khử đệ qui)

    Còn tui không chắc lắm về: không phải là đệ qui đuôi => không khử được đệ qui (được hiểu là không dùng thêm stack riêng)

    Về quicksort, nếu tui không lầm thì:

    Chia mảng ra làm 2 với điểm chia là xM
    Hoán vị các phần tử để nửa trước hL chứa các phần tử nhỏ hơn hay bằng xM, nửa sau hR chứa các phần tử lớn hơn xM
    Rồi đệ qui trên 2 nửa hL và hR

    Giả sử mình chia được 3 mức:
    - mức 1: điểm chia là xM
    - mức 2: các điểm chia là xL và xR
    - mức 3: các điểm chia là xLL, xLR, xRL, xRR

    Code:
    |----------------xM----------------|: hL và hR (2 mảng con)
    |-------xL-------xM-------xR-------|: hLL và hLR; hRL và hRR (4 mảng con)
    |--xLL--xL--xLR--xM--xRL--xR--xRR--|: hLLL và hLLR; hLRL và hLRR; hRLL và hRLR; hRRL và hRRR (8 mảng con)
    Nếu mình dò lần khi quicksort tạo các điểm chia thì thứ tự sẽ là:
    xM trước nhứt, rồi đến XL, XLL, xLR, xR, xRL, xRR

    Nếu mình tạo 1 cây nhị phân:

    Code:
              xM              
          /          \      
         xL           xR
        /  \         /   \
    xLL    xLR    xRL    xRR
    thì thứ tự duyệt xM, XL, XLL, xLR, xR, xRL, xRR sẽ tương ứng với duyệt theo chiều sâu

    Tui nghĩ mình có thể không xài đệ qui nếu duyệt theo chiều rộng như sau:
    - tìm điểm chia xM
    - hoán vị các phần tử để nửa trước hL chứa các phần tử nhỏ hơn hay bằng xM, nửa sau hR chứa các phần tử lớn hơn xM
    - tìm điểm chia xR và xL
    - hoán vị các phần tử để nửa trước hRL (xM -> xR) chứa các phần tử nhỏ hơn hay bằng xR, nửa sau hRR (xR -> cuối) chứa các phần tử lớn hơn xR
    - hoán vị các phần tử để nửa trước hLL (đầu -> xL) chứa các phần tử nhỏ hơn hay bằng xL, nửa sau hLR (xL -> xM) chứa các phần tử lớn hơn xL
    Code:
    |-------xL-------xM-------xR--------|
    |--------|--------|--------|--------|
       hLL      hLR      hRL      hRR
    - tìm điểm chia xRR, xRL, xLR và xLL
    - hoán vị các phần tử để nửa trước hRRL (xR -> xRR) chứa các phần tử nhỏ hơn hay bằng xRR, nửa sau hRRR (xRR -> cuối) chứa các phần tử lớn hơn xRR
    - hoán vị các phần tử để nửa trước hRLL (xM -> xRL) chứa các phần tử nhỏ hơn hay bằng xRL, nửa sau hRLR (xRL -> xR) chứa các phần tử lớn hơn xRL
    - hoán vị các phần tử để nửa trước hLRL (xL -> xLR) chứa các phần tử nhỏ hơn hay bằng xLR, nửa sau hLRR (xLR -> xM) chứa các phần tử lớn hơn xLR
    - hoán vị các phần tử để nửa trước hLLL (đầu -> xLL) chứa các phần tử nhỏ hơn hay bằng xLL, nửa sau hLLR (xLL -> xL) chứa các phần tử lớn hơn xLL
    Code:
    |-------xLL-------xL-------xLR--------xM-------xRL--------xR---------xRR------|
    | hLLL      hLLR      hLRL      hLRR      hRLL      hRLR       hRRL      hRRR |
    => thứ tự tạo các điểm chia là: xM, xR, xL, xRR, xRL, xLR, và xLL

    (có gì sai sót mong được góp ý, xin cám ơn)

    -thân
    Đã được chỉnh sửa lần cuối bởi bete : 24-04-2007 lúc 11:52 AM.

  10. #10
    Ngày gia nhập
    04 2007
    Bài viết
    3


    đại khái là dùng LIFO mới giải đc

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

  1. Thuật toán C++ Ưu nhược điểm các kiểu sort Interchange sort, Selection sort, Insertion sort, Sharke sort , Quick sort, Heap sort
    Gửi bởi duythanhnguyen trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 7
    Bài viết cuối: 23-09-2013, 01:16 AM
  2. Thuật toán quick sort viết trong C/C++?
    Gửi bởi nhoccon.uit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 30-10-2012, 07:44 PM
  3. quick sort viết bằng C++ không chạy
    Gửi bởi cttd trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 13-04-2011, 12:51 AM
  4. Thuật toán Quick Sort viết bằng C++, có lỗi làm sao sửa?
    Gửi bởi nikeboi89 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: 09-04-2009, 09:36 PM
  5. Code sắp xếp Quick Sort viết trên C++. Chạy = VC++ thì crash, TC thì sai?
    Gửi bởi camping29 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 11
    Bài viết cuối: 24-12-2008, 09:44 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