Scribd
Unggah
51 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 menyusun elemen-elemen lainnya dengan menjadikan pivot sebagai pembatas antara elemen yang lebih kecil dan lebih besar. Proses pengurutan dilakukan secara rekursif hingga semua elemen terurut. Quick Sort mampu menyelesaikan masalah pengurutan dengan cepat dan hanya memerl

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
51 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 menyusun elemen-elemen lainnya dengan menjadikan pivot sebagai pembatas antara elemen yang lebih kecil dan lebih besar. Proses pengurutan dilakukan secara rekursif hingga semua elemen terurut. Quick Sort mampu menyelesaikan masalah pengurutan dengan cepat dan hanya memerl

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

The divide-and-conquer method enhances the efficiency of Quick Sort by breaking down a large problem into smaller and more manageable sub-problems, solving each recursively . This approach effectively reduces the overall complexity as it partitions the dataset into sections that can be sorted independently, leading to faster sorting times especially with large datasets .

The Quick Sort algorithm has several advantages over other sorting methods. It generally has a time complexity of O(n log n), making it one of the fastest available sorting algorithms . The algorithm is simple, easy to implement, and adapts well to different programming languages, making it efficient and effective . It can also process directly on input data with minimal additional space (in-place sorting), and it handles various types of data, such as numbers and letters, very well .

The effectiveness of a sorting algorithm is typically measured by the amount of memory and time used during execution . Quick Sort is considered one of the fastest sorting algorithms because it generally runs in O(n log n) time complexity, which means it efficiently deals with large datasets. Its divide-and-conquer approach allows it to evenly partition datasets, leading to less overall computational effort .

Recursion is fundamental to Quick Sort's operation as it allows the algorithm to apply the partitioning and sorting process repeatedly to subarrays formed around the pivot . This recursive division is crucial for achieving Quick Sort's characteristic efficiency. However, improper implementation of recursion can lead to performance issues like stack overflow or infinite loops if base cases are not correctly defined .

Quick Sort can occasionally experience disadvantages, such as a potential for a time complexity of O(n²) due to poor pivot selection, although this is rare . Errors in recursive implementation can lead to program crashes. Quick Sort may not be the best choice for small datasets or datasets containing duplicate values, as other sorting algorithms might perform better in these scenarios .

In the Quick Sort algorithm, the pivot element determines the position where the array will be split into two subarrays . The algorithm organizes elements such that all items less than the pivot are on its left, and those greater are on its right. This partitioning allows recursive sorting of the subarrays, making the sort more efficient .

Quick Sort ensures in-place sorting by using indexed swapping to rearrange elements based on the pivot without requiring additional memory for storage of elements . This is beneficial for memory management because it minimizes the best use of auxiliary space, ensuring that the algorithm can handle large data efficiently without exceeding memory limits .

To implement Quick Sort in C++, the basic steps include selecting a pivot element, partitioning the array into two parts with elements smaller than the pivot on the left and larger ones on the right, and then recursively applying the same process to the subarrays. The C++ code involves functions to partition the elements and to recursively sort them by altering their positions accordingly .

Quick Sort is particularly advantageous for sorting large datasets with randomly distributed values, outperforming many other algorithms due to its O(n log n) complexity . While algorithms like Insertion Sort can be more efficient for small or nearly sorted datasets, Quick Sort is preferred for its speed with larger, more complex arrays. However, it may not perform as well with datasets containing many duplicate values where other algorithms like Counting Sort could be more efficient .

Quick Sort can experience a complexity of O(n²) in scenarios where poor pivot selection leads to uneven partitioning. For instance, if the pivot is always selected as the smallest or largest element, the algorithm essentially sorts in a linear fashion rather than dividing the array evenly, making it similar to less efficient sorts like Insertion Sort .

Anda mungkin juga menyukai