[Q] Hỏi về giải thuật sắp xếp.

[No Mercy]

Em hiện chỉ biết 3 giải thuật sort là: bubble sort, quick sort và heap sort. Anh chị nào làm ơn giải thích kỹ càng dùm em cái quick sort(0 đệ qui) và heap sort. Nếu có VD thì càng tốt. Thanks a lot.

[quangvu]

1. QuickSort không đệ quy thì . . . mới nghe lần đầu .Bạn có biết là Thuật toán QuickSort đã nằm trên giấy gần 2 năm mới được đưa ra chạy thử lần đầu tiên trên Angol-68 (ngôn ngữ hỗ trợ đệ quy đầu tiên).Nếu ai có QuickSort không đệ quy xin Post lên cho quangvu học hỏi với :) !
2. HeapSort (vung đống) : tức trong một dãy ,ta làm cho các Phần Tử nặng chìm xuống còn các phần tử nhẹ nỗi lên.Cứ thế cho đến hết dãy.
*** Bạn có thể tìm mua các sách về thuật toán (Cẩn nang thuật toán ,CTDL + Thiật Toán = Chương trình ,. . .) đễ tham khảo rỏ hơn.
Chúc thành công .

[CrazyBabe]

Hì hì, cái này không đồng ý lắm, tư tưởng của quicksort là xắp xếp trên đoạn chứ không nhất thiết phải thể hiện bằng đệ qui đâu, thể hiện bằng đệ qui thì dễ hiểu hơn mà thôi. Nếu bạn đã chịu khó đọc sách vậy thiết nghĩ phải biết biến thể này, còn nếu hông thì để mình chịu khó ziết lại zậy, nhưng mà lâu lắm không làm mí bài kiểu này, có lẽ wên mất; Nhưng có thể làm thế này: Thay vì bắt buộc gọi đệ qui cho một đoạn, hãy ghi nhớ lại đoạn cần xử lý vào 1 stack rùi kéo ra làm dần dần, cài đặt kiểu này thực tế khá phức tạp và dĩ nhiên không cần thiết. Mà nì, assembly có phải là ngôn ngữ có hỗ trợ đệ quy hông zậy ? Zĩ nhiên là nó cho phép gọi đệ quy và có mặt trước Algol (Hay là Angol ? Algol có phiên bản đầu tiên năm 58, see http://www.levenez.com/lang/history.html)

[quangvu]

Cả assembly sau này mới hổ trợ đệ quy đấy bạn ,theo mình biết hình nhừ thời đó assembly còn không biết hàm là gì nửa chứ đừng nói đến đệ quy .

[khoinguyen2n]

Sắp xếp là một bài toán mang tính thực tế cao. Không có thuật toán nào là tối ưu trong mọi trường hợp thực tế. Người ta thường dựa vào thực tế bài toán, có nghĩa là dựa vào điều kiện thêm vào của bài toán mà chọn lựa thuật toán. Chẳng hạn như nếu yêu cầu bài toán bị hạn hẹp về bộ nhớ thì thực hiện heap sort là hay nhất nhưng việc cài đặt lại hơi phức tạp một chút( đối với những bài toán cần làm nhanh). Ngược lại việc Quick sort thì cài đặt rất dễ dàng nhưng yêu cầu bộ nhớ lại quá lớn, bạn cứ tưởng tượng khi sếp một file có khoảng 1.000.000.000 số nguyên thì sao cần phải chui sâu đệ quy tới 10^3 lần... chết thế thì đủ làm đáp ứng với cái Stack nhỏ bé của bạn.

Việc làm QS không đệ quy không phải là khó nhưng nếu bạn hỏi làm chương trình QS mà chưa học đệ quy thì không cần thiết phải biết đến QS làm gì cứ xếp thô sơ nhất đi bạn ơi. Tuy vậy nếu bạn cần thì cứ gửi MAIL cho tớ sẽ nhận được ví dụ đấy.

VD:
void QS(int l,int r,int &*a)
{
int tg,i,j;
tg=a[(l+r)/2];
i=l;
j=r;
do
{
while(a[i]<tg)i++;
while(a[j]>tg)j--;
if(i<=j)
{
int doi;
doi=a[i];
a[i]=a[j];
a[j]=doi;
i++;j--;
}
}while(i<j);
if(j>l)QS(l,j,a);
if(i<r)QS(i,r,a);
}

Nếu cần về HS thì MAIL cho tớ nhé!!!

[lovely]

HeapSort&QuickSort cái nào chạy nhanh hơn vậy các bạn ?
(khi xắp xếp chuỗi số bé hơn hai phần tử và chuỗi số lớn hơn hai phần tử)

[thuongmemory12]

chào cô bé

fsn;lfjs;lf
sád dghsd['gjusd
gs gsdghsd'gsd
ưgsd

[freshgraduate09]

bài viết tham khảo trên wikipedia mô tả rất chi tiết

http://en.wikipedia.org/wiki/Heapsort

http://en.wikipedia.org/wiki/Bubble_sort

http://en.wikipedia.org/wiki/Quicksort

http://vi.wikipedia.org/wiki/Sắp_xếp_nhanh