Giải thuật Nói chung các giải thuật đã trình bày ở trên đều có độ phức tạp là O(n2) hoặc O(nlogn). Tuy nhiên khi kiểu dữ liệu của trường khoá là một kiểu đặc biệt, việc sắp xếp có thể chỉ chiếm O(n) thời gian. Sau đây ta sẽ xét một số trường hợp. | Giải thuật Sắp xếp BINSORT Giải thuật Nói chung các giải thuật đã trình bày ở trên đều có độ phức tạp là O n2 hoặc O nlogn . Tuy nhiên khi kiểu dữ liệu của trường khoá là một kiểu đặc biệt việc sắp xếp có thể chỉ chiếm O n thời gian. Sau đây ta sẽ xét một số trường hợp. Trường hợp đơn giản Giả sử ta phải sắp xếp một mảng A gồm n phần tử có khoá là các số nguyên có giá trị khác nhau và là các giá trị từ 1 đến n. Ta sử dụng B là một mảng cùng kiểu với A và phân phối vào phần tử b j một phần tử a i mà a i .key j. Khi đó mảng B lưu trữ kết quả đã được sắp xếp của mảng A. Ví dụ 2-7 Sắp xếp mảng A gồm 10 phần tử có khoá là các số nguyên có giá trị là các số 4 7 1 2 5 8 10 9 6 và 3 Ta sử dụng mảng B có cùng kiểu với A và thực hiện việc phân phối a 1 vào b 4 vì a 1 .key 4 a 2 vào b 7 vì a 2 .key 7 a 3 vào b 1 vì a 3 .key 1 . Hình sau minh họa cho việc phân phối các phần tử của mảng a vào mảng b. Nguyên Văn Linh Trang 39 Sưu tầm bởi Giải thuật Sắp xếp Mảng a Khóa a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 4 7 1 2 5 8 10 9 6 3 X - X Ỵ Khóa Mảng b 1 2 3 4 5 6 7 8 9 10 b 1 B 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 10 Hình 2-18 Phân phối các phân tử a i vào các bin b j Để thực hiện việc phân phối này ta chỉ cần một lệnh lặp for i 1 to n do b a i .key a i Đây cũng là lệnh chính trong chương trình sắp xếp. Lệnh này lấy O n thời gian. Các phần tử b j được gọi là các bin và phương pháp sắp xếp này được gọi là bin sort. Trường hợp tổng quát Là trường hợp có thể có nhiều phần tử có chung một giá trị khóa chẳng hạn để sắp một mảng A có n phần tử mà các giá trị khóa của chúng là các số nguyên lấy giá trị trong khoảng với m n. Trong trường hợp này ta không thể sử dụng các phần tử của mảng B làm bin được vì nếu có hai phần tử của mảng A có cùng một khoá thì không thể lưu trữ trong cùng một bin. Để giải quyết sự đụng độ này ta chuẩn bị một cấu trúc có m bin mỗi bin có thể lưu trữ nhiều hơn một phần tử. Cụ thể là bin thứ j sẽ lưu các phần tử có khóa là
