Robby Cokro Buwono

Algoritma Pencarian Dan Pengurutan 

Kode MK :   Revisi Terakhir :

Dapat menjelaskan algoritma pengurutan dan pencarian dan menggunakan contohnyapencarian dan menggunakan contohnya.

Pengurutan dengan menggunakan  metode bubble sort dan insertion sort Pencarianbubble sort dan insertion sort. Pencarian dengan menggunakan metode linear search 

Dalam banyak aplikasi, pengurutan menjadi algoritma yang banyak digunakanalgoritma yang banyak digunakan. Pengurutan sangat membantu dalam mengelola data karena karena dengan datamengelola data, karena karena dengan data yang terurut akan mudah melakukan pencarian data dan operasi lainnya.

Metode PengurutanBubble SortBubble SortInsertion Sort

Metode Bubble Sort  pengurutan dengan cara menarik nilai tertinggi atau terendah kecara menarik nilai tertinggi atau terendah ke indeks paling ujung dan dilakukan sebanyak n 1 langkah dimana n adalah k ran larikn‐1 langkah, dimana n adalah ukuran larikmisalnya ada 5 elemen dalam larik bernama A yadalah [10,8,3,5,4], elemen‐elemen larik A tersebut akan diurutkan secara ascendingtersebut akan diurutkan secara ascending (nilai terendah ke tertinggi), maka yang dilakukan adalahdilakukan adalah

1. Mengambil indeks 0 sebagai patokan, A[0] = 10, bandingkan A[0] dengan A[1], A[2], A[3], A[4]Jika A[0] > A[1] maka tukar nilai elemen, hasilnya A[0] menjadi 8, dan larik A menjadi [8,10,3,5,4]Jika A[0] > A[2] maka tukar nilai elemen, hasilnya A[0] menjadi 3, dan larik A menjadi [3,10,8,5,4]k [ ] [ ] k k l l h lJika A[0] > A[3] maka tukar nilai elemen, hasilnya tidak terjadi, dan larik A adalah [3,10,8,5,4]Jik A[0] A[4] k k il i l h ilJika A[0] > A[4] maka tukar nilai elemen, hasilnya tidak terjadi, dan larik A adalah [3,10,8,5,4]

2. Mengambil indeks 1 sebagai patokan, A[1] = 10, bandingkan A[1] dengan A[2], A[3], A[4]Jika A[1] > A[2] maka tukar nilai elemen, hasilnya A[1] menjadi 8, dan larik A menjadi [3 8 10 5 4][3,8,10,5,4]Jika A[1] > A[3] maka tukar nilai elemen, hasilnya A[1] menjadi 5 dan larik A menjadihasilnya A[1] menjadi 5, dan larik A menjadi [3,5,10,8,4]Jika A[1] > A[4] maka tukar nilai elemenJika A[1] > A[4] maka tukar nilai elemen, hasilnya A[1] menjadi 4, dan larik A menjadi [3,4,10,8,5][ , , , , ]

3. Mengambil indeks 2 sebagai patokan, A[2] = 10 bandingkan A[2] dengan A[3] A[4]10, bandingkan A[2] dengan A[3], A[4]Jika A[2] > A[3] maka tukar nilai elemen, hasilnya A[2] menjadi 8, dan larik A menjadi [3,4,8,10,5][ ]Jika A[2] > A[4] maka tukar nilai elemen, hasilnya A[2] menjadi 5 dan larik A menjadihasilnya A[2] menjadi 5, dan larik A menjadi [3,4,5,10,8]

4. Mengambil indeks 3 sebagai patokan, A[3] = 10 bandingkan A[3] dengan A[4]10, bandingkan A[3] dengan A[4]Jika A[3] > A[4] maka tukar nilai elemen, hasilnya A[3] menjadi 8, dan larik A menjadi [3,4,5,8,10][ ]

Jadi, hasil pengurutannya adalah 3,4,5,8,10

Secara algoritma, metode buble sort memerlukan dua buah indeks yaitumemerlukan dua buah indeks yaitu1. Sebagai patokan bergerak dari 1 hingga ke 

n‐1 dimana n adalah banyak elemen (0 s/d 4))

2. Sebagai pembanding mulai dari posisi indeks patokan + 1 sampai n dimana nindeks patokan + 1 sampai n dimana n adalah banyak elemen (1 s/d 4)

Algoritma Bubble SortDeklarasi

integer A[ ]  {10,8,3,5,4}integer i, j, temp

Deskripsifor(i 0, i<4, i i+1)

f (j (i 1) j 5 j j 1)for(j (i+1), j<5, j j+1)if (A[i] > A[j])

temp  A[i]A[i] A[j]A[i]  A[j]A[j]  temp

endifendforendfor

endfor{tampilkan hasil}for(x 0 x<6 x x+1)for(x 0, x<6, x x+1)

cetak B[x]endfor

public class BubbleSort{

bli t ti id i (St i [])public static void main(String args[]){

int A[] = {10,8,3,5,4};int A[]   {10,8,3,5,4};int temp ;for (int h=0; h<5; h++)

System.out.print(A[h]+" ");System.out.println(" ");for(int i 0 i<4 i++)for(int i=0; i<4; i++){

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

if(A[i]>A[j]){

t A[i]temp = A[i];A[i] = A[j];A[j] = temp;A[j]   temp;

}}

}for(int k=0; k<5; k++)

System out print(A[k]+" ")System.out.print(A[k]+   );

}}}

Metode insertion sort  pengurutan dengancara mengambil satu elemen berurut daricara mengambil satu elemen berurut dari posisi awal satu persatu kemudian menyisipkan elemen larik tersebut padamenyisipkan elemen larik tersebut padaposisi yang tepat.

Misalkan terdapat larik B dengan elemenMisalkan terdapat larik B dengan elemen‐elemennya {25,27,10,8,76,21}, agar dapat t t l i d i t k il k bterususun urut mulai dari tekecil ke besar , maka langkah yang dilakukan adalah b i b ik tsebagai berikut

1. Ambil nilai elemen pertama, B[0] = 25, sebagai posisi urut pertama

2 Ambil nilai elemen kedua B[1] = 27 bandingkan B[0] dan2. Ambil nilai elemen kedua, B[1] = 27, bandingkan B[0] dan B[1], posisi sudah tepat

3. Ambil nilai elemen B[2]=10, bandingkan dengan B[0] B[1] [ ] g g [ ] [ ]dan B[2], geser B[1] ke B[2], geser B[0] ke B[1], kemudian sisipkan B[2] ke B[0], sehingga larik B menjadi {10. 25, 27, 8, 76, 21}, , }

4. Ambil nilai elemen B[3]=8,  bandingkan dengan B[0], B[1], B[2], geser B[2] ke B[3], geser B[1] ke B[2], geser B[0] ke B[1] sisipkan B[3] ke B[0] sehingga larik B menjadiB[1], sisipkan B[3] ke B[0], sehingga larik B menjadi {8,10,25,27,76,21}

5. Ambil nilai elemen B[4]=76, bandingkan dengan B[0], B[1], [ ] g g [ ] [ ]B[2], B[3], posisi sudah tepat

6. Ambil nilai elemen B[5] = 21, bandingkan dengan B[0] B[1] B[2] B[3] B[4] geserdengan B[0], B[1], B[2], B[3], B[4], geser elemen‐elemen mulai B[2] ke belakang, dan sisipkan B[5] ke B[3] sehingga larik Bdan sisipkan B[5] ke B[3], sehingga larik B menjadi {8,10,21,25,27,76} 

Algoritma pengurutan insertion sortDeklarasii t B[ ] {25 27 10 8 76 21}int B[ ]  {25,27,10,8,76,21}int i, temp, x, y

DeskripsiDeskripsifor ( i 1,i<6,i i+1 )

temp  B[i]p [ ]x 0{cari posisi}while(temp>B[x] && x<i)

x x+1d hilendwhile

{sisipkan pada posisi yang tepat}if(temp <= B[x])

{geser ke kanan}{geser ke kanan}for ( y i, y<x,y y+1)

B[y] B[y‐1]endforB[x] temp

endifendifEndfor{tampilkan hasil}f ( 0 6 1)for(x 0, x<6, x x+1)

cetak B[x]endfor

public class InsertionSort1{

public static void main (String args[])p ( g g []){

int B[] = {25,27,10,8,76,21};int i temp x y;int i, temp, x, y;for(i=2;i<6;i++){

temp = B[i];temp = B[i];x=0;//cari posisihil ( B[ ] && i)while(temp>B[x] && x<i)

{x=x+1;

}

//sisipkan pada posisi yang tepatif(temp <= B[x]){{

for(y=i;y>x;y‐‐){

B[y]=B[y‐1];B[y]=B[y 1];}B[x]=temp;

}}}for(int z=0;z<6;z++)

S i (B[ ] " ")System.out.print(B[z]+" ");System.out.println();

}}

Pencarian linear  membandingkan data kunci dengan seluruh data, mulai dari data pertama hingga data terakhirhingga data terakhir

Misalnya terdapat larik C dengan elemennya {10,4,14,7,5,23}, kemudian akan dicari data dengan { , , , , , }, gnilai 14, maka langkah yang dilakukan adalah

1. Membandingkan elemen pertama 10 dengan 14, h il tid khasil tidak sama

2. Membandingkan elemen kedua 4 dengan 14, hasil tidak samatidak sama

3. Membandingkan elemen ketiga 14 dengan 14 hasil sama

4. Tampilkan keterangan ditemukan

Algoritam pencarian metode linearDeklarasiint C [ ] {10 4 14 7 5 23}int C [ ]  {10,4,14,7,5,23}integer i, posisi, cari

Deskripsicari  14for(i 0,i<6,i i+1)

if(C[i]=cari)if(C[i] cari)posisi  iprint posisib kbreak

endifendfor

public class Cari{

public static void main (String args[]){{

int C[] = {10,4,14,7,5,23} ;int i, posisi, cari;cari 14cari = 14;for(i=0;i<6;i++){

if(C[i]==cari)if(C[i]==cari){

posisi = i;System out println("Data berada di posisi : "+posisi);System.out.println( Data berada di posisi :  +posisi);break;

}}}

}}

25

LN Harnaningrum, Algoritma dan pemrograman Graha ilmu 2009pemrograman, Graha ilmu,2009.Rinaldi Munir, Algoritma dan pemrograman, Informatika, 2005Dr. Suarga, M.Sc.,M.Math.,Ph.D., AlgoritmaDr. Suarga, M.Sc.,M.Math.,Ph.D., Algoritma dan pemrograman, Andi, 2012htt // t t i l i t /j /i dhttp://www.tutorialspoint.com/java/index.htm

1. Daftar Harga

d k l d l kProduk Baju Celana Kaos Sepatu Sandal Aksesoris

Harga 50000 45000 30000 37000 25000 15000

Urutkan data diatas dari mulai harga tertinggi ke rendahke rendah

2. Cari produk dengan harga antara 28000 hingga 32000

Carilah metode pengurutan dan pencarian data larik selain yang sudah dibahasdata larik selain yang sudah dibahas, tampilkan dalam bentuk activity diagram, pse docode dan implementasi programpseudocode, dan implementasi program bahasa java