Sắp xếp mảng kiểu nào nhanh nhất? [Archive]

general2000vn

29-02-2004, 19:52

ke_tui_nha

29-02-2004, 21:55

Cái cách bạn hỏi là sắp xếp theo kiểu quick sort, ngoài ra còn có kiểu heap sort.

Thuật toán quick sort
Ý tưởng của thuật toán này là chia dãy cần sắp xếp thành 3 dãy con.
Dãy con bên trái gồm các ptử nhỏ hơn x (x là phần tử bất kỳ trong dãy)
Dãy con ở giữa gồm các ptử bằng x
Dãy con bên phải gồm các ptử lớn hơn x
Sau đó ta lại tiếp tục chia các dãy con bên trái & bên phải thành 3 dãy con và cứ thế cho đến khi dãy con cần chia chỉ có 1 ptử

Giả sử cần sắp xếp dãy sau:
0 1 2 3 4 5 6
[1 3 9 5 8 7 2]
Ta chọn ptử để so sánh là ptử ở chính giữa (0 + 6)/2 = ptử thứ 3
x = 5
Sau khi phân họach, ta có dãy như sau:

[1 3 2] [5] [8 7 9]

Ta lại tiếp tục phân họach dãy con bên trái:
0 1 2
[1 3 2]
Chọn ptử để so sánh là ptử (0 + 2)/2 = thứ 1
y = 3
Sau khi phân họach, ta có dãy
[1 2 3]

Tương tự, cho dãy [8 7 9], ta có dãy [7 8 9]
Sau khi quá trình phân hoạch kết thúc, ta có dãy [1 2 3 5 7 8 9] đã được sắp xếp.

Sau đây là mã C để sắp xếp kiểu quick sort
// a[]: dãy cần sắp xếp
// l : chỉ số bắt đầu của dãy con cần phân họach trong dãy cần sắp xếp
// r : chỉ số kết thúc của dãy con
void quicksort(int a[], int l, int r)
{
int i, j, x;
i = r; j = l;
x = a[(i + j)/2]; //ptử so sánh
while(i <= j) {
while(a[i] < x) i++;
while(a[j] > y) j--;
if(i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
if(j > l) quicksort(a, l, j); //phân họach dãy bên trái
if(r > i) quicksort(a, i, r); //phân họach dãy bên phải
}

mù_chữ_Java

29-02-2004, 23:56

Một cách khác nữa là merge sort.
Cách làm: chia đôi dãy ra, sort ở mỗi dãy, rồi gộp (merge) lại. Khi chia đôi, mỗi bên sễ có một dãy ngắn bằng một nửa dãy nguyên gốc. Cứ liên tục gọi chia đôi từng dãy như vậy sẽ đến khi dãy có độ dài bằng 1 ( dãy độ dài bằng 1 coi như đã được sort).
Ví dụ cho dãy
[ 3 2 4 6 9 5 1 7]
chia hai, bạn có được:
[ 3 2 4 6] [9 5 1 7]
Trước khi merge, mỗi nửa sẽ được chia hai tiếp:
[[3 2] [4 6]] [[9 5] [1 7]]
Trước khi merge mỗi nửa nhỏ bên trong, ta lại chia hai tiếp:
[[[3] [2]] [[4] [6]]] [[[9] [5]] [[1] [7]]]

Bây giờ mỗi nửa nhỏ trong cùng có một phần tử mà thôi, ta có thể bắt đầu merge. Nhớ rằng khi merge, ta sẽ sắp xếp hai nửa nhỏ của một dãy sao cho phần tử có giá trị nhỏ nằm trước:
[[2 3] [4 6]] [[5 9] [1 7]]

Xong rồi ghép tiếp:
[ 2 3 4 6] [1 5 7 9]

Ghép tiếp phần cuối cùng:
[1 2 3 4 5 6 7 9]

Xin lỗi tui không rành về Pascal nên không cho ví dụ Pascal được. Có C code mà thôi:

// method to call merge sort:
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}

// helper method to include two bound
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;

if (right > left)
{
// first devide the array in two parts
mid = (right + left) / 2;

// then recursively sort each half til right == left
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

// merge them back, now that two half are sorted:
merge(numbers, temp, left, mid+1, right);
}
}

// merge two array:
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

// walk through each, put the smallest left-over in either left side
// or right side to the temp array in each iteration.
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

// then put the left over in the two array, if any.
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

// copy the array back to its original array:
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}

general2000vn

04-03-2004, 10:29

Cám ơn các bạn đã giúp mình. Mình thấy các cách trên đây, nếu như sắp xấp mảng (ví dụ 9 phần tử) thì đều có số lần so sánh bằng nhau (36 lần) trong trường hợp xấu nhất (tức là mảng phải sắp xấp hoàn toàn.vVậy thì cũng nhanh bằng cách sủi bọt thôi à

Vậy có cách nào nhanh hơn không?

mù_chữ_Java

04-03-2004, 11:28

Đúng là nếu mảng chỉ có 9 phần tử thì không nên xài quick sort hay merge sort làm chi, vì không nhanh thêm được bao nhiêu. Chỉ nên xài mí cái này khi bạn có chừng vài chục ngàn phần tử trở lên.
Nếu bạn so sánh tốc độ của Bubble sort là
O(n) = n^2 (n lũy thừa 2) của Bubble sort
và
O(n) = n.log_2(n) (log bậc 2 )của merge sort và quick sort
thì biết liền. Thế n nhỏ vào thì hai đứa này xấp xỉ nhau, nhưng n lớn thì bubble sort thua đứt bóng ...

readln

04-03-2004, 15:04

Thuat toan sap xep mang nhanh nhat cho den bay gio toi moi chi duoc biet do la Qick_sort
con no nhu the nao Ban co the xem thi du mau trong "examples" cua thu muc nay ma
Cach viet cua ho cung hay lam day

general2000vn

05-03-2004, 00:32

Mình vẫn chưa hiểu lắm. Tại sao các bạn lại tính ra được cái công thức đó. Có thể giảng giải rõ hơn cho mình được không?

bete

05-03-2004, 00:50

Nếu tui 0 lầm:

1) buble sort: chạy n đợt con:
Đợt con 1: so sánh n-1 cặp phần tử
Đợt con 2: so sánh n-2 cặp phần tử
Đợt con 3: so sánh n-3 cặp phần tử
............
Đợt con N-2: so sánh 2 cặp phần tử
Đợt con N-1: so sánh 1 cặp phần tử

==> tổng cộng: so sánh ((n-1) + (n-2) + (n-3) + ... + 2 + 1) lần => khỏang n^2/2 => O(n^2)

2) quick sort: chạy log2(n) đợt con (vì mỗi đợt => chiều dài mảng con bị chia 2)

Đợt con 1: so sánh khỏang n cặp phần tử
Đợt con 2: so sánh khỏang n cặp phần tử
.......
Đợt con log2(n): so sánh khỏang n cặp phần tử

==> tổng cộng: so sánh n*log2(n) lần => O(n*log2(n))

3) merge sort: tương tự quick sort

luong_dien_nhan

05-03-2004, 01:46

bubble và insertion sort thực ra hoàn toàn khác nhau về ý tưởng cũng như giải thuật , bạn phải suy nghĩ thật kỹ lại nha,
giải thuật sắp xếp nhanh nhất thực ra là quick sort, tuy nhiên trong một vài trường hợp(sắp xếp một danh sách đã có thứ tự ) thì quick sort trở thành slow sort,ngoài ra heap sort cũng rất tốt!
có 9 giải thuật sắp xếp , nhưng không thể khẳng định tuyệt đối là giải thuật nào tốt nhất , bạn phải biết mình sử dụng cấu trúc dữ liệu gì và giải quyết bài toán nào mà có giải thuật cho phù hợp.

luong_dien_nhan

05-03-2004, 01:50

bạn không cần đọc code của mấy người kia làm gì cho mệt, bạn nên hiểu tư tưởng của gỉai thuật thì tốt hơn

luong_dien_nhan

05-03-2004, 01:55

bạn nên tìm đọc cuốn cấu trúc dữ liệu và giải thuật của GS_TS Đỗ Xuân Lôi

songok

05-03-2004, 02:22

Theo minh nghi thi de so sanh toc do cua tung giai thuat , ta dua vao thu mot mang co co 1000 hay nhieu hon nua cac phan tu de cho no chay thu xem, chu mot vai phan tu thi sap xep kieu nao cung nhu nhau thoi

bete

05-03-2004, 11:20

Quote từ luong_dien_nhan: bạn không cần đọc code của mấy người kia làm gì cho mệt, bạn nên hiểu tư tưởng của gỉai thuật thì tốt hơn

Nếu bạn đọc code hoặc ý tưởng hôm nay; một tuần sau bạn ngồi trước máy, 0 cần giở sách mà vẫn có thể viết lại được => vậy là tốt lắm (nếu 1 tháng sau, 1 năm sau ba,n vẫn viết lại được 0 cần giở sách => bạn đã nắm được giải thuật => chuẩn bị nghĩ ra 1 giải thuật riêng cho mình :))

general2000vn

05-03-2004, 14:45

Cảm ơn các tiền bối cho lời khuyên. Nhưng mà cái mình cần hiện nay là ai đó giải thích giùm mình, giải thích cái mấy thuật toán thui, không cần code cũng được.

To pete: "2) quick sort: chạy log2(n) đợt con (vì mỗi đợt => chiều dài mảng con bị chia 2)" . Cái câu này mình .... không đồng ý.

Lấy lại cái ví dụ của bạn ke_tui_nha:
0 1 2 3 4 5 6
[ 1 3 9 5 8 7 2 ]

Nếu như phần tử chính giữa là 2 thì sao? Cái mảng con đâu còn là n/2 phần tử nữa đâu? Mà thật ra để phân hoạch, thì cũng lấy phần tử ở giữa so sánh với n-1 phần tử còn lại rồi.

Sau đó nó sinh ra 2 mảng con, thì cái chuyện đó cũng khó nói à. Ví dụ lần phân họach đầu, cái phần tử (PT) chính giữa là PT có giá trị nhỏ nhất, thì sau khi phân họach chỉ loại được 1 PT, mãng con cũng lại gồm N-1 PT.

Rồi phân họach tiếp, thằng PT chính giữa của mãng N-1 lại là thằng nhỏ nhất mãng con, thì lãi loại thêm 1 PT và có mãng con gồm N-2 PT.

Cứ như thế, thì nó đâu còn khác gì là Sủi bọt, số lần so sánh là như nhau. Tất nhiên mọi chuyện ở đây là đặt vào trường hợp xấu nhất có thể xảy ra.

Giờ lấy cái Merge Sort của bạn Mu_Chu_Java:

Sau lần merge đầu tiên, số lượng thành phần (mãng con) giảm 1 nữa, nhưng mà phép so sánh chưa chắc giảm một nữa.

ví dụ: 1 8 7 4 3 6 2 5
lần 1: [1 8] [4 7] [3 6] [2 5] : so sánh 4 lần
lần 2: [1 4 7 8] [2 3 5 6] : so sánh 8 lần
......

Cứ như thế, số lượng thành phần giảm 1/2, thì số lần so sánh tăng 1/2.

Nói cách khác, thằng Phần Tử thứ nhất (là [1] trong mãng ví dụ đã được so sánh với tất cả mấy thằng còn lại. Tương tự thằng PT thứ 2 (là [4]) cũng thế, về tính chất này thì giống y chang như Sủi Bọt => sốn lần so sánh ngang nhau.

Do đó mình muốn nói, là mấy cách sắp xếp trên đều như nhau, chỉ có khác là mảng ban đầu đối với cách này thì tối ưu, đối với cách kia lại là kém hiệu quả, chỉ phụ thuộc vào vị trí ban đầu của mảng thui. Không phụ thuộc vào số lượng PT.

Ý của mình như thế, không biết có sai gì hông, mấy bạn góp ý giùm. Thanks.

Mình thấy hình như ý của mấy bạn nói là có tới 9 thuật giải, vậy ai biết chỉ mình biết với.

bete

05-03-2004, 16:24

To bete: "2) quick sort: chạy log2(n) đợt con (vì mỗi đợt => chiều dài mảng con bị chia 2)" . Cái câu này mình .... không đồng ý.

Lấy lại cái ví dụ của bạn ke_tui_nha:
0 1 2 3 4 5 6
[ 1 3 9 5 8 7 2 ]

Nếu như phần tử chính giữa là 2 thì sao? Cái mảng con đâu còn là n/2 phần tử nữa đâu? Mà thật ra để phân hoạch, thì cũng lấy phần tử ở giữa so sánh với n-1 phần tử còn lại rồi.

Sau đó nó sinh ra 2 mảng con, thì cái chuyện đó cũng khó nói à. Ví dụ lần phân họach đầu, cái phần tử (PT) chính giữa là PT có giá trị nhỏ nhất, thì sau khi phân họach chỉ loại được 1 PT, mãng con cũng lại gồm N-1 PT.

Rồi phân họach tiếp, thằng PT chính giữa của mãng N-1 lại là thằng nhỏ nhất mãng con, thì lãi loại thêm 1 PT và có mãng con gồm N-2 PT.

Cứ như thế, thì nó đâu còn khác gì là Sủi bọt, số lần so sánh là như nhau. Tất nhiên mọi chuyện ở đây là đặt vào trường hợp xấu nhất có thể xảy ra.

Tui xin đồng ý với sự 0 đồng ý của bạn :)
Tuy nhiên bạn có có nói: "đặt vào trường hợp xấu nhất có thể xảy ra" => rất là đụng Nếu tui 0 lầm thì khi phân tích đọ phức tạp O người ta thường xét đến
trường hợp tốt nhất (hay trung bình - 0 nhớ chắc) thì phải . Do đó mới gọi là quick sort; chứ nếu căn cứ vô trường hợp xấu nhất thì có lễ đã gọi là slow-ssort rồi :)

Tui cũng 0 ngờ là có đến 9 giải thuật sắp xếp => lật mấy cuốn sách đếm thử thì thấy:
1) straight insertion
2) binary insertion sort
3) straight selection
4) straight exchange (bubble sort)
5) bubble sort with flag
6) shaker sort
7) insertion sort by diminishing increment (shellsort)
8) tree sort (heap sort)
9) partition sort (quick sort)
10) merge sort
11) counting sort (số nguyên)
12) radix sort
13) bucket sort

(3 cái cuối hình như đòi hỏi dữ liệu muốn sắp xếp phải thỏa 1 số điều kiện nào đó mới áp dụng được !)

Tui chắc là còn sót so với 9 cái của luong_dien_nhan (mong bạn cho biết)
Tui cũng chắc là ở trường bây giờ 0 nhất thiết phải dạy hết (& mình 0 nhất thiết phải biết hết): chỉ cần biết vài cái chính yếu (quick sort, heap sort, merge sort) là đủ !

msn

05-03-2004, 21:15

Tôi xin bổ sung thêm sort bằng cây tìm kiếm nhị phân.
Theo ý kiến của tôi
Ổn định nhất: Heap Sort
Nhanh nhất với số thực: Quick Sort (Nếu cải tiến chọn chốt thì không thể SlowSort)
Merge Sort
Nhanh nhất với số nguyên nhỏ: Distribution Counting
Nhanh nhất với số nguyên lớn: Radix Sort

luong_dien_nhan

06-03-2004, 04:32

theo sự hiểu biết của tui thì gồm có
1.bubble sort
2.insertion sort
3.selection sort
4.SHELL sort
5.merg sort
6.quick sort
7.heap sort
8.Radix sort
9.tree sort
bạn bete đọc được bucket sort và shaker sort ở sách nào xin làm ơn chỉ cho tui biết với ,tui đang nghiên cứu về data structure and algorithms ,? xin đa tạ nhiều!

bete

06-03-2004, 11:45

Bạn luong_dien_nhan:

1) shaker sort: cái này ở trong "Algorithm+DataStructure=Programs" (Niklaus Wirth) => xưa lắm rồi !
Đại khái là sửa budble sort lại 1 tí: bubble sort làm nổi những phần tử nhẹ (nhỏ) lên mau nhưng làm chìm nhưng phần tử nặng (lớn) xuống chậm => thay đổi hướng xen kẽ . Nếu luong_dien_nhan vẫn còn muốn biết rõ thì tui sẽ gõ cái code vô (chừng 20 dòng)

2) Bucket sort: "Introduction to Algorithm" (Thomas Cormen, Charles Leiserson & Ronald Rivest): giả thiết dữ liệu muốn sắp xếp là những số thực (ngẫu nhiên) phân bố đồng nhất trong khỏang [0,1) => chia khỏang [0,1) thành N buckets . Sau đó bỏ các số của dữ liệu nhập vô đúng buckets tương ứng . Ví dụ N=10: số trong khỏang [0,0.1) => bucket #1, [0.1,0.2) => bucket #2, ..... Xong thì sắp xếp (bằng insertion sort) trong mõi bucket & và in ra theo thứ tự bucket #1, bucket #2, ... bucket #N (khi in bucket thì in các số theo thứ tự đã sắp xếp)

ke_tui_nha

06-03-2004, 18:41

Quicksort trong trường hợp xấu nhất thì cũng chả nhanh hơn các phương pháp sắp xếp đơn giản là bao :D. Chỉ có heapsort là hiệu quả trong mọi trường hợp.
Mergesort thì không ai dùng để sắp xếp dãy cả :D:D:D

bete

06-03-2004, 19:57

Tui nghĩ merge sort có lợi nếu mảng là lớn: 0 vừa bộ nhớ chẳng hạn => sort trên file
Nếu mảng là lớn thì cho dù có dùng bộ nhớ ảo thì tui nghĩ do bản chất truy xuất bộ nhớ ngẫu nhiên của các thật toán khác => vẫn có lợi hơn nếu xài mergee sort (truy xuất tuần tự)

luxuguy

06-03-2004, 23:23

Toi thay Heap sort la nhanh nhat vi` cach luu tru hieu qua cua no' ... neu ban muon tim hiu thi coi trong may cuon sach Cau Truc Du Lieu & Thuat toan ... co day du o trong ...

general2000vn

07-03-2004, 15:12

Vậy là .... túm lại .... sao? Hình như là nếu tính số lần so sánh thì trong trường hợp xấu nhất, mọi giải thuật đều như nhau hả? Còn tùy vào data structure nên chọn kiểu sort cho phù hợp và hiệu quả => nhanh , phải không? Câu hỏi cuối của Newbie đó. Chốt lại giùm nha các bác.

À, ví dụ như cái database Access, nó sort bằng cách nào?

ke_tui_nha

07-03-2004, 17:57

Merge sort là hiệu quả nhất

À, ví dụ như cái database Access, nó sort bằng cách nào?
Cái này chắc phải hỏi thằng Microsoft mới biết được :lick:

mù_chữ_Java

08-03-2004, 10:15

cha chả mí chú mí bác... kiểu này mà tui là người đặt ra câu hỏi đầu tiên cho thread này chắc tui cũng rối trí luôn wé.
To GeneralVn2000: Có thể trong trường hợp xấu nhất thì quicksort chạy còn chậm hơn mấy sort khác. Tuy nhiên thực tế thì mí trường hợp này không xảy ra nhiều lắm...
Nguyên tắc chung để xài loại sort nào cho phù hợp thì không có, vì người viết chương trình có thể không biết trước người dùng sẽ đưa vào dữ liệu kiểu gì. Nhưng theo kinh nghiệm thì nếu như bạn dùng chương trình của bạn cho những ứng dụng đơn giản, xài ít data thì cứ việc xài Bubble sort, Insertion sort và Selection sort, mí cái đơn giản dùng 2 vòng lặp ý. Còn nếu bạn phải dùng những dữ liệu thật lớn để quản lý toàn bộ member của DDTH chẳng hạn, lúc đó bạn nên xài mấy cái nlog(n) sort như Heap, Merge, Quick.

To ke_tui_nha:

Merge sort là hiệu quả nhất

Mergesort thì không ai dùng để sắp xếp dãy cả :D :D :D
vậy thì bạn muốn seo :)?

monkeyvu

08-03-2004, 16:54

:glare: Hay là đừng có sort,để nguyên dzậy đi.

ke_tui_nha

08-03-2004, 20:56

cha chả mí chú mí bác... kiểu này mà tui là người đặt ra câu hỏi đầu tiên cho thread này chắc tui cũng rối trí luôn wé.
To GeneralVn2000: Có thể trong trường hợp xấu nhất thì quicksort chạy còn chậm hơn mấy sort khác. Tuy nhiên thực tế thì mí trường hợp này không xảy ra nhiều lắm...
Nguyên tắc chung để xài loại sort nào cho phù hợp thì không có, vì người viết chương trình có thể không biết trước người dùng sẽ đưa vào dữ liệu kiểu gì. Nhưng theo kinh nghiệm thì nếu như bạn dùng chương trình của bạn cho những ứng dụng đơn giản, xài ít data thì cứ việc xài Bubble sort, Insertion sort và Selection sort, mí cái đơn giản dùng 2 vòng lặp ý. Còn nếu bạn phải dùng những dữ liệu thật lớn để quản lý toàn bộ member của DDTH chẳng hạn, lúc đó bạn nên xài mấy cái nlog(n) sort như Heap, Merge, Quick.

To ke_tui_nha:

vậy thì bạn muốn seo :)?
Quên, Heap sort chứ không phải merge sort :glare:

basic_delphi

09-03-2004, 00:28

Nói chung sắp xếp có rất nhiều cách. Nào thì bubble sort (dễ nhất nhưng chậm nhất), insertion sort(đơn giản nhưng cũng chậm), quick sort(nhanh nhất từ trước tới nay), heap sort(về lý thuyết thì nhanh hơn quick sort nhưng trong thực tế chưa từng có điều này) và merge sort(chẳng nhớ làm sao nhưng nói chung người ta không thích). Mỗi phương pháp lại có một ưu thế ở những mảng khác nhau. Ví dụ như mảng đã gần xếp xong mà dùng quick thì lâu nhưng bubble thì nhanh. Ngược lại,nếu trật tự mảng bị đảo lộn lung tung thì trong trường hợp này quick và heap tỏ ra lợi thế, bubble bị tụt xuống cuối cùng. Hic...

moibelgal

15-03-2004, 21:36

Các bạn có thể tìm xem demo applet về tốc dộ của các phương pháp Sort trong JDK 1.4

btkiet

23-03-2004, 15:47

tính độ phức tạp O người ta thường xét đến trường hợp trung bình.

nofear

31-03-2004, 14:14

Độ trung bình làm (average case) thì làm sao có thể phân tích được mà tính O đây chời...hix...Ví dụ: sắp xếp mảng chữ sau:

S O R T I N G A L G O R I T H M

Best case: no exchanges occured. This is the case when these chars are already fixed in their final position:
A H I I G G K L M N O O R R S T
Khi đó complexity của thuật toán sẽ là O(n) vì không có một sự hoán đổi vị trí nào (được thực hiện ở vòng lặp thứ 2).

Worse Case: n comparison and n exchanges. The example for this case is that the string of chars is in reverse order:
T S R R O O N M L K G G I I H A
Complexity sẽ là O(n^2) vì có n comparisions và n exchanges.

Average Case: giống Worse case nhưng sẽ được analysis theo một phương pháp khác.nói chung là không thể đo chính xác complexity của Average case vì nó random mà. Thường các nhà phân tích hay dựa vào worse case để tính các average case.

Sorry vì có một số terminology mình không biết dịch ra tiếng Việt... :)

minhbeo

04-04-2004, 18:53

Tôi là dân Amateur nên chỉ biết mỗi cái sủi bọt, mà cũng không muốn tìm hiểu nhiều cho nhức đầu, ngày nay máy thì mạnh, bộ nhớ thì to, cần gì mấy cái thuật toán lằng nhằng, với mỗi thuật sủi bọt vẫn giải quyết tốt mấy chương trình phục vụ công việc. Có điều nói cho vui vậy thôi, chứ nếu đang còn học ở trường thì các bạn đều phải ngâm cứu thôi.

imweasel

01-06-2004, 06:50

hehe, em thấy mấy cái này lại rất quan trọng. Nhất là trong những trường hợp phải tính toán nhiều thì việc dùng thuật toán thế nào để đạt hiệu quả cao nhất với bộ nhớ xác định trước là cả một thứ phải suy nghĩ, chưa kể phải kết hợp và modify cái algo có trước. Chắc tại tùy yêu cầu công việc của mỗi người.

buon_vi_dep_2003

26-06-2004, 23:00

sau đây là một số code thuật toán sort C++ mà các bạn trình bày trên .

// sắp xếp tăng từ trái sang phải
void hoanvi(int & x,int & y){
int tmp=x;
x=y;
y=t;
}

void bubble_sort(int a[],int n){
for (int i=0;i<n-1;i++)
for (int j=n;j>i;j--)
if (a[j]<a[j-1]) hoanvi (a[j-1],a[j]);
}

void selection_sort(int a[],int n){
for (int i=0;i<n-1;i++)
int min=i;
for (int j=i+1;j<n;j++)
if (a[j]<a[min]) {
min=j;
hoanvi(a[j],a[min]);
}

void interchang_sort(int a[],int n){
for (int i=0;i<n-1;i++)
for (int j=i+1;j<n;j++)
if (a[j]<a[i]) {
hoanvi(a[j],a[i]);
}
void insertion_sort(int a[],int n){
for (int i=1;i<n;i++)
int x=a[i];
int j=i-1;
while ((j>=0) && (a[j]>x))
{
a[j+1]=a[j];
j--;
}
a[j]+1]=x;// chèn x vào vị trí
}

Mergesort và qiucksort thì bạn nào đã trình bày trang 1 rồi !!!!

buon_vi_dep_2003

02-07-2004, 05:45

void shell_sort(int a[],int n,int b[],int m){// phân hoạch
// mảng b[m] là mảng nghịch .Ví dụ : 5 3 1 nên là 1 ở vị trí cuối
for (int j=0;j<m;j++)
{
int len=b[j];
for (int i=kc;i<n;i++){
int x=a[i];
int k=i-len;
while ((k>=0) && (a[k]>x)) {
a[k+len]=a[k];k--;
}
a[k+len]=x;
}
}

// còn sort là Natural Sort & Heap sort.Không biết huynh nào post lên đây ??

biboda

19-08-2004, 03:58

Mình có đọc trong một cuốn sách dạy Pascal căn bản, thấy nó chỉ 3 cách sáp xếp mảng.

Cách thứ 1 là sủi bọt, cách thứ 2 là chèn cái gì gì đó, nhưng mà mình coi lại thì 2 cách này là 1, chỉ có một thằng đi ngược, một thằng đi xuôi.

Còn cách thứ 3 theo như nó nói là nhanh nhất, nhưng mà mình đọc thì chẳng hiểu gì cả, cái gì gì mà chia mãng ra làm 2, rồi xoay, rối chi tiếp cái mãng con, chi đến khi nào hết chia được thì mãng cũng đã sắp xếp xong.

Vậy ai biết về cách thứ 3 này, làm ơn giảng giải cho mình hiểu với, hoặc là có cách nào sắp xếp mãng nhanh thì chỉ mình với. Thanks a lot.

Tùy trường hợp mà đánh giá mức độ nhanh chậm của thuật toán!(chứ ko phải độ phức tạp của thuật toán nha)
Thuật toán quick sort chỉ thật sự ...quick khi số lượng các phần tử cần sắp xếp là lớn thôi chứ với một trường hợp với số lượng phần tử vừa phải thì thuật toán này chưa hẳn quick. Không tin các bác cứ thử coi!

Crz_Mself

25-08-2004, 12:46

Cái code của heap sort trong pascal là gì ạ ? tư tưởng của nó thế nào?
Còn cái radix với lại distribution counting ntn ?

mljvv2004

25-08-2004, 14:56

Tốt nhất là bạn dùng QuickSort vừa ngắn gọn vừa hiệu quả, nhưng phải chọn chốt hợp lí thì độ phức tạp chỉ còn O(nlogn). Heap sort chậm hơn QuickSort, tôi chỉ dùng nó để tìm cây khung bao trùm bằng thuật toán Kruskal là tiện nhất, còn radix sort nhanh nhưng cài phức tạp, distribution counting chạy nhanh với số nguyên nhưng chỉ chạy được khi giá trị của khoá nhỏ, nói chung là cũng nên học cái này. QuickSort vẫn là nhất, ứng dụng nhiều nhất.

snow_white

31-08-2004, 02:27

chẳng phải ngẫu nhiên mà người ta nghĩ ra nhiều thuật toán sắp xếp đến thế. Theo mình thì người học về giải thuật nên biết hết tất cả các thuật toán sắp xếp, để học được các tư tưởng trong đó. Còn thì nên chọn riêng cho mình một giải thuật riêng thành thạo để áp dụng. Tuy nhiên trong từng bài toán lại phải áp dụng từng kiểu riêng. Ví dụ như Kruskal thì hiển nhiên là dùng Heap rồi. Còn nếu muốn dùng QSort mà tránh được trường hợp xấu nhât thì nên chọn khoá ngẫu nhiên, mức độ rủi ro sẽ rât thấp! Các bài toán về số học mà dùng sắp xếp cơ số thì nhanh tuyệt rồi, nếu QS hết 0.5s thì nói chung nó chỉ hết 0.1s, và nói chung là nhanh hơn QS, nhưng lại rất khó cài đặt và không phù hợp với các data khác... nói chung là mỗi thuật toán có một ưu điểm riêng...