Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình hướng dẫn kĩ thuật phân tích đánh giá giải thuật theo phương pháp tổng quan p7

Trong hàm FindPivot các lệnh {1}, {2}, {3} và {4} nối tiếp nhau, trong đó chỉ có lệnh WHILE là tốn nhiều thời gian nhất do đó thời gian thực hiện của hàm FindPivot phụ thuộc vào thời gian thực hiện của lệnh này. Trong trường hợp xấu nhất (không tìm thấy chốt) thì k chạy từ i+1 đến j, tức là vòng lặp thực hiện j-i lần, mỗi lần O(1) do đó tốn j-i thời gian. Đặc biệt khi i=1 và j=n, thì thời gian thực hiện là n-1 hay T(n) = O(n) | Giải thuật Sắp xếp 5 IF a k .key FirstKey THEN FindPivot k ELSE FindPivot i END Trong hàm FindPivot các lệnh 1 2 3 và 4 nối tiếp nhau trong đó chỉ có lệnh WHILE là tốn nhiều thời gian nhất do đó thời gian thực hiện của hàm FindPivot phụ thuộc vào thời gian thực hiện của lệnh này. Trong trường hợp xấu nhất không tìm thấy chốt thì k chạy từ i 1 đến j tức là vòng lặp thực hiện j-i lần mỗi lần O 1 do đó tốn j-i thời gian. Đặc biệt khi i 1 và j n thì thời gian thực hiện là n-1 hay T n O n . 2.4.3.2 Hàm Partition Hàm Partition nhận vào ba tham số i j và Pivot để thực hiện việc phân hoạch mảng a i .a j theo chốt Pivot và trả về giá trị L là chỉ số đầu tiên của mảng bên phải . Hai con nháy L R sẽ được sử dụng để thực hiện việc phân hoạch như đã trình bày trong phần 2.4.2.3. FUNCTION Partition i j integer pivot KeyType integer VAR L R integer BEGIN 1 L i Đặt con nháy L ở cực trái 2 R j Đặt con nháy R ở cực phải 3 WHILE L r DO BEGIN L tiến sang phải 4 WHILE a L .key pivot DO L L 1 R tiến sang trái 5 WHILE a R .key pivot DO R R-1 6 IF L R THEN Swap a L a R END 7 Partition L Trả về điểm phân hoạch END Trong hàm Partition các lệnh 1 2 3 và 7 nối tiếp nhau trong đó thời gian thực hiện của lệnh 3 là lớn nhất do đó thời gian thực hiện của lệnh 3 sẽ là thời gian thực hiện của hàm Partition. Các lệnh 4 5 và 6 là thân của lệnh 3 trong đó lệnh 6 lấy O 1 thời gian. Lệnh 4 và lệnh 5 thực hiện việc di chuyển L sang phải và R sang trái thực chất là duyệt các phần tử mảng mỗi phần tử một lần mỗi lần tốn O 1 thời gian. Tổng cộng việc duyệt này tốn j-i thời gian. Vòng lặp 3 thực chất là để xét xem khi nào thì duyệt xong do đó thời gian thực hiện của lệnh 3 chính là thời gian thực hiện của hai lệnh 4 và 5 và do đó là j-i. Đặc biệt khi i 1 và j n ta có T n O n . 2.4.3.3 Thủ tục Quicksort Bây giờ chúng ta trình bày thủ tục cuối cùng có tên là Quicksort và chú ý rằng để sắp xếp mảng A các record gồm n phần tử của kiểu Recordtype ta chỉ cần gọi QuickSort 1 n . Ta sẽ sử dụng biến Pivotindex để lưu