“TI
Politala Algoritma dan Pemograman II 2C”
[
Tugas Kuliah ] Algoritma dan Pemograman “Sorting (Buble dan Quick)”
“Sorting
(Buble dan Quick)”
A. Pengertian dan Konsep Pada Buble Sort
Pengurutan
merupakan proses dasar yang ada dalam algoritma dan stuktur data. Terdapat
banyak algoritma pengurutan yang sering digunakan, namun pada tulisan kali ini
akan dibahas mengenai dasar algoritma Bubble Sort. Algortima ini merupakan
algortima pengurutan sederhana dan biasanya dipelajari sebagai pokok bahasan
seputar pengurutan. Algoritma Bubble Sort ini merupakan proses pengurutan yang
secara berangsur-angsur berpindah ke posisi yang tepat karena itulah dinamakan
Bubble yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang
terbesar ke yang terkecil (ascending) atau sebaliknya (descending). Secara
sederhana, bisa didefenisikan algoritma Bubble Sort adalah pengurutan dengan
cara pertukaran data dengan data disebelahnya secara terus menerus sampai dalam
satu iterasi tertentu tidak ada lagi perubahan. Untuk belajar algoritma Bubble
Sort ini kita hanya perlu memahami cara yang digunakan untuk mengurutkan data,
sederhananya algoritma ini menggunakan perbandingan dalam operasi antar
elemennya. Di bawah ini merupakan gambaran dari algoritma Bubble Sort dengan array
“3 1 4 2 8”.
Proses pertama :
(3 1 4 2 8) menjadi (1 3
4 2 8)
(1 3 4 2 8) menjadi (1 3
4 2 8)
(1 3 4 2 8) menjadi (1 3
2 4 8)
(1 3 2 4 8) menjadi (1 3
2 4 8)
Proses kedua :
(1 3 2 4 8) menjadi (1 3
2 4 8)
(1 3 2 4 8) menjadi (1 2
3 4 8)
(1 2 3 4 8) menjadi (1 2
3 4 8)
(1 2 3 4 8) menjadi (1 2
3 4 8)
Proses ketiga :
(1 2 3 4 8) menjadi (1 2
3 4 8)
(1 2 3 4 8) menjadi (1 2
3 4 8)
(1 2 3 4 8) menjadi (1 2
3 4 8)
(1 2 3 4 8) menjadi (1 2
3 4 8)
Jika
kita perhatikan proses diatas, para proses kedua data sudah terurut dengan
benar. Tetapi algoritma Bubble Sort tetap berjalan hingga proses kedua
berakhir. Proses ketiga masih terus berjalan karena pada algoritma Bubble Sort
maksud terurut itu adalah tidak ada satupun penukaran pada suatu proses. Proses
ketiga ini dilakukan untuk verifikasi data. Algoritma Bubble Sort ini mempunyai
kelebihan dan kekurangan, untuk kelebihannya metode ini merupakan metode paling
sederhana untuk mengurutkan data. Selain sederhana, algoritma Bubble Sort mudah
dipahami. Sementara itu, kekurangannya terletak pada efisiensi. Bubble Sort ini
merupakan metode pengurutan yang tidak efisien karena ketika mengurutkan data
yang sangat besar akan sangat lambat prosesnya. Selain itu, jumlah pengulangan
akan tetap sama jumlahnya meskipun data sudah cukup terurut.
B. Contoh Program Pada Buble Sort
#include<iostream>
#include
<conio.h>
using
namespace std;
main()
{
int data[6];
int a, b, c, i;
int buble;
int pilihan;
string fg;
cout<<"Banyak Data Yang Di
Masukkan :";cin>>a;
cout<<endl;
for (i=0; i<a; i++)
{
cout<<"Masukkan Data Ke -
"<<i+1<<" :";cin>>data[i];
cout<<endl;
}
ulang :
cout<<"Pilih Metode Yang
Ingin Digunakan :"<<endl;
cout<<"1.
Ascending"<<endl;
cout<<"2.
Descending"<<endl;
cout<<endl;
cout<<"Masukkan Metode Yang
Dipilih :";cin>>pilihan;
cout<<endl;
if (pilihan ==1)
{
for (i=0; i<a-2; i++)
{
for (c=a-1; c>=i+1; c--)
{
if (data[c] < data[c-1])
{
buble = data[c];
data[c] = data[c-1];
data[c-1] = buble;
}
}
}
cout<<"Data Yang Terurut
Menggunakan Ascending"<<endl;
cout<<endl;
for (i=0; i<a; i++)
{
cout<< "Data ke -
"<<i+1<< " :"<<data[i]<<endl;
}
}
else if (pilihan ==2)
{
for (i=0; i<=a-2; i++)
{
for (c=a-1; c>=i+1; c--)
{
if (data[c] > data[c-1])
{
buble = data[c];
data[c] = data[c-1];
data[c-1] = buble;
}
}
}
cout<<"Data Yang Terurut
Menggunakan Descending"<<endl;
cout<<endl;
for (i=0; i<a; i++)
{
cout << "Data ke -
" <<i+1<< " : "<<data[i]<<endl;
}
}
else
{
cout << "Data Yang Anda
Masukkan Salah "<<endl;
cout << "Jika Anda ingin
mengulang Pilihlah Yes Jika Tidak Pilih Tidak :"; cin>>fg;
cout <<endl;
if (fg =="Y" ||
fg=="T")
{
goto ulang;
}
else
{
cout <<
"Stop"<<endl;
}
}
}
C. Metode Quick Sort
Algoritma quicksort diperkenalkan pertama kali oleh
C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di Computer Journal 5
pada April 1962. Bentuknya yang sederhana, efisien dan efektif dengan cepat
membuatnya menjadi algoritma pengurutan (sorting) yang paling banyak digunakan,
terutama dalam bahasa pemrograman. Berbagai penelitian dan pengembangan telah
banyak dilakukan hingga saat ini. Tercatat peneliti seperti Sedgewick, Bentley,
McIlroy, Clement, Flajolet, Vallee, hingga Martinez, membuat analisis dan
implementasi dari quicksort. Algoritma quick sort mengurutkan dengan sangat
cepat, namun algoritma ini sangat komplex dan diproses secara rekursif.Sangat
memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus
khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan
algoritma quick sort. Quick Sort merupakan suatu algoritma pengurutan data yang
menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini
disebut juga dengan nama partition exchange sort. Untuk memulai irterasi
pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur
sedemikian rupa. Metode Quick sering disebut juga metode partisi (partition
exchange sort). Metode ini mempunyai efektifitas yang tinggi dengan teknik
menukarkan dua elemen dengan jarak yang cukup besar. Metode pengurutan quick
sort dapat diimplementasikan dalam bentuk non rekursif dan rekursif. Berbagai
varian dari quicksort pada intinya berupaya untuk mengembangkan teknik-teknik
pembuatan partisi yang efektif untuk berbagai macam masukan.Hal ini merupakan
bahan yang terus dipelajari hingga kini.Ditambah pula dengan perbaikan dari
segi pemrograman sehingga lebih efisien (seperti mengurangi operasi
pembandingan, pertukaran maupun perulangan). Pada tahun 1998 M.D. McIlroy
membuat tulisan berjudul “A Killer Adversary for Quicksort” yang menguraikan
cara untuk membuat susunan data tertentu (dalam array) hingga operasi
pengurutan menggunakan quicksort mendekati kuadratik O(n2). Cara ini berlaku
untuk setiap varian dari quicksort dengan syarat tertentu.Dikenal juga dengan
istilah antiqsort.
D.
Program yang Berjalan Pada Quick Sort
#include
<iostream>
using
namespace std;
int n;
void
quick_sort(int arr[], int left, int right);
int main()
{
int jmlhbil=5;
cout << "Masukkan jumlah
bilangan : "<<endl; cin>>jmlhbil;
int ar[jmlhbil];
for (int i=0; i<jmlhbil; i++)
{
cout << "Bilangan
ke-"<<i+1<<endl;
cin>>ar[i];
}
quick_sort(ar, 0, jmlhbil-1);
cout << "Data yang telah
diurutkan : "<<endl;
for(int i=0; i<jmlhbil; i++)
{
cout<<ar[i]<<"\n";
}
}
void
quick_sort(int arr[], int left, int right)
{
int i=left, j=right;
int tmp;
int pivot=arr[(left+right)/2];
while (i<=j)
{
while (arr[i]<pivot) i++;
while (arr[j]>pivot) j--;
if (i<=j)
{
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
i++;
j--;
}
}
if(left<j)
quick_sort(arr,left,j);
if (i<right)
quick_sort(arr,i,right);
}
Sumber :
Tidak ada komentar:
Posting Komentar