Tiếp tục quá trình trên và giải thuật kết thúc sau bước 9, ứng với bước i =2. Phân tích HeapSort Thời gian thực hiện của HeapSort là O(n logn) Như đã phân tích trong mục , thủ tục PushDown lấy O(logn) để đẩy một nút xuống trong cây có n nút. Trong thủ tục HeapSort dòng lệnh {1}-{2}) lặp n/2 lần mà mỗi lần PushDown lấy O(logn) nên thời gian thực hiện | Giải thuật Sắp xếp Chỉ số 1 2 3 4 5 6 7 8 9 10 Ban đầu 5 2 6 2 5 3 2 2 6 10 3 5 12 9 10 9 3 10 Heap 2 10 2 3 2 10 9 6 5 12 9 10 10 9 10 2 i 10 2 9 3 3 9 5 9 6 5 9 12 10 10 9 2 2 i 9 3 10 5 5 10 6 9 6 10 9 12 10 10 3 2 i 8 5 6 9 10 9 12 10 3 Hình 2-17 Hoán đổi a 1 với a 8 và đầy a 1 xuống trong a Tiếp tục quá trình trên và giải thuật kết thúc sau bước 9 ứng với bước i 2. Phân tích HeapSort Thời gian thực hiện của HeapSort là O n logn Như đã phân tích trong mục thủ tục PushDown lấy O logn để đẩy một nút xuống trong cây có n nút. Trong thủ tục HeapSort dòng lệnh 1 - 2 lặp n 2 lần mà mỗi lần PushDown lấy O logn nên thời gian thực hiện 1 - 2 là O n logn . Vòng lặp 3 - 4 - 5 lặp n-1 lần mỗi lần PushDown lấy O logn nên thời gian thực hiện của 3 - 4 - 5 là O n logn . Tóm lại thời gian thực hiện HeapSort là O n logn . 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 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 .
