searching dan sorting

Sorting & Searching

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 :

1. Bandingkan nilai pada data ke-1 dengan data ke-2
2. Jika nilai data ke-1 lebih besar dari data ke-2 maka tukar posisinya
3. Kemudian data yang lebih besar tersebut dibandingkan lagi dengan data ke-3
4. 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

Contoh syntax bubble sort:

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:

1. Pengecekan dimulai dari data 1 sampai dengan data ke n
2. Tentukan bilangan dengan Index terkecil dari data bilangn tersebut
3. Tukar bilangan dengan index terkecil tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut
4. 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 :

1. Bandingkan data kedua dengan data pertama, jika data kedua lebih kecil maka tukar posisinya, jika tidak biarkan aja.
2. Data ketiga dibandingin dengan data ke-1 dan ke-2,jika data ke-3 lebih kecil tukar lagi posisinya.
3. 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;itemp = data[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:

1. Pilih satu elemen secara acak
2. 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
3. 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 :

1. i←0
2. ketemu←false
3. 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;

}

2.-Binary Search

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;

}

 

 Insertion sort

Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

Algoritmanya :

void insertionSort(Object array[], int startIdx, int endIdx) {

for (int i = startIdx; i < endIdx; i++) {

int k = i;

for (int j = i + 1; j < endIdx; j++) {

if(((Comparable) array[k]).compareTo(array[j])>0) {

k = j;

}

}

swap(array[i],array[k]);

}

}

 

Selection sort

Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah – langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.

Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

Algoritmanya :

void selectionSort(Object array[], int startIdx, int endIdx) {

int min;

for (int i = startIdx; i < endIdx; i++) {

min = i;

for (int j = i + 1; j < endIdx; j++) {

if (((Comparable)array[min]).compareTo(array[j])>0) {

min = j;

}

}

swap(array[min], array[i]);

}

}

 

Merge sort

Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.

Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.

1. Divide

Memilah masalah menjadi sub masalah

2. Conquer

Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif

3. Kombinasi

Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama

Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah
berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide

Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi

Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Algoritmanya :

void mergeSort(Object array[], int startIdx, int endIdx) {

if (array.length != 1) {

//Membagi rangkaian data, rightArr dan leftArr

mergeSort(leftArr, startIdx, midIdx);

mergeSort(rightArr, midIdx+1, endIdx);

combine(leftArr, rightArr);

}

}

 

Gambar3.1. Diagram Merge Sort

 

 

 Quick sort

Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

1. Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif

Pada algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

Algoritmanya :

void quickSort(Object array[], int leftIdx, int rightIdx) {

int pivotIdx;

/* Kondisi Terminasi */

if (rightIdx > leftIdx) {

pivotIdx = partition(array, leftIdx, rightIdx);

quickSort(array, leftIdx, pivotIdx-1);

quickSort(array, pivotIdx+1, rightIdx);

}

}

Gambar 3.2. Diagram Quick Sort

 

Counting sort

Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

Algoritma ini diproses dengan mendefinisikan sebuah hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran yang serupa dengan array A. katakana array tersebut adalah array B. untuk setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang dengan 1.

Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

Adapun syarat algoritma ini berjalan dengan baik ialah:

1. Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
   
2. Range data diketahui
   

Ada 3 macam array yang terlibat:

1. Array untuk mengisi bilangan yang belum diurutkan.
   
2. Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
   
3. Array untuk mengisi bilangan yang sudah diurutkan.
   

Algoritmanya :

countingsort(A[], B[], min, max, n)
for i = min to max do
C[i] = 0

for j = 1 to n do
C[A[j]] = C[A[j]] + 1

for i = min + 1 to max do
C[i] = C[i] + C[i-1]

for j = n downto 1 do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] – 1

Gambar 3.3 Diagram Counting Sort

Radix Sort

Radix sorting bisa digunakan ketika masing-masing universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’ sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting pada least significant decimal digit. Kunci utama dari radix sort adalah pada passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data yang terisi telah disorting.

Algoritmanya :

source

List of bytes

source_n

number of bytes to sort

dest[256]

256 lists of bytes. each list should have enough space to hold source_n elements.

//——————-saving element in memory——————–

int distribution[256]


// fill the list with zeros.


for i=0 to 255 do

distribution[i]=0;


// build a distribution history:


for i=0 to source_n do

distribution] = distribution] +1;

endfor


// Now we build a index-list for each possible element:


int index[256];

index [0]=0;


for i=0 to 255 do

index[i]=index[i-1]+distribution[i-1];

endfor

//sorting

dest: array of bytes with space for source_n bytes.

for i = 0 to source_n do

  dest[index]]=source[i];

  index] = index] +1;

endfor

 Binary Searching

Algoritma pencairan secara linear melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama dengan elemen pertama dalam tabel) dan Nmax kali untuk kasus terburuk. Sehingga algoritma ini mempunyai kompleksitas algoritma O(n).

Implementasi algoritma pencarian biner dalam bahasa C adalah sebagai berikut.

void BinSearch (int T[],int Nmax, int

value, int* idx)

int i,j,mid;

boolean found;$

/*algoritma*/

found = false;

i = 1;

j = Nmax;

while ((!found) && (i<=j))

{

mid = (i+j) div 2;

if (T[mid] == value)

{

found = true;

}

else

{

if (T[mid]<value)

{

i = mid + 1;

}

else

{

j = mid – 1;

}

}

}

if (found)

{

*idx = mid;

}

else

{

*idx = 0;

}

}

Algoritma pencarian biner adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu :

• Mencari nilai tengah dari tabel (median)

• Melakukan perbandingan nilai tengah

dengan nilai yang dicari untuk menentukan

apakah nilai yang dicari ada pada sebelum

atau setelah nilai tengah

• Mencari setengah sisanya dengan cara yang

sama.