Quicksort

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Quicksort

  • Mengikuti prinsip divide and conquer
  • Diimplementasikan oleh banyak bahasa pemrograman
  • Teknik partisi
    • Pivot
    • item lebih kecil dari pivot -> kiri
    • item lebih besar dari pivot -> kanan
  • Elemen di kiri diurutkan rekursif
  • Elemen di kanan diurutkan rekursif
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak.

Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru.

  • Partisi Hoare
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen kedua dan penunjuk kanan ke elemen terakhir.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen ketiga dan penunjuk kanan ke elemen terakhir.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen ketiga dan penunjuk kanan ke elemen kelima.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen ketiga dan penunjuk kanan ke elemen kelima. Ada dua panah yang menunjukkan elemen ketiga dan kelima akan dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen ketiga dan penunjuk kanan ke elemen kelima. Elemen ketiga dan kelima telah dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen keempat dan penunjuk kanan ke elemen kelima.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen keempat dan penunjuk kanan ke elemen keempat.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen keempat dan penunjuk kanan ke elemen ketiga.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru. Ada dua penunjuk. Penunjuk kiri ke elemen keempat dan penunjuk kanan ke elemen ketiga. Ada dua panah yang menunjukkan elemen pertama dan ketiga akan dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen ketiga berwarna biru. Elemen pertama dan ketiga telah dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen ketiga berwarna hijau.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen ketiga berwarna hijau dan dua elemen pertama berwarna oranye, mewakili bagian kiri daftar.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru, elemen kedua oranye, dan elemen ketiga hijau. Penunjuk kiri dan kanan mengarah ke elemen kedua.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru, elemen kedua oranye, dan elemen ketiga hijau. Penunjuk kiri dan kanan mengarah ke elemen kedua. Ada dua panah yang menunjukkan elemen pertama dan kedua akan dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna biru, elemen kedua oranye, dan elemen ketiga hijau. Penunjuk kiri dan kanan mengarah ke elemen kedua. Elemen pertama dan kedua telah dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama berwarna oranye, dan elemen kedua serta ketiga berwarna hijau.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, dan ketiga berwarna hijau.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, dan ketiga berwarna hijau. Bagian kanan daftar berwarna oranye.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, dan ketiga berwarna hijau. Elemen pertama bagian kanan berwarna biru. Penunjuk kiri ke elemen kedua bagian kanan dan penunjuk kanan ke elemen terakhir bagian kanan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, dan ketiga berwarna hijau. Elemen pertama bagian kanan berwarna biru. Penunjuk kiri dan kanan ke elemen kedua bagian kanan daftar.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, dan ketiga berwarna hijau. Elemen pertama bagian kanan berwarna biru. Penunjuk kiri ke elemen pertama bagian kanan dan penunjuk kanan ke elemen kedua bagian kanan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, ketiga, dan keempat berwarna hijau, dan elemen kelima serta keenam berwarna oranye.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, ketiga, dan keempat berwarna hijau. Elemen berwarna biru. Penunjuk kiri dan kanan ke elemen terakhir.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, ketiga, dan keempat berwarna hijau. Elemen berwarna biru. Penunjuk kiri dan kanan ke elemen terakhir. Ada dua panah yang menunjukkan elemen kelima dan keenam akan dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Elemen pertama, kedua, ketiga, dan keempat berwarna hijau. Elemen berwarna biru. Penunjuk kiri dan kanan ke elemen terakhir. Elemen kelima dan keenam telah dipertukarkan.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - praktik

Skema daftar dengan angka acak. Semua elemen berwarna hijau karena sudah terurut.

  • Partisi Hoare
    • Geser penunjuk kiri hingga nilai lebih besar dari pivot ditemukan
    • Geser penunjuk kanan hingga nilai lebih kecil dari pivot ditemukan
Struktur Data dan Algoritma di Python

Quicksort - implementasi

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)
Struktur Data dan Algoritma di Python

Quicksort - implementasi

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer
Struktur Data dan Algoritma di Python

Quicksort - implementasi

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]
Struktur Data dan Algoritma di Python

Quicksort - kompleksitas

  • Kasus terburuk: $O(n^2)$
  • Sangat efisien!
    • Rata-rata: $\Theta(n\log{}n)$
    • Terbaik: $\Omega(n\log{}n)$
  • Kompleksitas ruang: $O(n\log{}n)$
Struktur Data dan Algoritma di Python

Ayo berlatih!

Struktur Data dan Algoritma di Python

Preparing Video For Download...