Algoritma Sorting

Algoritma Sorting
ada beberapa Algoritma Sorting, yaitu :
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.


2.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

3.Merge Sort
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari
konsep divide and conquer karena merge sort mengadaptasi pola tersebut.
Pola Divide and Conquer
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.
- Divide
Memilah masalah menjadi sub masalah
- Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif
- Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama

4.Quicksort
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

berikut contoh algoritmanya :

#include
#include

int data[100],data2[100];
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]}
}
cout<<”bubble sort selesai!”<}

void exchange_sort()
{
for (int i=0; i{
for(int j = (i+1); j{
if (data [i] > data[j]) tukar(i,j);
}
}
cout<<”exchange sort selesai!”<}

void selection_sort()
{
int pos,i,j;
for(i=0;i{
pos = i;
for(j = i+1;j{
if(data[j] < data[pos]) pos = j;
}
if(pos != i) tukar(pos,i);
}
cout<<”selection sort selesai!”<}

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;
}
cout<<”insertion sort selesai!”<}

void QuickSort(int L, int R) //the best sort i’ve ever had
{
int i, j;
int mid;

i = L;
j = R;
mid = data[(L+R) / 2];

do
{
while (data[i] < mid) i++;
while (data[j] > mid) j–;

if (i <= j)
{
tukar(i,j);
i++;
j–;
};
} while (i < j);

if (L < j) QuickSort(L, j);
if (i < R) QuickSort(i, R);
}

void Input()
{
cout<<”Masukkan jumlah data = “; cin>>n;
for(int i=0;i{
cout<<”Masukkan data ke-”<<(i+1)<<” = “; cin>>data[i];
data2[i] = data[i];
}
}

void Tampil()
{
cout<<”Data : “<for(int i=0;i{
cout<}
cout<}

void AcakLagi()
{
for(int i=0;i{
data[i] = data2[i];
}
cout<<”Data sudah teracak!”<}

void main()
{
int pil;
clrscr();
do
{
clrscr();
cout<<”Program Sorting Komplit!!!”<cout<<”*********************************************”<cout<<” 1. Input Data”<cout<<” 2. Bubble Sort”<cout<<” 3. Exchange Sort”<cout<<” 4. Selection Sort”<cout<<” 5. Insertion Sort”<cout<<” 6. Quick Sort”<cout<<” 7. Tampilkan Data”<cout<<” 8. Acak Data”<cout<<” 9. Exit”<cout<<” Pilihan Anda = “; cin>>pil;
switch(pil)
{
case 1:Input(); break;
case 2:bubble_sort(); break;
case 3:exchange_sort(); break;
case 4:selection_sort(); break;
case 5:insertion_sort(); break;
case 6:QuickSort(0,n-1);
cout<<”quick sort selesai!”<break;
case 7:Tampil(); break;
case 8:AcakLagi(); break;
}
getch();
}while(pil!=9);
}

Read More..

Algoritma Binary Search

Binary Search adalah salah satu algoritma pencarian yang tercepat. Kecepatan algoritma ini hanya bisa dikalahkan oleh teknik hashing, yang tidak akan dibahas di sini. Untuk mencari jutaan data, Binary Search hanya butuh O(log N) kali pembandingan (sekitar 20 kali), sedangkan Linier Search butuh O(N) pembandingan (sekitar 500.000 kali). Tapi yang harus dicatat di sini, data yang dicari harus sudah terurut!
Algoritma iteratif (contohnya yang menggunakan perputaran FOR, WHILE, dsb) pada umumnya dapat dengan mudah diubah ke dalam algoritma rekursif (memanggil dirinya sendiri). Keistimewaan algoritma iteratif adalah sederhana, cepat, dan menggunakan sedikit memori. Sedangkan pada kasus seperti menelusuri pohon, algoritma rekursif jelas lebih baik karena lebih mudah difahami.
Pada prinsipnya, Binary Search adalah membandingkan Key (angka yang dicari) dengan angka yang berada tepat di tengah-tengah deretan angka yang sudah terurut. Jika sama, maka itulah yang dicari. Tapi jika tidak sama, maka deretan data dipecah menjadi dua blok: Blok bawah (kecil) dan blok atas (kecil). Lalu proses diulangi terhadap blok bawah atau blok atas, tergantung besarnya Key apakah lebih kecil ataukah lebih besar daripada data yang berada di tengah-tengah tadi.berikut contoh algoritmanya :

#include
#include

int binarySearch(int sortedArray[], int awal, int akhir, int key) {
if (awal <= akhir) {
int tengah = (awal + akhir) / 2; // Hitung titik tengah.
if (key == sortedArray[tengah])
return tengah; // Ketemu.
else if (key < sortedArray[tengah])
// Panggil prosedur binarySearch untuk setengah bagian bawah.
return binarySearch(sortedArray, awal, tengah-1, key);
else
// Panggil prosedur binarySearch untuk setengah bagian atas.
return binarySearch(sortedArray, tengah+1, akhir, key);
}
return -(awal + 1); // Gagal menemukan Key yang dicari.
}

void main(void) {
int sortedArray[100];
int jumlahData, i, key;
int letak;

cout << "Demo Binary Search menggunakan teknik rekursi" << endl;
cout << "Oleh: (Ketik nama anda di sini)." << endl;
cout << endl;
cout << "Ada berapa banyak data? (max 100) "; cin >> jumlahData;
cout << endl;
cout << "Silakan Ketik " << jumlahData << " angka yg sudah terurut!" << endl;
cout << "Tiap angka dipisahkan oleh spasi." << endl;

for (i = 0; i < jumlahData; i++) {
cin >> sortedArray[i];
};

cout << endl;
cout << "Angka berapa yang dicari? "; cin >> key;
cout << endl;
cout << "Mulai mencari..." << endl;
letak = binarySearch(sortedArray, 0, (jumlahData - 1), key);
if (letak < 0) {
cout << "Maaf, data tidak ketemu." << endl;
}
else {
cout << "Data ditemukan pada posisi ke " << (letak + 1) << endl;
cout << "Pada posisi tsb terdapat angka " << sortedArray[letak] << endl;
};
cout << endl;
cout << "Tekan sembarang tombol.";
getch();
}

Read More..

Algoritma Sequential Search

Algoritma sequential search adalah salah satu algoritma yang digunakan untuk memecahkan masalah pencarian data pada suatu data larik/array. Cara kerja dari algoritma ini adalah dengan menelusuri elemen-elemen array dari awal sampai akhir, dimana data tidak perlu diurutkan terlebih dahulu. Kemungkinan terbaik(best case) dari algoritma ini adalah jika data yang dicari berada pada elemen array yang terdepan sehingga waktu yang dibutuhkan untuk pencarian data semakin singkat. Sebaliknya, akan mencapai kondisi terburuk(wors case) apabila data yang dicari berada pada elemen akhir.berikut contoh programnya


#include
#include
void main()
{
clrscr();
int data[8] = {8,10,6,-2,10,7,1,100};
int cari,index;
int ketemu=0;
cout<<”masukkan data yang ingin dicari = “;
cin>>cari;
for(int i=0;i<8;i++)
{
if(data[i] == cari)
{
ketemu=1;
index = i;
break;
}
}
if(ketemu == 1)
{
cout<<”Data ada!”<cout<<”Data terletak di index ke – “<}
else cout<<”Data Tidak ada!”<getch();
}

Read More..