KATA PENGANTAR

Puji dan syukur kepada Tuhan Yang Maha Esa yang menghadiahkan kita dengan kesehatan
dan anugerah sehingga tersusunnya makalah sederhana ini. Tujuan utama kami membuat
makalah ini adalah mendiskusi dan mengembangkan kemampuan kerjasama tim kami dalam
mempelajari suatu permasalahan dan belajar memecahkannya. Kami yakin dengan
mempelajari dan membagikan hasil makalah yang bertema algoritma quick sort ini akan
bermanfaat untuk kedepannya. Kami menyadari bahwa makalah kami tak jauh dari sekedar
puing puing kaca yang berusaha disusun kembali dengan begitu polosnya, kami dengan
ikhlas lapang dada dan ikhlas kritik dan saran yang positif untuk perkembangan kami ke
depannya. Kami penyusun berharap makalah ini dapat bermanfaat untuk tujuan
pembelajaran. Medan, 16 Februari 2025 Penyusun i ii DAFTAR ISI KATA
PENGANTAR ............................................................................................... i I.
PENDAHULUAN ............................................................................................... 1 1.1. Definisi
......................................................................................................... 1 1.2.
Ilustrasi ......................................................................................................... 2 II.
PEMBAHASAN ................................................................................................ 4 2.1.
Program ........................................................................................................ 4 2.2.
Penjelasan ..................................................................................................... 5 III.
PENUTUP ......................................................................................................... 7 3.1.
Kesimpulan ................................................................................................... 7 DAFTAR
PUSTAKA .............................................................................................. 8 I.
PENDAHULUAN 1.1. Definisi Quick sort adalah metode pengurutan atau sorting yang
dikenal sangat efisisen dalam nengurutkan deretan data dalam array. Quick sort merupakan
metode pngurutan yang menggunakan konsep seperti pembagian partisi, oleh karena itu
dikenal sebagai partition exchange sort atau jika diterjemahkan adalah penyortiran pertukaran
partisi. Secara sederhana, partition exchange sort merupakan metode penyortiran atau
penyaringan atau teknik memperkecil data yang dipilih dengan melakukan pertukaran antar
partisi sehingga menghasilkan urutan yang sesuai antar partisi. Metode ini sendiri ditemukan
oleh Charles Antony Richard Hoare (1962) seorang ilmuwan komputer berkebangsaan
Inggris. Pada awal tahun 1960-an, beliau bekerja di salah satu universitas Rusia yakni
University of Moscow dan tertarik untuk mencari tahu metode pengurutan data yang lebih
efisien dan cepat. Kala itu, metode pengurutan seperti bubble sort dan insertion sort adalah
metode yang digunakan oleh para ahli komputer tetapi kedua metode ini tidak cukup efisisen
terutama jika dihdapkan dengan sekumpulan data yang besar. Keduanya cenderung akan
melakukan eksekusi yang lambat. Metode quick sort bekerja dengan membagi dua partisi
menjadi dua bagian setelah menentukan satu pivot dan begitu seterusnya sampai pada sub-
sub partisi berikutnya. Dengan metode ini, sebuah masalah akan dipecah menjadi beberapa
bagian kecil sehingga memudahkan kita untuk melakukan pengurutan data. 1 1.2. Ilustrasi
Metode quick sort cukup mudah jika digambarkan dengan sederhana. Membagi masalah
besar menjadi beberapa masalah kecil, itu bisa dijadikan bahasa sederhana untuk
mendeskripsikannnya. Sebelum masuk ke dalam contohnya, kita perlu mengenal apa itu pivot
?. Pivot adalah elemen atau data pada array yang dijadikan titik tumpu dalam membagi data-
data lainnya menjadi dua bagian dan berguna untuk membagi elemen-elemn yang lebih kecil
disbanding pivot (kiri) dan elemen-elemen yang lebih besar (kanan). Mari kita masuk ke
contoh dan pembahasan. 3 4 2 9 8 6 5 7 Mari perhatikan deretan angka di atas, anggap saja
mereka adalah sekumpulan data yang diletakkan di array X. Nah sekarang tugas kita adalah
untuk membuat mereka menjadi tersusun secara ascending berarti kita perlu melakukan
sorting dan kita menggunakan metode yang saat ini kita seang bahas yaitu quick sort method.
Hal pertama yang perlu kita lakukan yaitu memilih pivot. Dalam quick sort, teknik memilih
pivot bisa secara acak tapi biasanya memilih elemen paling ujung atau paling tengah. 3 4 2 6
5 7 9 8 Pada kasus di atas, kita akan memilih angka 7 sebagai pivot dan kemudian elemen
lainnya yaitu (3, 4, 2, 9, 8, 6, 5) akan dipecah menjadi dua bagian yaitu sebelah kiri adalah
elemen yang lebih kecil dari pivot (7) dan sebelah kanan adalah elemen yang lebih besar dari
pivot (7). Metode inilah yang disebut dengan partition exchange. 2 2 3 4 6 5 7 8 9 Nah
sekarang sudah terbagi menjadi 2 partisi, selanjutnya kita perlu memilih pivot pada masing-
masing partisi. Pada partisi kiri (hijau) adalah elemen-elemen yang lebih kecil dari pada pivot
(7) dan dalam partisi ini kita pilih 2 sebagai pivot. Kemudian di partisi kanan (oranye) kita
pilih 9 sebagai pivot. Perhatikan! pada partisi kiri (hijau), elemen 2 sebagai pivot nah elemen-
elemen pada partisi tersebut yakni (3, 4, 2, 6, 5) berubah menjadi (2, 3, 4, 6, 5) alias elemen
(3, 4, 6, 5) sebagai elemen yang lebih dari dari pivot (2) bergeser ke kanan dan dibagian kiri
partisi menjadi kosong () karena tidak ada angka yang lebih kecil dari pada pivot (2).
Kemudian pada partisi kanan (oranye) dengan 9 sebagai pivot maka otomatis 8 bergeser ke
kiri karena lebih kecil. Maka partisi kanan berakhir di pivot 9. Pada partisi kiri (hijau)
sekarang menjadi 2 sub array lagi yaitu (2) dan (3, 4, 6, 5) dan perlu untuk di-sort lagi. 2 3 4
5 6 7 8 9 Pada partisi kanan (3, 4, 6, 5) kita ambil elemen 6 sebagai pivot. Dengan begitu dari
yang awalnya (3, 4, 6, 5) menjadi (3, 4, 5, 6) karena 6 adalah elemen terbesar dari 4 elemen
dalam partisi tersebut maka sekarang data telah terurut dengan sempurna. 3 4 II.
PEMBAHASAN 2.1. Program Quick sort adalah metode pengurutan data atau elemen pada
array yang juga dikenal sebagai partition exchange sort. Metode yang efisien dan dianggap
paling cepat dalam mengeksekusi data. Berikut contoh program yang menggunakan metode
quick sort algorithm. Code: #include using namespace std; int partition(int arr[], int low, int
high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <=
pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } void
quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Rekursi pada kiri quickSort(arr, pi + 1, high); // Rekursi pada
kanan } } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << "
"; } cout << endl; } int main() { int arr[] = {11, 15, 12, 14, 17}; int n = sizeof(arr) /
sizeof(arr[0]); cout << "Array sebelum diurutkan: "; printArray(arr, n); quickSort(arr, 0, n -
1); cout << "Array setelah diurutkan: "; printArray(arr, n); return 0; } Output: 2.2. Penjelasan
Program di atas adalah salah satu contoh metode quick sort, dengan diberikan sebuah array
yang memiliki indeks 0-4 kemudian terdapat fungsi partition untuk menentukan pivot dan
mengatur elemen-elemen yang lebih dan lebih dari pivot berada di posisinya. Kemudian ada
fungsi quickSort yaitu untuk membagi array menjadi 2 partisi. Pada program di atas, pivot
adalah elemen paling kanan (arr[high]). 5 Keterangan: Low = [0]; High = [4]; i = low-1=0-
1=-1; Iterasi 1 Pivot = [17] (indeks keempat adalah elemen 17) int pivot = arr[high] = [4] for
j=0; j<=[4]){ i++; swap(arr[i], arr[j] (selama j=0 tidak lebih besar dari 4 alias selama
indeksnya masih belum sampai ke indeks keempat alias pivot yaitu 17 maka perulangan akan
terus berlanjut sampai selesai, contoh j=0 dan lebih dari kecil dari 4 maka akan masuk ke
percabangan if yaitu jika arr[0] yakni dalam kasus ini adalah elemen 11 lebih kecil atau sama
dengan pivot(17) maka i akan bertambah 1 sehingga menjadi -1+1 = 0. Jadi variabel i adalah
variabel yang mewakili partisi yang lebih kecil dari pivot. Karena arr[0] atau 11 < pivot [17]
maka terjadi swap atau pertukaran atau pergeseran antara arr[i] dan arr[j] yaitu arr[0] dan
arr[0] atau antara 11 dan 11. Begitu seterusnya sampai pada j=3 atau iterasi ke-empat. Tetap
akan berada pada posisi yang sama karena semua angka yang lebih kecil dari pivot (17)
berada di bagian kiri. 6 III. PENUTUP 3.1. Kesimpulan Quick sort adalah metode pengurutan
yang dikenal efisisen dan cepat dalam dunia komputasi. Metode ini berfokus pada titik tumpu
atau pivot untuk menarik deretan elemen lainnya membentuk urutan yang sesuai. Dalam
quick sort sendiri, dibagi menjadi 2 partisi yaitu kiri dan kanan dan memperkecil
kemungkinan. 7 DAFTAR PUSTAKA Saputro, W. T. (2018). Kompleksitas Algoritma
Quick Sort Guna Menemukan Efisiensi Waktu dan Memori. Jurnal INTEK Vol.1 Nomor 1,
6. ALGORITMA PENGURUTAN (QUICK SORT). (n.d.). Retrieved from Politeknik
Elektronika Negeri Surabaya: [Link] Nasihin, S. (n.d.). contoh
program metode quick sort dan penjelasannya. Retrieved from [Link]
[Link]/ Wijaya, M. (n.d.). Algoritma Quick Sort di Python. Retrieved from
[Link]. 8 9