Algoritma merupakan kumpulan perintah yang memiliki daya guna yang sangat besar bagi masyarakat. Algoritma biasanya digunakan sebagai kumpulan perintah untuk menyelesaikan suatu masalah. Algoritma ini memiliki aplikasi yang bermacam-macam dalam setiap masalah yang ada. Contohnya saja adalah algoritma cara menyelesaikan suatu aritmatika yang rumit, algoritma untuk menghitung luas penampang dari suatu kabel, atau bahkan untuk menghitung bayaran parkir di setiap mal. Salah satu aplikasi bentuk pemrograman ini adalah dalam bahasa permrograman yang disebut bahasa C. Dimana bahasa C ini memiliki suatu aturan-aturan tertentu yang sangat penting sehingga dalam penggunaanya kita harus memperhatikan cara menggunakan aturan tersebut. Salah satu cara penggunaannya adalah dengan array. Dimana array ini merupakan suatu data struktur yang berkoneksi satu sama lain dengan tipe yang sama. Aplikasi array ini banyak sekali, contohnya saja adalah menghitung golongan dari umur yang berjumlah 25 tahun hingga 55 tahun. Array ini juga bisa digunakan untuk mencari suatu elemen nilai dalam suatu struktur data, selain itu array ini juga bisa digunakan untuk mengurutkan data-data yang tidak berurutan. Hal –hal yang telah disebutkan disebut sebagai searching array dan sorting array.
Sorting array merupakan salah satu aplikasi yang paling penting dalam suatu sistem aplikasi perhitungan data. Biasanya suatu bank memiliki komputasi sorting array yang sudah biasa digunakan dalam aplikasinya sehari-hari. Bahkan telephone juga mengurutkan suatu list yang terdiri dari nama akhir , nama awal agar bisa memudahkan dalam perhitungan dalam mencari nomor telephone.
Searching array juga memiliki tak kalah pentingnya dibandingkan dengan sorting array. Pada searcing array kita biasa menggunakannya pada data yang sangat banyak. Sehingga sangat sulit bila kita ingin mencari suatu data atau suatu angka didalamnya satu per satu. Aplikasi searching array memudahkan kita dalam mencari suatu data atau angka yang kita inginkan dengan hanya memasukkan nilai input pada suatu data yang disikan.
1. Insertion sort
void insertionSort(Object array[], int startIdx, int endIdx){ for (int i = startIdx; i < endIdx; i++) { int k = i;if(((Comparable) array[k]).compareTo(array[j])>0) {for (int j = i + 1; j < endIdx; j++) { k = j; } } swap(array[i],array[k]); }}
2. Selection sort
void selectionSort(Object array[], int startIdx, int endIdx){ int min; for (int i = startIdx; i < endIdx; i++) {if (((Comparable)array[min]).compareTo(array[j])>0) {min = i; for (int j = i + 1; j < endIdx; j++) { min = j;}} } swap(array[min], array[i]);}
3. 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 langkahberpola 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
void mergeSort(Object array[], int startIdx, int endIdx){ if (array.length != 1) {mergeSort(leftArr, startIdx, midIdx);//Membagi rangkaian data, rightArr dan leftArr}mergeSort(rightArr, midIdx+1, endIdx); combine(leftArr, rightArr); }
4. 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-arrayAlgoritmanya :void quickSort(Object array[], int leftIdx, int rightIdx) {
int pivotIdx;
/* Kondisi Terminasi */
pivotIdx = partition(array, leftIdx, rightIdx);if (rightIdx > leftIdx) {
quickSort(array, leftIdx, pivotIdx-1);
}
quickSort(array, pivotIdx+1, rightIdx);
}
5. 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
C[A[j]] = C[A[j]] + 1for j = 1 to n do
for i = min + 1 to max do
B[C[A[j]]] = A[j]C[i] = C[i] + C[i-1]
for j = n downto 1 do
C[A[j]] = C[A[j]] – 1
6. 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 source_n dofor i=0 to 255 do
distribution[i]=0;
// build a distribution history:
distribution] = distribution] +1;
for i=0 to 255 doendfor
// Now we build a index-list for each possible element:
int index[256];
index [0]=0;
for i = 0 to source_n doindex[i]=index[i-1]+distribution[i-1];
endfor
//sorting
dest: array of bytes with space for source_n bytes.
endfor dest[index]]=source[i];
index] = index] +1;
7. Searching
7.1 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.Algoritmanya :void SeqSearch1 (int T[], int Nmax,
int value, int *idx)
{
/*Algoritma*//*kamus lokal*/
int i;
i = 1;
i = i + 1;while ((i<Nmax) && (T[i] !=
value))
{
}
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;
i = 1;boolean found;
/*algoritma*/
found = false;
if (T[i] == value)while ((i<=Nmax) && (!found))
{
{
found = true;
}
else
{
i = i + 1;
}}
}
if (found)
{
*idx = i;
}
else
{
*idx = 0;
7.2 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;
found = false;boolean found;$
/*algoritma*/
i = 1;
mid = (i+j) div 2;j = Nmax;
while ((!found) && (i<=j))
{
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.
