Algoritma yang membagi daftar (list) menjadi dua bagianyang menggunakansebuah pivotatauacuanadalahalgoritma Quick Sort.
 

Pembahasan

Algoritma pengurutan data Quick Sortadalah salah satu algoritma yang berdasarkan pada prinsip“Divide and Conquer“. Contoh algoritma lain yang berprinsip “Divide and Conquer“ antara lain adalah Merge Sort, dan algoritma pencarian Binary Search.

Pada algoritma Quick Sort, sebuah elemen dipilih dari daftar (list) yang ingin diurutkan. Elemen tersebut dinamakan elemen pivot. Lalu, daftar atau list dibagi/dipartisi di sekitar pivot.

Terdapat beberapa cara pemilihan pivot untuk Quick Sort, yaitu:

• Selalu memilih elemen pertama dari list sebagai pivot.
• Selalu memilih elemen terakhir dari list sebagai pivot.
• Memilih elemen acak sebagai pivot.
• Memilih elemen ”median“ (elemen tengah) sebagai pivot.

Proses utama dari algoritma Quick Sort adalah pembuatan dan pengolahan partisi array/list. Kita sebut saja sebagai .  Yang dilakukan oleh secara garis besar adalah:

1. Diberikan array/list dan sebuah elemen x dari array/list tersebut sebagai pivot.
2. Meletakkan x pada posisi yang tepat dalam sebuah array/list terurut.
3. Memposisikan semua elemen yang lebih kecil dari x, pada posisi sebelum x.
4. Memposisikan semua elemen yang lebih besar dari x, pada posisi setelah x.

____________

Contoh Algoritma Quick Sort dalam Notasi Algoritmik

Berikut ini adalah contoh notasi algoritmik dari algoritma Quick Sort secara rekursif, dengan selalu memilih elemen terakhir sebagai pivot.

procedure QuickSort(arr: array of NumericType; low, high: Integer)
{***
Input: array, indeks terkecil (low), dan indeks terbesar (high).
K. Awal: array belum terurut.
K. Akhir: array sudah terurut.
***}

Kamus Data:
   p: Integer

Algoritma:
   if low < high then
      { p adalah indeks partisi. }
       p ← partisi(arr, low, high)
       { Untuk elemen-elemen yang lebih kecil dari pi: }
       QuickSort(arr, low, p – 1)
       { Untuk elemen-elemen yang lebih besar dari pi: }
       QuickSort(arr, p + 1, high)
   end if
____________

function partisi(arr: array of NumericType; low, high: Integer)
{***
- Memilih elemen terakhir sebagai pivot.
- Memposisikan pivot pada posisi yang benar
 dalam array yang sudah terurut.
- Memposisikan semua elemen yang lebih kecil
 dari pivot di sebelah kiri pivot.
- Memposisikan semua elemen yang lebih besar
 dari pivot di sebelah kanan pivot.
***}

Kamus Data:
   pivot: NumericType
   i, j: Integer

Algoritma:
   pivot ← arr[high]
   i ← low – 1
   for j ← low to (high – 1) do
       if arr[j] < pivot then
           { inkrementasi i }
           i ← i+1
           swap(arr[i], arr[j])
       end if
   end for
   swap(arr[i+1], arr[high])
   return (i+1)
____________

Contoh Kasus Pengurutan dengan Quick Sort
(versi pivot pada elemen terakhir)

Diberikan daftar/list dalam bentuk array:

• arr = [3, 6, 5, 4, 2]
• Asumsi: array adalah zero-based array (indeks pertama = 0)

Eksekusi perintah:

QuickSort(arr, 0, 4)
⇒ 0 < 4, maka:

▪ p = partisi(arr, 1, 5)
   ▪ pivot = 2; i = –1
   ▪ Iterasi j = 0 to 3:
       ▪ j = 0: 3 > 2, maka i tetap
       ▪ j = 1: 6 > 2, maka i tetap
       ▪ j = 2: 5 > 2, maka i tetap
       ▪ j = 3: 4 > 2, maka i tetap
   ▪ swap(arr[0], arr[4])
      ⇒ arr = [2, 6, 5, 4, 3]
   ▪ return –1+1 = 0
⇒ p = 0

▪ QuickSort(arr, 1, –1)
⇒ 1 > –1, keluar dari prosedur.

▪ QuickSort(arr, 1, 4)
⇒ 1 < 4, maka:
   ▪ p = partisi(arr, 1, 4)
       ▪ pivot = 3; i = 0
       ▪ Iterasi j = 1 to 3:
           ▪ j = 1: 6 > 3, maka i tetap
           ▪ j = 2: 5 > 3, maka i tetap
           ▪ j = 3: 4 > 3, maka i tetap
       ▪ swap(arr[1], arr[4])
          ⇒ arr = [2, 3, 5, 4, 6]
       ▪ return 0+1 = 1
    ⇒ p = 1
   ▪ QuickSort(arr, 1, 0)
       ⇒ 1 > 0, keluar dari prosedur.
   ▪ QuickSort(arr, 2, 4)
    ⇒ 2 < 4, maka:
      ▪ p = partisi(arr, 2, 4)
           ▪ pivot = 6; i = 1
           ▪ Iterasi j = 2 to 3:
               ▪ j = 2: 5 < 6, maka i = 2
                 ⇒ swap(arr[2], arr[2])
                 ⇒ arr = [2, 3, 5, 4, 6]
               ▪ j = 3: 4 < 6, maka i = 3
                 ⇒ swap(arr[3], arr[3])
                 ⇒ arr = [2, 3, 5, 4, 6]
           ▪ swap(arr[4], arr[4])
              ⇒ arr = [2, 3, 5, 4, 6]
           ▪ return 3+1 = 4
        ⇒ p = 4
       ▪ QuickSort(arr, 2, 3)
        ⇒ 2 < 3, maka:
          ▪ p = partisi(arr, 2, 3)
               ▪ pivot = 4; i = 1
               ▪ Iterasi j = 2 to 2:
                   ▪ j = 2: 5 > 4, maka i tetap
               ▪ swap(arr[2], arr[3])
                ⇒ arr = [2, 3, 4, 5, 6]
               ▪ return 1+1 = 2
                ⇒ p = 2
           ▪ QuickSort(arr, 2, 1)
            ⇒ 2 > 1, keluar dari prosedur.
           ▪ QuickSort(arr, 3, 3)
            ⇒ 3 = 3, keluar dari prosedur.

SELESAI.

∴ Daftar/list yang terurut:
arr = [2, 3, 4, 5, 6]
____________

Detail Jawaban

Mata Pelajaran: Informatika
Kelas: 10 (X)
Materi: Berpikir Komputasional - Pengurutan (Sort)
Kode Kategorisasi: 11.10.2