Xin thuật toán sắp xếp!!

English | Vietnamese

Rules

Main Forum

Portal

Member Listing

Statistics

Search

Reading Room
[Register]

Login [ | https ]

Forum Index

Thảo luận hệ điều hành Windows

Xin thuật toán sắp xếp!!

[Programming] Xin thuật toán sắp xếp!!	12/04/2009 01:03:48 (+0700) \| #1 \| 176713

qtran
Member

Joined: 12/12/2007 12:24:33
Messages: 12
Offline

Xin lỗi ae đã post bài không đúng box, nhưng em đa tìm mà không thấy.

Là thế này..
Em đang có đồ án giữa kì là tìm hiểu về một tuật toán sắp xếp ngoài những thuật toán này: (số là mấy cái này đã được học trên trường)

1. Bubble sort
2. Shaker sort
3. Insertion sort
4. Select sort
5. Heapsort
6. Quicksort
7. Radix sort
8. BinaryInsertion Sort
9. Shellsort

Em đã tìm khá nhìu rồi mà khó quá, xin lời khuyên của mấy ae.!!
có code C++ càng tốt, vì em phải làm trên đó.

Thanks ae.

[Question] Re: Xin thuật toán sắp xếp!!	12/04/2009 01:37:04 (+0700) \| #2 \| 176723

hizit91
Member

Joined: 04/01/2009 20:29:43
Messages: 133
Offline

em xin đóng góp 1 ý tưởng:

Cho dãy A1 ,... , An ( khác nhau từng cặp).

Lấy A1 ra, và đếm tất cả những Ai < A1, giả dụ có k số như vậy, vị trí của A1 sau sắp xếp sẽ là k + 1;
Tương tự cho A2, ..., An

Sau khi thực hiện:, Ta có 2 ánh xạ:

1 ánh xạ từ A --> bảng vị thứ.
1 ánh xạ từ bảng vị thứ --> A.

Độ phức tạp là n^2.

Hết cấp ba, ta lên cấp bố smilie

[Question] Re: Xin thuật toán sắp xếp!!	12/04/2009 01:52:32 (+0700) \| #3 \| 176725

thienthanh1986vn
Member

Joined: 28/01/2008 12:57:31
Messages: 2
Offline

ở đây mình chỉ có 5 thuật sắp xếp à
- Ínerttion
- Interchanger
- Selecttion
- Bubble
- Quick
bạn dùng tạm nha smilie

http://www.mediafire.com/download.php?wyoyymh5dtl

[Question] Xin thuật toán sắp xếp!!	12/04/2009 02:25:03 (+0700) \| #4 \| 176726

nbthanh
HVA Friend

Joined: 21/12/2001 14:51:51
Messages: 429
Offline

qtran wrote:

Xin lỗi ae đã post bài không đúng box, nhưng em đa tìm mà không thấy.

Là thế này..
Em đang có đồ án giữa kì là tìm hiểu về một tuật toán sắp xếp ngoài những thuật toán này: (số là mấy cái này đã được học trên trường)

1. Bubble sort
2. Shaker sort
3. Insertion sort
4. Select sort
5. Heapsort
6. Quicksort
7. Radix sort
8. BinaryInsertion Sort
9. Shellsort

Em đã tìm khá nhìu rồi mà khó quá, xin lời khuyên của mấy ae.!!
có code C++ càng tốt, vì em phải làm trên đó.

Thanks ae.

Không biết bạn có hiểu sai đề hay là sai ý thầy hay không chứ đề tài mà đúng như vầy thì quả là thầy bà ở VN đang làm khó SV.

List ra gần hết các thuật toán sắp sếp, rồi bắt SV tìm hiểu 1 cái ngoài danh sách? Vậy tức chả khác gì bắt SV nghiên cứu ra 1 thuật toán mới? Cái này...thầy của thầy của bạn cũng chưa chắc làm được chứ nói gì bạn!

(mà nếu đúng đề như vậy thì cái Merge Sort chưa có nằm trong list đó, bạn lấy mà đưa thầy smilie

)

[Question] Re: Xin thuật toán sắp xếp!!	12/04/2009 02:43:03 (+0700) \| #5 \| 176728

qtran
Member

Joined: 12/12/2007 12:24:33
Messages: 12
Offline

Đúng là Thầy bắt tìm hiểu như vậy đó. và trong list đó còn có lun cái Merge Sort của anh nbthanh lun rùi...(ac)..

Đại loại như ổng bắt tìm hiểu mấy cái như BucketSort, Cocktail sort, vv..vv... Mà em đọc vào chẳng hiểu mấy. mà nguyên tắc chấm bài là thi vấn đáp và demo chương trình + bao test!!
Không biết cái ý tưởng của bạn hizit91 có nằm trong thuật toán nào k? Hay là bạn tự nghỉ ra nhỉ? Nếu tự nghỉ ra thì sẽ cho nó cái tên khác...^^

Anh em giúp giùm, đồ án trong vòng một tuần thôi, đến hôm nay là còn 5 ngày nữa...

[Question] Re: Xin thuật toán sắp xếp!!	12/04/2009 05:09:09 (+0700) \| #6 \| 176742

hizit91
Member

Joined: 04/01/2009 20:29:43
Messages: 133
Offline

Hì, em tự nghĩ ra đó smilie

Hay gọi nó là thuật toán Sắp xếp chỉ số ( index ) smilie

, cái tên cũng hay, tại vì tinh thần của nó, là ta đi tim vị trí sau sắp xếp của các phần tử smilie

, thông qua đếm các phần tử nhỏ hơn nó smilie

Hết cấp ba, ta lên cấp bố smilie

[Question] Re: Xin thuật toán sắp xếp!!	12/04/2009 08:55:52 (+0700) \| #7 \| 176776

StarGhost
Elite Member

Joined: 29/03/2005 20:34:22
Messages: 662
Location: The Queen
Offline

Bạn đã thử flashsort chưa? Complexity trên lý thuyết của nó là O(n), mặc dù trên thực tế để khiến nó chạy nhanh hơn quicksort thì còn là cả một vấn đề, vì tính toán của nó phức tạp hơn nhiều. Nhưng mà thuật toán này chỉ làm việc hiệu quả với sắp xếp số nguyên thôi.

Edited: xóa một câu không cần thiết.

Mind your thought.

[Question] Re: Xin thuật toán sắp xếp!!	12/04/2009 08:59:20 (+0700) \| #8 \| 176778

blackboy212
Member

Joined: 30/12/2006 19:36:55
Messages: 17
Offline

bạn thử làm việc với cây đa nhánh đi, duyệt, thêm, xóa, sữa, hiễn thị

Go to:

Users currently in here
1 Anonymous