quocdunginfo
Tổng số bài gửi : 3 Reputation : 1 Join date : 07/06/2011
| Tiêu đề: Thuật toán sắp xếp nhanh nhất, nhanh hơn QuickSort ! Tue Jun 07, 2011 9:08 pm | |
| Xem chi tiết tại đây-Cùng 1 bộ input ngẫu nhiên gồm 100,000,000 phần tử, Quicksort cho thời gian sắp xếp tăng dần là 26 giây, trong khi đó InteractiveSort cho thời gian là 0.5 giây! (cả 2 giải thuật đều không kể thời gian load dữ liệu). Bạn có tin không ?! -Khi số lượng phần tử lớn (trên 10,000,000) một số thuật giải sắp xếp hiện tại không thể đáp ứng được, và đòi hỏi một thuật giải khác tối ưu hơn, một trong những giải thuật sắp xếp tốt nhất hiện nay có thể kể đến như Quicksort, Shellsort, Mergesort, Heapsort, … tuy nhiên với những bộ dữ liệu đặc trưng, điển hình như một dãy gồm trên 100,000,000 các số nguyên có giá trị tuyệt đối không vượt quá 100,000,000 thì những thuật sắp xếp trên không đáp ứng được về thời gian. -Và một giải thuật mới ra đời, InteractiveSort (sắp xếp trực quan), mình đã suy nghĩ và phát triển một cách độc lập, hoàn chỉnh thuật giải này, tuy nhiên, thật không may mắn là đã có người khác phát hiện ra trước đó rồi. Puồn 5 giây. -Cấu hình: CPU Core 2 Dou T6570 (2.21 GHz), RAM 2GB DDR3, trình biên dịch C-Free 5 -Ý tưởng của InteractiveSort là lần lượt đưa các phần tử của mảng cần sắp xếp (mảng a) vào mảng mới (mảng tmp) bằng cách tmp[a[i]] = số phần từ ứng với giá trị a[i], bằng cách này, sau khi thực hiện xong, ta sẽ thu được các phần tử trên mảng tmp đã nằm đúng thứ tự, việc còn lại là copy tất cả các phần tử của tmp về ngược lại mảng cần sắp xếp, bằng một số thủ thuật như tịnh tiến ảo mảng a về bên phải k phần tử trước khi tiến hành sắp xếp để đảm bảo chúng ta không xử lý số âm, trong đó k=ABS(MIN(mảng a)), ta sẽ dễ dàng tổng quát cho trường hợp các phần tử a[i] là số âm. Và do dùng chính giá trị của từng phần tử trong mảng a, nên chương trình không thể xử lý các số thực (đây là nhược điểm hạn chế của thuật giải trực quan) | |
|
thachthen_it Admin
Tổng số bài gửi : 53 Reputation : 0 Join date : 19/05/2011 Age : 32 Đến từ : trà vinh
| Tiêu đề: gửi quocdunginfor Sun Jun 12, 2011 9:57 am | |
| cám ơn bạn đã đóng góp một giải thuật rất hay cho diễn đàn rất mong sự nhiệt tình tham gia của bạn ,chúng ta hãy cùng nhau chung tay góp sức lấp đầy những thiếu xót để thật sự trở thành một sinh viên công nghệ thông tin theo đúng nghĩa của nó mà bạn có thể cho code để mọi người cùng tham khảo không nếu thế sẽ dễ dàng nắm bắt cách làm việc của giải thuật hơn; mà tôi nghĩ bạn nên khai báo tuổi của mình để tiện cho việc xưng hô kẻo mà........... | |
|