Scribd
Unggah
105 tayangan4 halaman

Metode Quick Sort dalam C++

Metode Quick Sort merupakan salah satu algoritma pengurutan data yang paling cepat. Quick Sort bekerja dengan memilih satu elemen sebagai pivot dan mengurutkan elemen lain berdasarkan apakah lebih kecil atau lebih besar dari pivot. Proses pengurutan dilakukan secara rekursif hingga semua elemen terurut. Quick Sort memiliki kompleksitas waktu terbaik sebesar O(n log n) dan ruang tambahan yang kecil, sehingga merup

Diunggah oleh

Santa Silalahi
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd
105 tayangan4 halaman

Metode Quick Sort dalam C++

Metode Quick Sort merupakan salah satu algoritma pengurutan data yang paling cepat. Quick Sort bekerja dengan memilih satu elemen sebagai pivot dan mengurutkan elemen lain berdasarkan apakah lebih kecil atau lebih besar dari pivot. Proses pengurutan dilakukan secara rekursif hingga semua elemen terurut. Quick Sort memiliki kompleksitas waktu terbaik sebesar O(n log n) dan ruang tambahan yang kecil, sehingga merup

Diunggah oleh

Santa Silalahi
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd

METODE SORTING QUICK SORT DALAM BAHASA PEMROGRAMAN C++

Santa Maria Sopiana Silalahi


Program study Teknik Informatika, STIKOM Pematangsiantar
Jl. Jend. Sudirman Blok A No. 1-3 Pematangsiantar
Email : santasilalahi14@[Link]

ABSTRAK

Dalam dunia teknologi masa kini, perkembangan ilmu pengetahuan dan teknologi berkembang pesat dan
mulai menghasilkan inovasi-inovasi terbaru. Sorting (pengurutan data) adalah salah satu operasi yang
sangat penting dalam pengolahan data. Algoritma berperan penting dalam dunia pemrograman, sehingga
diperlukan pemahaman dalam konsep dasar pada algoritma. Banyak metode algoritma yang dapat
digunakan dalam penyelesaian suatu permasalahan, baik untuk kasus umum maupun kasus yang lebih
spesifik atau khusus. Masing-masing algoritma memiliki tingkat efektivitas yang berbeda. Keefktivitasan
algoritma diukur dari berapa banyak ruang(memori) dan waktu yang digunakan untuk menjalankannya.
Apabila semakin sedikit ruang dan waktu yang digunkan maka semakin efektif. Masalah pengurutan
sering muncul dalam dunia pemrograman komputer. Banyak metode pengurutan yang dikembangkan dan
ditingkatkan sehingga pengurutan lebih cepat, salah satunya metode Quick Sort. Metode Quick Sort
merupakan metode tercepat dalam pengurutan data.

Kata Kunci : Algoritma, Quick Sort, Data

ABSTRAC
In today’s world of technology, the development of science and technology is growing rapidly
and starting to produce the latest innovations. Sorting is one of the most important operations in
data processing. Algorithms play an important role in the programming world, so an
understanding of the basic concepts of algorithms is needed. Many algorithmic methods can be
used in solving a problem, both for general cases and for more specifik or special cases. Each
algorithm has a different level of effectiveness. The effectiveness of the algorithm is measured by
how muckh space(memory) and time it takes to run it. The less space and time that is used, the
more effective it is. Sequencing problems often arise in the world of computer programming.
Many sorting methods have been developed and improved so that sorting is faster, one of which
is the Quick Sort method. Quick Sort method is the fasted method in sorting data.

Keyword : Quick Sort, Data, Algorithm.

PENDAHULUAN

Pemanfaatan ilmu pengetahuan dan dan efisien. Kebutuhan jumlah ruang dan waktu
teknologi yang berkembang pesat menghasilkan bergantung pada jumlah data yang akan di proses.
inovasi baru harus diseimbangkan dengan Dalam program studi informatika terdapat
kemampuan beradaptasi dengan teknologi tersebut. banyak jenis-jenis algoritma pengurutan yang
Seiiring dengan perkembangan teknologi tersebut, dapat digunakan. Contoh pengurutan data yang
perkembangan jumlah data juga semakin sering dijumpai seperti pengurutan data
bertambah, sehingga dibutuhkan cara pengolahan mahasiswa, nomor absen, nilai, dan banyak lagi.
data yang efektif dan efisien. Pada dasarnya, terdapat dua jenis
Disinilah algoritma berperan penting pengurutan (sorting) data yaitu, pengurutan data
dalam pengurutan data. Algoritma yang baik akan dari yang terkecil hingga yang terbesar (ascending)
menghasilkan output yang baik, terstruktur, efektif dan pengurutan data menurun, yaitu pengurutan
dari yang terbesar hingga yang terkecil devide-and-conqueror. Untuk mempertinggi
(descending). efektifitas dari metode ini, digunakan teknik
Dalam penulisan ini, penulis menggunakan menukarkan dua elemen dengan jarak yang
metode Quick Sort sebagai percobaan dan cukup besar.
mengaplikasikannya dalam bahasa pemrograman Algoritma ini mengamil salah satu elemen
C++. acak yang disebut dengan pivot lalu menyimpan
semua elemen yang lebih kecil di sebelah kiri pivot
METODE PENELITIAN dan elemen yang besar di sebelah kanan pivot. Hal
ini dilakukan secara rekursif sampai semua elemen
Metode penelitian yang digunakan penulis telah berurut.
adalah pengumpulan data dari berbagai jurnal dan Algoritma Quick Sort :
pencarian di internet yang membahas tentang  Pilih salah satu elemen secara acak, bebas
metode pengurutan data (sorting). disebelah kiri, kanan atau tengah.
Setelah itu penulis melakukan percobaan  Pindahkan semua elemen yang lebih kecil
atau simulasi menggunakan bahasa C++ guna ke sebelah kiti dan yang lebih besar ke
mengimplementasikan dan mendapatkan hasil kanan pivot. Apabila elemen bernilai
yang diinginkan. sama, bisa disimpan di kiri atau kanan.
 Setelah itu lakukan sort secara rekursif
terhadap sub-array sebelah kiri dan sebalah
PEMBAHASAN kanan pivot.
A. Algoritma Quick Sort Contoh program pengurutan data dengan quick sort
dalam bahasa program C++:
Menurut Saputra, dkk (2010:1) menjelaskan
bahwa algoritma adalah deretan instruksi yang #include<bits/stdc++.h>
jelas untuk memecakan masalah, yaitu untuk using namespace std;
memperoleh keluaran yang diinginkan dari int partition(int *a,int start,int end)
suatu masukan. {
Menurut Yahya (2014:135) Sorting adalah int pivot=a[end];
proses pengurutan data yang sebelumnya
disusun secara acak atau tidak teratur menjadi
urut dan teratur menurut suatu aturan tertentu. int P_index=start;
Menurut Saputra, dkk (2010:1) juga int i,t;
menjelaskan bahwa algoritma sorting
didefinisikan sebagai algoritma pengurutan
for(i=start;i<end;i++)
sejumlah data berdasarkan nilai kunci tertentu.
{
Pengurutan dapat dilakukan dari nilai terkecil
if(a[i]<=pivot)
ke nilai terbesar (ascending) atau sebaliknya
{
(descending).
t=a[i];
algoritma Quick Sort merupakan algoritma
a[i]=a[P_index];
yang membandingkan suatu elemen (pivot) dengan
a[P_index]=t;
elemen yang lain dan menyusunnya sedemikian
P_index++;
rupa sehingga elemenelemen lain yang lebih kecil
}
daripada pivot tersebut terletak di sebelah kirinya
}
dan elemenelemen lain yang lebih besar daripada
pivot tersebut terletak di sebelah kanan. Sehingga
t=a[end];
dengan demikian telah terbentuk dua sublist kiri
a[end]=a[P_index];
dan sublist kanan dari pivot.
a[P_index]=t;
Quick Sort merupakan pengurutan data yang
menggunakan pemecahan data menjadi partisi-
partisi, sehingga metode quick sort ini dapat juga
disebut dengan partition exchange sort. return P_index;
Metode ini diperkenalkan pertama kali }
void Quicksort(int *a,int start,int end)
oleh C.A.R. Hoare pada tahun 1962. Quick
{
Sort adalah algoritma sorting dengan metode
if(start<end)  Merupakan metode yang paling tercepat
{ dalam menyelesaikan permasalahan
int P_index=partition(a,start,end); pengurutan data.
Quicksort(a,start,P_index-1);  Dapat melakukan proses langsung pada
Quicksort(a,P_index+1,end); input (in-place) dengan tambahan sedikit
} ruang atau memori.
}  Bekerja dengan baik dalam berbagai jenis
int main() input data baik berupa angka maupun
{ huruf.
int n;
cout<<"Masukkan jumlah data: "; Kekurangan dari quick sort:
cin>>n;  Apabila terjadi sedikit kesalahan dalam
int a[n]; penulisan program dapat membuatnya
cout<<"Masukkan data ke:\n"; bekerja tidak beraturan.
for(int i=0;i<n;i++)  Memiliki kompleksitas O(n2), namun hal
{ ini sangat langka terjadi.
cin>>a[i];  Dalam penerapansecara rekursif, apabila
} terjadi kesalahan dapat memacetkan
Quicksort(a,0,n-1); program.
cout<<"Hasil input Data Quick Sort :\n";
for(int i=0;i<n;i++)
{
cout<<a[i]<<" "; KESIMPULAN
}
return 0;
} Metode pengurutan data memang cukup
beragam, namun tentunya dalam proses ada
Tampilan outputnya : metode yang tercepat. Masing-masing dari metode
tesebut memiliki kelebihan dan kekurangan. Dalam
pembuatan program komputer tidak lepas dari
algoritma, karena program yang dibuat sangat
kompleks. Program dapat dibuat tanpa
menggunakan algoritma, akan tetapi program yang
dihasilkan memiliki akses yang lambat atau
memakai banyak memori.
Dari percobaan di atas dapat kita
simpulkan bahwa metode Quick Sort memakan
sedikit ruang dan waktu pemrosesan yang terbilang
cukup cepat, sehingga metode ini menjadi metode
yang paling cepat dalam pengurutan data(sorting)
dibandingkan dengan metode lainnya. Meskipun
begitu, algoritma quick sort ini tidak selalu
menjadi pilihan yang terbaik.
Algoritma Quicksort lebih sesuai untuk
digunakan pada data yang berjumlah banyak
Gambar 1. Output data Quick Sort dan memiliki nilai yang terdistribusi secara acak
karena proses pengurutan data lebih cepat. Namun
metode ini memiliki kekurangan jika mengurutkan
Kelebihan dari Quick Sot : data yang sedikit dan memiliki data kembar.
 Metode quick sort secara umum memiliki
kompleksitas O(n log n).
 Memiliki algoritma yang sederhana dan
mudah diterapkan pada berabagai bahasa
pemrograman komputer dan sangat efisien
dan efektif.
DAFTAR PUSTAKA

Firmansyah. Alfian. 2019. “PERFORMA


PADA ALGORITMA INSERTION SORT DAN
QUICK SRT”. Jurnal.
Waruwu. Sabarudi, dkk. 2019.
“PENERAPAN ALGORITMA QUICK PRIVOT
SORT DAN RADIX SORT PADA DATA BUKU”.
Jurnal.
Arifin. RW. Setiyadi. Didik. 2020.
“ALGORITMA METODE PENGURUTAN
BUBBLE SORT DAN QUICK SORT DALAM
BAHASA PEMROGRAMAN C++”. Jurnal.
Rahayuningsih. PH. 2016. “Analisis
Perbandingan Kompleksitas Algoritma
Pengurutan Nilai (Sorting)”. Jurnal
Audy. 2015. “Komparasi Algoritma Quick
Sort dan Bucket Sort Pada Pengurutan Data
Integer”. Jurnal
Rizkirahadiansyah. 2018. “Macam-Macam
Metode Sorting”.
[Link]
macam-macam-metode-sorting/ (Diakses tanggal
10 Juni 2021.
Mustakim. Hendri. 2015. “SORTING
(STRUKTUR DATA).
[Link]
ng/ (Daikses tanggal 12 Juni 2021)
Hardifal. Elang. 2018. “Contoh Program
Algoritma Quick Sort C++ Sederhana”.
[Link]
[Link] (Diakses
tanggal 12 Juni 2021)

Common questions

Didukung oleh AI

Kompleksitas waktu Quick Sort rata-rata adalah O(n log n) namun bergantung pada pemilihan pivot dan distribusi data. Jika data sudah terurut atau penempatan pivot tidak ideal, kompleksitas dapat meningkat menjadi O(n^2) karena pembagian yang tidak merata. Distribusi data secara acak lebih memungkinkan pivot memilih posisi tengah, menjaga keseimbangan partisi dan efisiensi waktu.

Quick Sort menggunakan elemen yang disebut pivot untuk membagi array menjadi dua sub-array. Elemen yang lebih kecil dari pivot ditempatkan di sebelah kiri, sedangkan elemen yang lebih besar di sebelah kanan. Proses ini dilakukan secara rekursif sampai seluruh elemen terurut. Pemilihan pivot dan pembagian yang efektif memastikan bahwa keseluruhan pengurutan dapat dilakukan dengan cepat dan efisien.

Metode pengurutan rekursif pada Quick Sort dimulai dengan memilih elemen pivot dan membagi array menjadi dua sublist berdasarkan nilai pivot. Array kemudian diurutkan secara rekursif pada kedua sublist tersebut, yaitu sublist kiri dan sublist kanan dari pivot. Pemanggilan rekursif berhenti ketika sublist berukuran satu atau kosong, yang berarti elemen telah terurut secara keseluruhan. Teknik rekursif memastikan bahwa pengurutan dilakukan secara efisien tanpa perlu ruang tambahan yang signifikan selain panggilan fungsi pada stack.

Quick Sort dianggap sebagai metode pengurutan tercepat karena memiliki kompleksitas rata-rata O(n log n) yang membuatnya efisien untuk data besar dengan elemen acak. Algoritma ini mudah diterapkan dalam berbagai bahasa pemrograman dan dapat menangani berbagai jenis data dengan baik. Namun, dalam kasus terburuk kompleksitasnya bisa mencapai O(n^2), tetapi keadaan ini jarang terjadi. Algoritma ini memproses elemen secara langsung pada input (in-place) sehingga hanya membutuhkan sedikit ruang tambahan.

Quick Sort menggunakan pendekatan divide and conquer dalam menyelesaikan masalah pengurutan data. Algoritma ini membagi array menjadi sublist lebih kecil menggunakan pivot, kemudian secara rekursif mengurutkan setiap sublist tersebut. Teknik ini memanfaatkan pembagian data yang efektif, sehingga mempercepat proses pengurutan keseluruhan dengan melakukan operasi pada partisi data lebih kecil secara paralel atau berurutan.

Kesalahan implementasi pada algoritma Quick Sort, terutama dalam aspek rekursi, dapat menyebabkan program tidak bekerja secara efisien atau bahkan macet. Rekursi yang tidak terkontrol dapat mengakibatkan overhead memori karena adanya panggilan berulang yang tidak berhenti atau berakhir, menguras sumber daya sistem, dan menyebabkan runtime error. Kesalahan dalam penanganan base case atau perburuan pivot yang tidak tepat juga bisa mengganggu operasi normal dari Quick Sort.

Quick Sort menonjol karena dapat melakukan pengurutan secara in-place, yang berarti tidak memerlukan ruang tambahan yang signifikan selain dua lokasi memori untuk menyimpan pivot dan pertukaran sementara. Ini berbeda dari algoritma lain seperti Merge Sort yang membutuhkan tambahan ruang memori untuk array atau sub-array tambahan. Pendekatan Quick Sort yang hemat ruang membantu dalam mengoptimalkan pemakaian memori terutama pada dataset besar.

Kelebihan Quick Sort antara lain adalah kompleksitas rata-rata O(n log n), algoritmanya sederhana dan mudah diterapkan, dan metode ini sangat efisien dalam hal pemanfaatan ruang karena in-place. Selain itu, Quick Sort bekerja baik dengan input data yang bervariasi, mulai dari angka hingga huruf. Sedangkan O(n^2) hanya terjadi pada kasus-kasus tertentu yang jarang terjadi, membuatnya umum digunakan saat pengurutan data besar.

Algoritma Quick Sort dapat menjadi kurang efisien ketika digunakan pada data yang sudah hampir terurut atau ketika semua elemen dalam array sama. Dalam situasi ini, kompleksitas waktu bisa memburuk menjadi O(n^2) karena pembagian yang tidak merata dari elemen oleh pivot. Oleh karena itu, Quick Sort lebih cocok untuk data dengan nilai yang terdistribusi secara acak dan berjumlah besar.

Quick Sort mudah diterapkan dalam berbagai bahasa pemrograman karena algoritmanya sederhana, yaitu berfokus pada penggunaan pivot untuk membagi dan mengurutkan sublist. Kode implementasi Quick Sort, seperti dalam C++, hanya membutuhkan dasar pengulangan, kontrol aliran, dan rekursi, yang merupakan fitur dasar di banyak bahasa pemrograman komputer. Hal ini membuatnya fleksibel dan modular saat diadaptasi ke dalam beragam sistem dan aplikasi.

Anda mungkin juga menyukai