Contoh Program Algoritma Quick Sort C++ beserta penjelasan

Contoh Program Algoritma Quick Sort C++ – ada banyak sekali algoritma sorting yang bisa kita gunakan dalam dunia pemrograman, seperti bubble sort, insertion sort, dan quick sort. kali ini kita akan berfokus untuk membahas quick sort.

Penjelasan algoritma quick sort

algoritma quick sort adalah salah satu algoritma sorting modern yang cukup populer.

metode dari algoritma ini adalah divide and conquer (bagi dan kuasai) dimana sebuah List akan dibagi menjadi 2 bagian berdasarkan pivot, yaitu elemen yang lebih kecil dari pivot dan elemen yang lebih bersar dari pivot.

lalu elemen tersebut dibagi kembali dengan mengguanakn pivot baru sampai semua elemen berhasil di sorting.

Cara pemilihan pivot.

Pivot adalah elemen krusial dalam algoritma quick sort. jika salah memilihnya, maka algoritma yang dijalankan tidak akan secepat yang kita inginkan. jadi dengan kata lain, pivot ini menentukan performa dari algoritma ini, ada 3 cara memilih pivot, yaitu:

• Pivot berasal dari elemen pertama atau akhir dari sebuah list. Pivot jenis ini bisa kita gunakan apaliba List yang akan disusun memiliki angka yang benar benar acak. dan sebaliknya pivot jenis ini sangat buruk jika kita memiliki list yang sebagian/ sepenuhnya sudah tersusun.
• Pivot dipilih secara acak, pivot jenis ini sering digunakan bila kita tidak mengenal List yang akan di susun, hasilnya pun akan random, terkadang performanya baik, namun terkadang performanya juga buruk.
• Pivot berasal dari median tabel. cara ini yang paling sering digunakan, karena pivot ini bersifat seimbang dimana semua elemen akan dibagi rata dan hasilnya pun cukup baik untuk data yang sebagian sudah di sort ataupun semua data masih acak.

Penjelasan algoritma quick sort.

kali ini kita akan menggunakan pivot median dari sebuah list.

anggap saja kita memiliki list sebagai berikut:

di dalam tersebut, terdapat 8 angka. berarti kita memiliki 2 pilihan dalam memilih pivot, yaitu 3 dan 8. namun saat kita membagi bilangan bulat, biasanya angka akan dibulatkan ke bawah, yang berarti kita akan memilih index ke 4 yaitu angka 3

selanjutnya kita akan memecah List tersebut menjadi 2 bagian, yaitu angka yang lebih kecil dari pivot dan angka yang lebih besar dari pivot, dengan cara.

pertama kita menyimpan angka pivot sebagian acuan, dan mengabaikannya. disini, anggap saja pivot berada di ujung list.

selanjutnya kita akan menentukan angka low dan angka high, angka low berasal dari index list paling kiri(2), dan high berasal dari index list paling kanan (1).

setelah itu kita membandingkan, apakah low lebih besar dari pivot? dan high lebih kecil dari pivot? jika iya maka kita akan berhenti dan melakukan pertukaran.

contoh, 6 lebih besar dari pivot, dimana seharusnya angka disebelah kiri lebih kecil dari pivot, begitupun angka 1.maka disini kita melakukan pertukaran.

selanjutnya, angka 5 lebih besar dari pivot, dan angka 0 lebih kecil dari pivot, maka lakukan pertukaran kembali.

karena index ke low sudah lebih kecil dibanding index ke high, maka looping selesai dan pivot sudah menempati posisi semestinya, yaitu berada di list index ke low.

selanjutnya, kita akan melakukan rekursiv dan mengulang kembali prosesnya di masing masing bagian( bagian kurang dari pivot dan lebih dari pivot). disini saya akan menampilkan bagian lebih dari pivot.

disini, kita kembali memilih pivot, yaitu 7.

lalu kita kembali mengesampingkan pivot.

lalu, kita melakukan perbandingan kembali angka high dan low. maka angka 6 dan 8 bertukar posisi.

karena angka ke low sudah lebih kecil dibanding angka high, maka looping selesai dan pivot bisa menempati posisi list ke low.

baca juga: contoh program algoritma bubble sort c++

kelebihan algoritma quick sort

• karena sorting langsung dilakukan di array asli, maka tidak memerlukan memory tambahan.
• performanya tinggi

baca juga: Contoh program algoritma Merge Sort C++

Kelemahan algoritma quick sort

• jika salah memilih pivot, maka algoritmanya akan sangat buruk.
• sulit untuk dimengerti.

baca juga: contoh program algoritma Insertion Sort C++

Contoh program quick sort c++

Penjelasan

Line 4-8 : ini adalah sebuah function yang nanti akan digunakan untuk menampilkan semua data yang ada di dalam array.

Line 10-30 : disini proses sorting terjadi, dimana pertama kita akan memilih pivot di ujung list. dan membandingkan setiap angka dari sebelah kiri dan kanan, dimana jika angka lebih kecil dari pivot maka ia akan ditempatkan di sebelah kiri dan jika lebih besar maka akan ditempatkan disebelah kanan. serta kita akan mereturn pivot(angka paling kanan sebagai acuan proses selanjutnya)

Line 32-42 : disini kita akan membuat function recursiv, pertama kita akan melakukan proses pivot jika angka masih belum tersoting secara ascending, maka kita akan terus menjalankan functionnya hingga semua angka terurut sempurna.

Line 47-52 : disini kita menyiapkan array untuk menampung inputan dari user dengan inputan banyak array yang akan di sorting.

Line 56-60 : Disini kita menginputkan seluruh data mulai dari array[0] hingga array ke n.

Line 61-63 : Disini kita hanya tinggal menjalankan fungsi quick sort dan menampilkannya menggunakan function yang telah kita buat sebelumnya.

Output

itulah Contoh program algoritma Quick Sort beserta penjelasannya di c++, semoga bermanfaat