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