TAILIEUCHUNG - Giáo trình hình thành quá trình đánh giá kĩ thuật giải thuật theo phương pháp tổng quan p3

Tham khảo tài liệu 'giáo trình hình thành quá trình đánh giá kĩ thuật giải thuật theo phương pháp tổng quan p3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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 . 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 . 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 . 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 giữ kết .

• Toán học
• giáo trình đại số
• giáo trình lượng giác
• phương pháp học toán
• mẹo học toán cao cấp
• kỹ năng học toán
• Giáo án đại số 12
• tài liệu giảng đại số 12
• giáo trình đại số 12
• tài liệu đại số 12
• cẩm nang giảng dạy đại số 12
• Giáo án Đại Số 10
• tài liệu giảng dạy Đại Số 10
• giáo trình Đại Số 10
• tài liệu Đại Số 10
• cẩm nang giảng dạy Đại Số 10
• Thông tư số 07 2015 TT BGDĐT
• Giáo dục đại học
• Trình độ đào tạo giáo dục đại học
• Quy trình xây dựng trình độ đại học
• Quy trình xây dựng trình độ thạc sĩ
• Quy trình xây dựng trình độ tiến sĩ
• Giáo án Đại Số 8
• tài liệu giảng dạy Đại Số 8
• giáo trình Đại Số 8
• tài liệu Đại Số 8
• cẩm nang giảng dạy Đại Số 8