SORTING
PENDAHULUAN
- Pengurutan data dalam struktur data sangat penting terutama untuk data yang beripe data numerik ataupun karakter.
- Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
- Pengurutan (Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
DEKLARASI ARRAY UNTUK SORTING
Deklarasikan secara global:
int data[100];
int n; //untuk jumlah data
Prosedur Tukar 2 Buah Data:
void tukar(int a,int b){
int tmp;
tmp = data[a];
data[a] = data[b];
data[b] = tmp;
}
Bagian-bagian Sorting :
BUBBLE SORT
- Metode sorting termudah
- Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti
gelembung yang keluar dari sebuah gelas bersoda.
- Bubble Sort mengurutkan data dengan cara membandingkan
elemen sekarang dengan elemen berikutnya.
- Jika elemen sekarang lebih besar dari elemen berikutnya maka
kedua elemen tersebut ditukar, jika pengurutan ascending.
- Jika elemen sekarang lebih kecil dari elemen berikutnya, maka
kedua elemen tersebut ditukar, jika pengurutan descending
- Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya.
- Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian
seterusnya.
- Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
#Prosedur Bubble Sort
void bubble_sort(){
for(int i=1;i
for(int j=n-1;j>=i;j--){
if(data[j]
}
}
}
Dengan prosedur diatas, data terurut naik (ascending), untuk urut turun (descending) silahkan ubah bagian :
if (data[j]
Menjadi:
if (data[j]>data[j-1]) tukar(j,j-1);
EXCHANGE SORT
- Sangat mirip dengan Bubble Sort
- Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort
- Pebedaan : dalam hal bagaimana membandingkan antar elemen- elemennya.
- Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
- Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
#Prosedur Exchange Sort
void exchange_sort()
{
for (int i=0; i
for(int j = (i+1); j
if (data [i] <>
}
}
}
SELECTION SORT
- Merupakan kombinasi antara sorting dan searching
- Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
- Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).
- Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
#Prosedur Selection Sort
void selection_sort(){
for(int i=0;i
pos = i;
for(int j=i+1;j
if(data[j] < pos =" j;">
}
if(pos != i) tukar(pos,i);
}
}
INSERTION SORT
- Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
- Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
- Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
#Prosedur Insertion Sort
void insertion_sort(){
int temp;
for(int i=1;i
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0){
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
#Program Lengkapnya:
#include
#include
int data[10],data2[10];
int n;
void tukar(int a,int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}
void bubble_sort()
{
for(int i=1;i
for(int j=n-1;j>=i;j--){
if(data[j]
}
}
printf("bubble sort selesai!\n");
}
void exchange_sort(){
for (int i=0; i
for(int j = (i+1); j
if (data [i] > data[j]) tukar(i,j);
}
}
printf("exchange sort selesai!\n");
}
void selection_sort(){
int pos,i,j;
for(i=0;i
pos = i;
for(j = i+1;j
if(data[j] < pos =" j;
}
if(pos != i) tukar(pos,i);
}
printf("selection sort selesai!\n");
}
void insertion_sort(){
int temp,i,j;
for(i=1;i
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0){
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
printf("insertion sort selesai!\n");
}
void Input(){
printf("Masukkan jumlah data = ");scanf("%d",&n);
for(int i=0;i
printf("Masukkan data ke-%d =
",(i+1));scanf("%d",&data[i]);
data2[i] = data[i];
}
}
void AcakLagi(){
for(int i=0;i
data[i] = data2[i];
}
printf("Data sudah teracak!\n");
}
void Tampil(){
printf("Data : ");
for(int i=0;i
printf("%d ",data[i]);
}
printf("\n");
}
void main(){
clrscr();
int pil;
do{
clrscr();
printf("1. Input Data\n");
printf("2. Bubble Sort\n");
printf("3. Exchange Sort\n");
printf("4. Selection Sort\n");
printf("5. Tampilkan Data\n");
printf("6. Acak\n");
printf("7. Exit\n");
printf("Pilihan = ");scanf("%d",&pil);
switch(pil){
case 1:Input();break;
case 2:bubble_sort();break;
case 3:exchange_sort();break;
case 4:selection_sort();break;
case 5:Tampil();break;
case 6:AcakLagi();break;
}
getch();
}while(pil!=7);
}
Quick Sort
Quick sort merupakan divide and conquer algorithm.Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) lalu menyimpan semua elemen yang lebih kecil di sebelah kirinya dan semua elemen yang lebih besar di sebelah kanannya. Hal ini dilakukan secara rekursif terhadap elemen di sebelah
kiri dan kanannya sampai semua elemen sudah terurut. Algoritma ini termasuk algoritma yang cukup baik dan cepat. Hal penting dalam algoritma ini adalah
pemilihan nilai tengah yang baik sehingga tidak memperlambat proses sorting secara keseluruhan. Ide dari algoritma ini adalah sebagai berikut :
· Pilih satu elemen secara acak
· Pindahka semua elemen yang lebih kecil ke
sebelah elemen tersebut dan semua elemen yang lebih besar ke sebelah kanannya. Elemen yang nilainya sama bisa disimpan di
salah satunya. Ini disebut operasi partisi
· Lakukan sort secara rekursif terhadap sublist sebelah kiri dan kanannya
Berikut adalah psudocode untuk quicksort :
function quicksort(array)
var list kecil,sama,besar
if length(array) ≤ 1
return array
end if
pilih sebuah nilai, disebut
pivot
for each x in array
if x <>then append x
to kecil
end if
if x = pivot then append x
to sama end if
if x > pivot then append x
to besar
end if
end for
return
concatenate(quicksort(kecil), sama ,
quicksort(besar))
SEARCHING
Binary Search
- Adalah teknik pencarian data dalam array dengan cara membagi array menjadi dua
bagian setiap kali terjadi proses pengurutan.
- Prinsip pencarian biner adalah:
Data diambil dari posisi 1 sampai posisi akhir N
Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah - 1
Jika data sama, berarti ketemu.
Sequential Search
Disebut juga sabagai metode pencarian urut adalah metode pencaharian yang paling mudah. Bayangkan saja jika anda dihadapkan pada sebuah rak buku, dan anda diberi tugas untuk mencari sebuah buku dari rak tersebut. Sudah tentu anda akan mulai mencarinya satu persatu entah itu dari atas atau dari bawah sampai buku yang dimaksud ketemu.
Singkatnya sequential search memiliki proses sabagai berikut :
Tentukan banyaknya data yang akan di olah, missal banyak data adalah N.
Tentukan data apa yang akan dicari, missal data yang akan dicari adalah C.
Deklarasikan sebuah counter untuk menghitung banyak data yang ditemukan, missal counternya adalah K.
Inisialisasikan K = 0.
Lakukanlah perulangan sebanyak N kali.
Dalam tiap proses perulangan tersebut periksalah apakah data yang sedang diolah sama dengan data yang dicari.
Jika ternyata sama K = K+1.
Jika tidak, lanjutkan proses perulangan.
Setelah proses perulangan berhenti, periksalah nilai K.
Jika nilai K lebih dari 0, artinya data yang dicari ada dalam data / array dan tampilkan nilai K ke layar sebagai jumlah data yang ditemukan.
Jika nilai K = 0, artinya data yang dicari tidak ditemukan dalam data / array dan tampilkan ke layar bahwa data tidak ditemukan.
Proses selesai.
Tidak ada komentar:
Posting Komentar