Cài đặt thuật toán quicksort
Trong bài tập này, bạn sẽ cài đặt thuật toán quicksort để sắp xếp một danh sách số.
Ở bước đầu tiên, bạn sẽ cài đặt hàm partition(), hàm này trả về chỉ số của pivot sau khi xử lý danh sách sao cho tất cả phần tử bên trái pivot đều nhỏ hơn pivot và tất cả phần tử bên phải pivot đều lớn hơn pivot.
Ở bước thứ hai, bạn sẽ cài đặt hàm quicksort(), hàm này sẽ gọi hàm partition().
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
def partition(my_list, first_index, last_index):
pivot = my_list[first_index]
left_pointer = first_index + 1
right_pointer = last_index
while True:
# Iterate until the value pointed by left_pointer is greater than pivot or left_pointer is greater than last_index
while ____ < ____ and ____ < ____:
left_pointer += 1
while my_list[right_pointer] > pivot and right_pointer >= first_index:
right_pointer -= 1
if left_pointer >= right_pointer:
break
# Swap the values for the elements located at the left_pointer and right_pointer
my_list[left_pointer], my_list[right_pointer] = ____, ____
my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]
return right_pointer