By: Michael Wijaya

Apa itu Algoritma Quick Sort?

Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical (Dalam matematika, urutan leksikografik, biasa dikenal sebagai urutan leksikal atau urutan alfabet, adalah bentuk umum dari urutan alfabet kata yang berdasarkan pada pengurutan huruf depan). Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi (membakukan) data dan menghasilkan output yang dapat dibaca manusia.

Salah satu jenis algoritma sorting adalah Quick Sort. Quick Sort adalah salah satu algoritma pengurutan data yang paling cepat, yaitu dengan membagi list menggunakan sebuah pivot. Quick Sort juga menggunakan rekursif dalam algoritmanya. Data yang kurang dari pivot sudah ditentukan ditaruh disebelah kirinya pivot sedangkan data yang lebih besar dari pivot maka ditaruh disebelah kanan pivot.

#berikut adalah nilai” dari anak” di kelas LB01 urutkanlah dari yang terkecil hingga terbesar (70,55,45,50,30,68,100,98,42,12,54)

array=[70,55,45,50,30,68,100,98,42,12,54]

lbK = []
smD = []
lbB = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
lbK.append(x)
elif x == pivot:
smD.append(x)
elif x > pivot:
lbB.append(x)
a = lbK.sort()
b = lbB.sort()
print(lbK+smD+lbB)

else:
print(‘error’)

output:

[12, 30, 42, 45, 50, 54, 55, 68, 70, 98, 100]

Implementasi Quick Sort di Python

Berikut adalah implementasi Quick Sort dalam bahasa Python.

# Fungsi untuk melakukan partisi

def partition(arr, low, high):

    pivot = arr[high]  # Mengambil elemen terakhir sebagai pivot

    i = low – 1        # Indeks dari elemen yang lebih kecil

 

    for j in range(low, high):

        # Jika elemen saat ini lebih kecil atau sama dengan pivot

        if arr[j] <= pivot:

            i += 1

            # Tukar elemen arr[i] dan arr[j]

            arr[i], arr[j] = arr[j], arr[i]

 

    # Tukar elemen pivot ke posisi yang tepat

    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    return i + 1

 

# Fungsi utama quicksort

def quicksort(arr, low, high):

    if low < high:

        # Pi adalah indeks partisi

        pi = partition(arr, low, high)

 

        # Mengurutkan elemen sebelum dan sesudah partisi

        quicksort(arr, low, pi – 1)

        quicksort(arr, pi + 1, high)

 

# Contoh penggunaan

arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quicksort(arr, 0, n – 1)

print(f”Hasil pengurutan: {arr}”)

 

Penjelasan Implementasi

  1. Fungsi partition(arr, low, high): Fungsi ini bertanggung jawab untuk menempatkan pivot di posisi yang benar dalam array, yaitu memindahkan elemen-elemen yang lebih kecil dari pivot ke sisi kiri dan elemen-elemen yang lebih besar ke sisi kanan. Elemen pivot dipilih dari elemen terakhir dari array (yaitu arr[high]), tetapi teknik lain bisa digunakan untuk memilih pivot.
  2. Fungsi quicksort(arr, low, high): Fungsi ini mengimplementasikan logika utama Quick Sort, yaitu memanggil fungsi partition untuk memecah array dan kemudian melakukan rekursi pada subdaftar di kiri dan kanan pivot.
  3. Contoh penggunaan: Dalam contoh ini, kita memiliki array [10, 7, 8, 9, 1, 5], dan setelah dilakukan pengurutan menggunakan Quick Sort, array tersebut akan menjadi [1, 5, 7, 8, 9, 10].

Memilih Pivot

Pemilihan pivot adalah aspek yang sangat penting dalam Quick Sort. Pilihan pivot yang buruk dapat menghasilkan pembagian yang tidak seimbang pada setiap iterasi, yang meningkatkan waktu eksekusi hingga mencapai O(n2)O(n^2)O(n2). Berikut beberapa strategi umum dalam memilih pivot:

  1. Pivot Terakhir: Elemen terakhir dari array (seperti dalam implementasi di atas).
  2. Pivot Pertama: Elemen pertama dari array.
  3. Pivot Tengah: Elemen tengah dari array.
  4. Pivot Acak: Memilih elemen acak sebagai pivot, yang umumnya mengurangi kemungkinan terburuk O(n2)O(n^2)O(n2) dengan probabilitas tinggi.

Untuk meningkatkan performa dalam skenario terburuk, banyak implementasi Quick Sort modern menggunakan teknik pemilihan pivot acak atau strategi median-of-three yang memilih pivot dari median tiga elemen (elemen pertama, tengah, dan terakhir).

Berikut implementasi Quick Sort dengan pemilihan pivot acak:

import random

 

def partition(arr, low, high):

    # Memilih pivot acak

    pivot_index = random.randint(low, high)

    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]  # Tukar pivot dengan elemen terakhir

    pivot = arr[high]

    i = low – 1

 

    for j in range(low, high):

        if arr[j] <= pivot:

            i += 1

            arr[i], arr[j] = arr[j], arr[i]

 

    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    return i + 1

 

def quicksort(arr, low, high):

    if low < high:

        pi = partition(arr, low, high)

        quicksort(arr, low, pi – 1)

        quicksort(arr, pi + 1, high)

 

arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quicksort(arr, 0, n – 1)

print(f”Hasil pengurutan dengan pivot acak: {arr}”)