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 sortbekerja 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]);
}
}
swap(array[i],array[k]);
}
}
Selection sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan menemukan sebuah algoritma yang mirip denganselection 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 :
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
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 poladivide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah
berpola divide-and-conquer. Berikut menjelaskan langkah kerja dariMerge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sortsecara 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);
}
}
Gambar. Diagram Merge Sort
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama
Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan poladivide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah
berpola divide-and-conquer. Berikut menjelaskan langkah kerja dariMerge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sortsecara 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);
}
}
Gambar. Diagram Merge Sort
Quick sort
Quick sort 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 :
Quick sort 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. 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.
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. 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:
Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
Range data diketahui
Ada 3 macam array yang terlibat:
Array untuk mengisi bilangan yang belum diurutkan.
Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
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. 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
Searching
Linear Searching
Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.
Adapun syarat algoritma ini berjalan dengan baik ialah:
Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
Range data diketahui
Ada 3 macam array yang terlibat:
Array untuk mengisi bilangan yang belum diurutkan.
Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
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. 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
Searching
Linear Searching
Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.
void SeqSearch1 (int T[], int Nmax,
int value, int *idx)
{
/*kamus lokal*/
int i;
/*Algoritma*/
i = 1;
while ((i<Nmax) && (T[i] !=
value))
{
i = i + 1;
}
if (T[i]==value)
{
*idx = i;
}
else
{
*idx = 0;
}
}
Algoritma di atas melakukan pengulangan sampai i sama dengan Nmax (ukuran tabel) atau harga value dalam tabel sudah ditemukan. Kemudian harga i di-assign ke dalam variable idx. Elemen terakhir diperiksa secara khusus.
int value, int *idx)
{
/*kamus lokal*/
int i;
/*Algoritma*/
i = 1;
while ((i<Nmax) && (T[i] !=
value))
{
i = i + 1;
}
if (T[i]==value)
{
*idx = i;
}
else
{
*idx = 0;
}
}
Algoritma di atas melakukan pengulangan sampai i sama dengan Nmax (ukuran tabel) atau harga value dalam tabel sudah ditemukan. Kemudian harga i di-assign ke dalam variable idx. Elemen terakhir diperiksa secara khusus.
void SeqSearch2 (int T[],int Nmax,
int value, int *idx)
{
int i;
boolean found;
/*algoritma*/
i = 1;
found = false;
while ((i<=Nmax) && (!found))
{
if (T[i] == value)
{
found = true;
}
else
{
i = i + 1;
}
}
if (found)
{
*idx = i;
}
else
{
*idx = 0;
}
Binary SearchingAlgoritma 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.
int value, int *idx)
{
int i;
boolean found;
/*algoritma*/
i = 1;
found = false;
while ((i<=Nmax) && (!found))
{
if (T[i] == value)
{
found = true;
}
else
{
i = i + 1;
}
}
if (found)
{
*idx = i;
}
else
{
*idx = 0;
}
Binary SearchingAlgoritma 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 :
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.
No comments:
Post a Comment