Thuật toán sắp xếp nhanh nhất, nhanh hơn QuickSort !

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)