Sorting dan Searching
- Runtuhan/Sequence. Kaidah pemrograman yang menyatakan bahwa perintah-perintah dalam program komputer akan dieksekusi menurut urutannya dari atas ke bawah
- Seleksi/Selection. Perintah-perintah dalam program komputer akan dieksekusi berdasarkan nilai kebenaran boolean tertentu.
- Perulangan/loop. Sejumlah perintah dalam program komputer yang akan dieksekusi beberapa kali berdasarkan nilai kebenaran boolean-nya.
Sorting dapat dilakukan dengan du metode, yaitu Ascending dan Descending. Ascending akan melakukan pengurutan dari data yang terkecil ke data yang lebih besar.
Contoh: 1,2,3,.....10.
Descending akan melakukan pengurutan dari data yang terbesar ke data yang lebih kecil.
Contoh : 10,9,8,....1.
A. Pencarian Linear (Linear Search)
Pencarian Linear adalah metode pencarian yang membandingkan data kunci(data yang dicari) dengan seluruh data, mulai dari data pertama.
B. Pencarian Biner (Binary Search)
Pencarian Biner adalah pencarian terhadap data yang sudah terurut. Data kunci dengan data tengah(data pivot), jika sama berarti pencarian ditemukan. Jika data kunci lebih besar dari data tengah maka pencarian akan dilakukan disebelah kanan data tengah (data diurutkan secara ascending). Jika belum ditemukan maka data pada sisi pencarian akan dibagi dua kembali, dibandingkan lagi, demikian seterusnya sampai data ditemukan/tidak ditemukan.
C. Bubble Sort
Algoritma Bubble Sort akan membandingkan elemen yang saat ini dibaca dengan elemen yang berikutnya. Jika elemen yang saat ini dibaca lebih besar dari elemen berikutnya, maka tukarkan.
D. Insertion Sort
Pada metode ini pengurutan dilakukan dengan cara membandingkan data ke-i (dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.
E. Selection Sort
Metode ini akan membandingkan elemen yang sekarang dengan elemen berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen yang lebih kecil dari elemen sekarang, maka dicatat posisinya dan kemudian ditukarkan.
F. Quick Sort
Metode Quick Sort adalah membandingkan suatu elemen pivot dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen tersebut terletak disebelah kirinya dan elemen-elemen yang lebih besar daripada pivot terletak disebelah kanan.
Berikut Contoh BubbleSort/Script BubbleSort:
import java.util.Scanner;
public class BubbleSort{
public void bubblesSort (float larik2[]){
for (int i=0; i<larik2.length; i++){
for (int elemen=0;elemen<larik2.length-1;elemen++){
if (larik2[elemen]>larik2[elemen+1])
tukar(larik2, elemen,elemen+1);
}
}
}
public void tukar(float larik3[], int satu, int dua){
float temp;
temp = larik3[satu];
larik3[satu] = larik3[dua];
larik3[dua] = temp;
}
public static void main(String[]args){
Scanner masuk = new Scanner (System.in);
BubbleSort lrk = new BubbleSort ();
float nilai[] = new float [5];
System.out.println ("Masukkan 5 buat data nilai");
for (int i = 0; i < 5; i++)
{
System.out.print ((i + 1)+" : ");
nilai[i]=masuk.nextFloat();
}
System.out.println("Data nilai yang dimasukkan");
for (int i = 0; i < 5; i++)
System.out.print(nilai[i]);
System.out.println("Data hasil pengurutan ");
lrk.bubbleSort(nilai);
for (int i = 0; i < 5; i++)
System.out.println(nilai[i]);
}
}
Hasil dari BubbleSort
Berikut Contoh QuickSort/Script QuickSort:
import java.util.Scanner;
public class QuickSort{
public void quickSort(float A[], int L, int R)
{
int i,j;
float p;
p=A[(L+R)/2];
i=L;
j=R;
{
while (A[i]<p) i++;
while (A[j]>p) j--;
if (i<=j)
{
tukar(A,i,j);
i++;
j--;
}
}
if (L<j) quickSort(A,L,j);
if (i<R) quickSort(A,i,R);
}
public void tukar(float larik3[], int satu, int dua)
{
float temp;
temp = larik3[satu];
larik3[satu] = larik3[dua];
larik3[dua] = temp;
}
public static void main(String args[]){
Scanner masuk = new Scanner(System.in);
QuickSort lrk = new QuickSort();
float nilai[]=new float[5];
System.out.println("Masukkan 5 buat data nilai");
for (int i = 0; i<5; i++)
{
System.out.print((i + 1)+" : ");
nilai[i]=masuk.nextFloat();
}
System.out.println("Data yang dimasukkan");
for (int i = 0; i < 5; i++)
System.out.println(nilai[i]);
System.out.println("Data hasil pengurutan ");
lrk.quickSort(nilai, 0, nilai.length-1);
for (int i = 0; i < 5; i++)
System.out.println(nilai[i]);
}
}
Hasil dari QuickSort
Berikutnya Script BinerSearch :
import java.util.Scanner;
public class BinerSearch{
public int pencarianBiner(int b[], int kunciPencarian, int low, int high){
int i, middle;
while (low<=high){
middle = (low+high)/2;
if (kunciPencarian==b[middle]) return middle;
else if (kunciPencarian<b[middle]) high = middle-1;
else low = middle+1;
}
return -1;
}
public static void main(String args[]){
Scanner input = new Scanner(System.in);
BinerSearch biner = new BinerSearch();
int i, x, hasil;
boolean ketemu;
int data[] = {9, 13, 14, 26, 34};
System.out.print("Masukkan Data yang dicari = ");
x = input.nextInt();
hasil = biner.pencarianBiner(data, x, 0, data.length-1);
if (hasil>=0)
System.out.println("Data tersebut ada pada posisi ke-" +(hasil+1));
else
System.out.println("Data tidak ketemu !");
}
}
Output dari BinerSearch
Stack/Tumpukan Dan Antrian/Queue
Sebelumnya ada yang udah tahu apa itu Stack atau Tumpukan dan Atnrian/Queue, jika masih ada yang belum paham saya akan menjelaskan lebih rinci tentang Stack/Tumpukan.
Stack atau tumpukan adalah struktur data dimana semua penyisipan dan penghapusan data dilakukan pada salah satu ujung yang disebut top (puncak) stack. Stack dapat dibayangkan sebagai tumpukan kardus dimana hanya kardus teratas dapar diperoleh kembali dengan satu langkah. Kardus-kardus yang terdapat dibawah hanya dapat diambil setelah kardus yang berada diatasnya diambil (dikeluarkan). Dengan bentuk yang demikian tumpukan dapat dikatakan sebagai struktur data yang bersifat LIFO (Last In First Out). Metode/fungsi yang terpenting pada stack adalah push dan pop.
Antrian/Queuedidefinisikan sebagai sebuah jalur tunggu, seperti sebuah jalur orang menunggu untuk beli tiket, dimana orang yang pertama datang akan dilayani terlebih dahulu.
Dalam aplikasi komputer, queue didefinisikan sebagai sebuah list dimana semua penambahan elemen dibuat di ujung belakang dan penghapusan elemen list dibuat di ujung depan. Dengan bentuk yang demikian queue dapat dikatakn sebagai struktur data yang bersifat FIFO (First In Firs Out).
Setelah telah emngetahui apa itu stack/tumpukan, dan Antrian/queue. Sebagai contoh saya akan memberikan contoh Program yang sudah jadi dengan menggunakan Java.
Berikut script tentang Stack/Tumpukan :
class Tumpukan
{
private int ukuran;
private long[] tumpukan;
private int top;
public Tumpukan(int s)
{
ukuran = s;
tumpukan = new long[ukuran];
top = -1;
}
public void push(long j)
{
tumpukan[++top] = j;
}
public long pop()
{
return tumpukan[top--];
}
public long peek()
{
return tumpukan[top];
}
public boolean isEmpty()
{
return (top == ukuran-1);
}
public void baca()
{
int i = top;
while(i>=0)
{
System.out.print(tumpukan[i]);
System.out.print(" ");
i--;
}
System.out.println(" ");
}
}
class ApliStack
{
public static void main(String[] args)
{
Tumpukan stack = new Tumpukan(10);
stack.push(56);
stack.baca();
stack.push(45);
stack.baca();
stack.push(67);
stack.baca();
stack.push(83);
while( !stack.isEmpty())
{
long nilai = stack.pop();
System.out.print(nilai);
System.out.print(" ");
}
System.out.println(" ");
}
}
Jika sudah membuat Script Stack/Tumpukan, silahkan lihat output-nya sekarang. hehe
berikut Script tentang Antrian/Queue :
class Antrian{
private int ukuran;
private long[] antrian;
private int depan;
private int belakang;
private int jumItem;
public Antrian(int s) {
ukuran = s;
antrian = new long[ukuran];
depan = 0;
belakang = -1;
jumItem = 0;
}
public void masuk(long j){
if(!isFull()){
antrian[++belakang] = j;
jumItem++;
}
}
public long keluar(){
long temp = antrian[0];
for (int i=0;i<jumItem;i++)
antrian[i]=antrian[i+1];
jumItem--;
belakang--;
return temp;}
public long peeDepan(){
return antrian[depan];}
public boolean isEmpty(){
return (jumItem==0);}
public boolean isFull(){
return (belakang==ukuran-1);}
public int ukuran(){
return jumItem;}
public void lihat(){
for (int i=0; i<jumItem;i++)
System.out.print(antrian[i]+" ");
System.out.println("");
}}
class ApliAntrian{
public static void main(String[]args){
Antrian antrian = new Antrian(10);
antrian.masuk(13);
antrian.lihat();
antrian.masuk(32);
antrian.lihat();
antrian.masuk(45);
antrian.lihat();
antrian.masuk(67);
antrian.lihat();
antrian.keluar();
antrian.lihat();
antrian.keluar();
antrian.lihat();
antrian.masuk(43);
antrian.lihat();
antrian.keluar();
antrian.lihat();
antrian.masuk(56);
antrian.lihat();
antrian.masuk(76);
antrian.lihat();
antrian.masuk(85);
antrian.lihat();
antrian.masuk(92);
antrian.lihat();
while ( !antrian.isEmpty()){
long n = antrian.keluar();
System.out.print(n);
System.out.print(" ");}
System.out.println(" ");
}}
Untuk melihat hasil output apa yang akan terjadi, Anda bisa coba sendiri dengan script ini.
Script ini hanya untuk koding menggunakan java seperti software netbeans,textpad dan lainnya sebagainya.
Jika Anda menggunakan textpad jangan lupa saat disave berilah nama yang sesuai dengan nama class yang kalian gunakan dalam koding tersebut. Seperti script yang saya buat tentang antrian/queue nama class yang digunakan yaitu class Tumpukan. jadi Simpanlah dengan nama Tumpukan.java
Jika sudah disimpan lihat terlebih dahulu apakah script yang dibuat sudah benar. Untuk melihat semua script benar atau salah dengan menekan tombol ctrl dan angka 1, apabila ada tulisan Tools Succesfully maka script yang dibuat sudah benar, selanjutnya tinggal melihat hasil output script tersebut dengan menekan tombol ctrl dan angka 2.
Nah setelah selesai semua kalian akan tahu apa yang akan dihasilkan. Apabila ada keluhan tentang stack/tumpukan dan Antrian/Queue silahkan berikan komentar dengan jelas.
jika ada kesalahan ataupun keluhan komen aja dibawah yaa, InsyaAllah dibales kalo ga sibuk.
0 Komentar untuk "Sorting Searching dan Satck"