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

[darlong]

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

[neverland87]

Code đây:

void QuickSort(int a[],int l,int r)
{
    int i,j,x,tam;
    do
     {
         do
         {
             x = a[(l+r)/2];
             i = l;
             j = r;
             do
             {
                 while (a[i]<x) i++;
                 while (a[j]>x) j--;
                 if (i<=j) HoanVi(a[i],a[j]);
                 i++;
                 j--;
             } while (i<j);
             tam = r;
             r = j;
         } while (l<j);
         r = tam;
         l = i;
     } while (i<r);
} 

[nguyentuan2]

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

[neverland87]

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).

[kidkid]

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 à ?

[nguyentuan2]

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

[nguyentuan2]

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

//#include<new.h>#include<iostream.h>#include<stdlib.h>//#include<conio.h> template <class T>void Swap(T &x, T &y) {    T tmp = x;    x = y;    y = tmp;} [B]void QuickSort(int a[],int l,int r)[/B]{     int i,j,x,tam;     do      {          do          {              x = a[(l+r)/2];              i = l;              j = r;              do              {                  while (a[i]<x) i++;                  while (a[j]>x) j--;                  if (i<=j) Swap(a[i],a[j]);                  i++;                  j--;              } while (i<j);              tam = r;              r = j;          } while (l<j);          r = tam;          l = i;      } while (i<r); }  template <class T>void PrintArray(T arr[], int num) {    cout<<"--- begin PrintArray ---"<<endl;    int i;    for (i=0; i<num; ++i) {        cout<<arr[i]<<" ";    }    cout<<endl;} int CompareInt (const void * a, const void * b){  return ( *(int*)a - *(int*)b );} void main() {    const int ARR_NUM = 10;    int arr[ARR_NUM];        int i;    for (i=0; i<ARR_NUM; ++i) {        arr[i] = ((i+1)*1001 % 97);    }        PrintArray(arr, ARR_NUM);     [B]QuickSort(arr, 0, ARR_NUM - 1);[/B]     PrintArray(arr, ARR_NUM);     [B]qsort(arr, ARR_NUM, sizeof arr[0], CompareInt);[/B]     PrintArray(arr, ARR_NUM);    //getch();}

output

--- 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

[neverland87]

Ừ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

[bete]

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

|----------------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:

          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

|-------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

|-------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

[www]

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