Mengimplementasikan algoritma quicksort
Dalam latihan ini, Anda akan mengimplementasikan algoritma quicksort untuk mengurutkan sebuah daftar angka.
Pada langkah pertama, Anda akan mengimplementasikan fungsi partition() yang mengembalikan indeks pivot setelah memproses daftar angka sehingga semua elemen di sebelah kiri pivot lebih kecil daripada pivot dan semua elemen di sebelah kanan pivot lebih besar daripada pivot.
Pada langkah kedua, Anda akan mengimplementasikan fungsi quicksort() yang akan memanggil fungsi partition().
Latihan ini adalah bagian dari kursus
Struktur Data dan Algoritma di Python
Latihan interaktif praktis
Cobalah latihan ini dengan menyelesaikan kode contoh berikut.
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