TAILIEUCHUNG - Giáo trình giải thuật của Nguyễn Văn Linh part 5

Hàm FindPivot Ta thiết kế hàm FindPivot để xác định trong dãy a[i]a[j] có hay không hai phần tử có khóa khác nhau. Nếu không tìm thấy hai phần tử có khóa khác nhau thì trả về giá trị 0 (không tìm thấy chốt), ngược lại hàm trả về giá trị là chỉ số của phần tử có khóa lớn hơn trong hai phần tử có khóa khác nhau đầu tiên. Khóa lớn hơn này sẽ trở thành phần tử chốt mà ta sẽ xác định trong thủ tục QuickSort | Giải thuật Sắp xếp Giải thuật Quicksort Để sắp xếp mảng a i .a j ta tiến hành các bước sau Xác định chốt. Phân hoạch mảng đã cho thành hai mảng con a i .a k-1 và a k .a j . Sắp xếp mảng a i .a k-1 Đệ quy . Sắp xếp mảng a k .a j Đệ quy . Quá trình đệ quy sẽ dừng khi không còn tìm thấy chốt. Ví dụ 2-4 Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên 5 8 2 10 5 12 8 1 15 và 4. Với mảng a 1 .a 10 hai phần tử đầu tiên có khóa khác nhau là là a 1 và a 2 với khoá tương ứng là 5 và 8 ta chọn chốt v 8. Để phân hoạch khởi đầu ta cho L 1 đặt L ở cực trái và R 10 đặt R ở cực phải . Do a L có khoá là 5 nhỏ hơn chốt nên L L 1 2 di chuyển L sang phải lúc này a L có khoá là 8 chốt nên dừng lại. Do a R có khoá là 4 nhỏ hơn chốt nên R cũng không chuyển sang trái được. Tại các điểm dừng của L và R ta có L R L 2 và R 10 nên hoán đổi a L và a R a 2 và a 10 cho nhau. Sau khi hoán đổi a L lại có khoá là 4 nhỏ hơn chốt nên di chuyển L sang phải L L 1 3 . Khoá của a L là 2 nhỏ hơn chốt nên lại di chuyển L sang phải L L 1 4 . Khoá của a L là 10 lớn hơn chốt nên dừng lại. Với R khoá của a R bây giờ là 8 bằng chốt nên di chuyển R sang trái R R-1 9 . Khoá của a R là 15 lớn hơn chốt nên di chuyển R sang trái R R-1 8 . Khoá của a R là 1 nhỏ hơn chốt nên dừng lại. Tại các điểm dừng của L và R ta có L R L 4 và R 8 nên hoán đổi a L và a R a 4 và a 8 cho nhau. Sau khi hoán đổi a L có khoá là 1 nhỏ hơn chốt nên di chuyển L sang phải L L 1 5 . Khoá của a L là 5 nhỏ hơn chốt nên lại di chuyển L sang phải L L 1 6 . Khoá của a L là 12 lớn hơn chốt nên dừng lại. Với R khoá của a R bây giờ là 10 lớn hơn chốt nên di chuyển R sang trái R R-1 7 . Khoá của a R là 8 bằng chốt nên di chuyển R sang trái R R-1 6 . Khoá của a R là 12 lớn hơn chốt nên di chuyển R sang trái R R-1 5 . Khoá của a R là 5 nhỏ hơn chốt nên dừng lại. Tại các điểm dừng của L và R ta có L R L 6 và R 5 nên ta đã xác định được điểm phân hoạch ứng với L 6. Tức là mảng đã cho ban đầu được phân thành hai mảng con bên trái a 1 .a 5 và

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao