SORTING
Sorting adalah pengurutan data. Data diurutkan dari yang terkecil sampai yang paling besar atau sebaliknya. Tujuannya supaya data tersebut jadi tersusun rapi, terurut dan teratur. Algoritma untuk melakukan sorting sperti itu ada bermacam-macam diantaranya BubbleSort, SelectionSort, InsertionSort, QuickSort, ExchangeSort, HeapSort, SmoothSort, CocktailSort, ShellSort, MergeSort, dan masih banyak lagi yang lainnya. Kali ini kita akan membahas 5 macam sorting saja yaitu BubbleSort, SelectionSort, InsertionSort, ExchangeSort dan QuickSort.
1.-BubbleSort
BubbleSort adalah pengurutan data yang dilakukan dengan membandingkan antara data[n] dengan data[n+1] atau antara data[n] dengan data[n-1] kemudian jika data lebih kecil/besar dilakukan pertukaran. Pada setiap iterasi dapat terjadi beberapa kali pertukaran atau tidak sama sekali. Jumlah iterasi ditentukan oleh banyaknya data atau ‘N’. Iterasi=N-1.”
Langkah-langkah bubble sort yaitu :
Bandingkan nilai pada data ke-1 dengan data ke-2
Jika nilai data ke-1 lebih besar dari data ke-2 maka tukar posisinya
Kemudian data yang lebih besar tersebut dibandingkan lagi dengan data ke-3
Jika data ke-3 lebih kecil dari data ke-2 maka tukar posisinya, dan begitu seterusnya sampai data yang ada jadi terurut.
Contoh secara manual :
-
iterasi
Urutan data
0
87 74 71 54 88 60
1
74 71 54 87 60 88
2
71 54 74 60 87 88
3
54 71 60 74 87 88
4
54 60 71 74 87 88
void bubble_sort()
{
for(int i=1;i
{
for(int j=n-1;j>=i;j--)
{
if(data[j]
}
}
Dengan cara ini data akan terurut naik (ascending),untuk data terurut turun (descending)
silahkan rubah bagian di bawah ini:
(data[j]
menjadi:
if (data[j]>data[j-1]) tukar(j,j-1);
Intinya bubble sort itu salah satu metode yang simpel untuk sorting, tetapi jika jumlah data yang disorting besar akan memakan waktu yang lama.2.-SelectionSort
SelectionSort adalah merupakan sebuah algoritma pengurutan yang secara berulang mencari data yang belum terurut dan mencari paling sedikit satu untuk dimasukkan ke dalam lokasi akhir.
Prinsip kerja dari Teknik Section sort ini adalah:
Pengecekan dimulai dari data 1 sampai dengan data ke n
Tentukan bilangan dengan Index terkecil dari data bilangn tersebut
Tukar bilangan dengan index terkecil tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut
Lakukan langkah 2 dan3 untuk bilangan berikutnya (I=I+1)sampai di dapatkan data yang optimal
Syntax program fungsi Selection Sort
for ( i=0 ; i <= N-2 ; i++) { kecil = i; for ( k = i+1 ; k <= N-1 ; k++ ) { if (A[k] > A[j])
{
kecil=k;
}
}
temp=A[i];
A[i]=A[kecil];
A[kecil]=temp;
}
3.-InsertionSort
InsertionSort dilakukan dengan cara menyisipkan sebuah angka ke posisi yang diinginkan. Angka yang disisipkan sesuai dengan urutan iterasinya. Jumlah iterasi ditentukan oleh banyaknya data atau ‘N’. Iterasi=N”.Sekilas algoritma ini tidak jauh berbeda dengan Bubble Sort, namun sesungguhnya berbeda.
Langkah-langkahnya :
Bandingkan data kedua dengan data pertama, jika data kedua lebih kecil maka tukar posisinya, jika tidak biarkan aja.
Data ketiga dibandingin dengan data ke-1 dan ke-2,jika data ke-3 lebih kecil tukar lagi posisinya.
Data ke-4 dibandingin dengan data ke-3, ke-2, dan ke-1, jika data ke-4 lebih kecil dari ketiganya maka letakkan data ke-4 ke posisi paling depan, gitu dech seterusnya.
Contoh (secara manual aja) :
Misalkan data : 10 5 7 9 2 1 8 6
-
Iterasi
Data
0
10 5 7 9 2 1 8 6
1
5 10 7 9 2 1 8 6
2
5 7 10 9 2 1 8 6
3
5 7 9 10 2 1 8 6
4
2 5 7 9 10 1 8 6
5
1 2 5 7 9 10 8 6
6
1 2 5 7 8 9 10 6
7
1 2 5 6 7 8 9 10
Pada iterasi 7, data sudah terurut.
Contoh syntax insertion sort:
void insertion_sort(){
int temp;
for(int i=1;i
j = i -1;
while(data[j]>temp && j>=0){
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
4.-QuickSort
QuickSort 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 (pivot) yang baik sehingga tidak memperlambat proses sorting secara keseluruhan.
Ide dari algoritma ini adalah sebagai berikut:
Pilih satu elemen secara acak
Pindahkan 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.
Contoh program QuickSort :
void QuickSort (int L,int R)
{
int i, j;
int mid;
i=L;
j=R;
mid = data[(L+R) / 1];
do
{
while (data[i] <>
while (data[j] > mid) j--;
if (i <= j)
{
tukar(i,j);
i++;
j--;
};
} while (i <>
if (L <>
if (i <>
}
5.-ExchangeSort
ExchangeSort hampir sama dengan Bubble Sort. Tapi ada bedanya, yaitu bagaimana membandingkan antar elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika diperlukan. 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.
Contoh programnya :
void exchange_sort()
{
for (int i=0; i
for(int j = (i+1; j
if (data [i] < data[j]) tukar(i,j); //descending
}
}
}
untuk pengurutan secara ascending, silahkan gunakan/ ganti syntax sebelumnya menjadi :
if (data [i] > data[j]) tukar(i,j);
SEARCHING
Searching adalah pencarian suatu data dalam sekumpulan data . Kali ini kita akan bahas tentang 2 jenis searching yaitu Sequential Search dan Binary Search.
1.-Sequential Search
Sequential Search merupakan proses pencarian data dengan metode pencarian langsung. Ini dilakukan dengan cara mencocokkan data yang akan dicari dengan semua data yang ada dalam kelompok data. Proses pencocokan data dilakukan secara berurutan. Satu demi satu dimulai dari data ke1 hingga data pada urutan terakhir.
Secara manual contoh :
Data : 20 25 35 79 80 90
Data yang dicari 35
-
Iterasi
Data
keterangan
0
20 25 35 79 80 90
Data awal
1
20 25 35 79 80 90
Belum cocok
2
20 25 35 79 80 90
Belum cocok
3
20 25 35 79 80 90
Data ditemukan
Ket : angka yang ditebalkan maksudnya angka yang diseleleksi.
Yang diatas pengertian secara manual. Secara teoritis sequential search : pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma pencarian berurutan dapat dituliskan sebagai berikut :
i←0
ketemu←false
Selama (tidak ketemu) dan (i <= N) kerjakan baris 4 4 Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1 5 Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian sekuensial.
int SequentialSearch(int x)
{
int i = 0;
bool ketemu = false;
while ((!ketemu) && (i <>
if(Data[i] == x)
ketemu = true;
else
i++;
}
if(ketemu) return i;
else
return -1;
}
Binary Search adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu komputer. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Sebuah pencarian biner adalah salah satu contoh dari algoritma divide and conquer .
Penerapan terbanyak dari binary search adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai.
Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama.
Contoh syntax nya :
int BinarySearch(int x)
{
int L = 0, R = Max-1, m;
bool ketemu = false;
while((L <= R) && (!ketemu))
{
m = (L + R) / 2;
if(Data[m] == x)
ketemu = true;
else if (x <>
R = m - 1;
else
L = m + 1;
}
if(ketemu)
return m;
else
return -1;
}
