Macam-macam Sorting dan Algoritma Searching

Macam-macam Sorting:

• Buble Sort :

Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.

• Selection Sort :

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.

• Insertion Sort :

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. 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.

• Shell Sort :

Merupakan algoritma yang stau jenis dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir

author: wikipedia

• Merge Sort :

Algoritma dirumuskan dalam 3 langkah berpola 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

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.

author : Swfung8

• Quick Sort :

Algoritma ini 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

Author: Matt Chan

• Heap Sort:

Heap sort adalah sorting yang menggunakan struktur data heap, dengan nilai parent selalu lebih besar dari pada nilai childnya.

Algoritma:

1. Buat suatu heap.
2. Ambil isi dari root masukkan kedalam sebuah array.
3. Hapus element root dengan mempertahankan properti heap.
4. Ulangi sampai tree menjadi kosong

author : Swfung8

• Bucket Sort :

Algoritma:

• Cari nilai maksimum dan minimum di array
• Inisialisasi array bucket Daftar <> unsur (ukuran maxValue – minValue + 1)
• Pindahkan elemen dalam array untuk bucket
• Write bucket keluar (dalam rangka) ke array yang asli

• Radix Sort:

Secara kompleksitas waktu, radix sort termasuk ke dalam Divide and Conquer.Namun dari segi algoritma untuk melakukan proses pengurutan, radix sort tidak termasuk dalam Divide and Conquer.

Radix sortmerupakan sebuah algoritma pengurutan yang mengatur pengurutan nilai tanpa melakukan beberapa perbandingan pada data yang dimasukkan.

Searching

ALGORITMA SEARCHING

1.      Pengertian Algoritma Pencarian (searching)

Pencarian(searhing) merupakan proses yang fundamental dalam pengolahan data. Proses pensarian adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama (baik bertipe dasar maupun bertipe bentukan).

Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan  langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut.  Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).

1.      Macam-macam Algoritma Pencarian (Searching)

1.1  Pencarian sekuensial (Sequential searching)

·         Pengertian

Pencarian Sekuensial (sequential searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana.  Pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa. Pencarian beruntun terbadi dua:

1.      Pencarian beruntun pada larik tidak terurut;

2.      Pencarian beruntun pada larik terurut.

·         Algoritma

Pencarian berurutan menggunakan prinsip sebagai berikut :

1.      data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

2.      Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data.

3.      Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari.

4.       Apabila sama, berarti data telah ditemukan.   Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada.

Kelemahan pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula. Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

(1)           i ← 0

(2)           ketemu ← false

(3)           Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

(4)           Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1

(5)           Jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan

·         Contoh

#include <stdio.h>

#include <conio.h>

void main(){

int data[8] = {8,10,6,-2,11,7,1,100};

 int cari;

   int flag=0;

  printf("masukkan data yang ingin dicari = ");scanf("%d",&cari);

   for(int i=0;i<8;i++){

                if(data[i] == cari) flag=1;

   }

   if(flag==1) printf("Data ada!\n"); 

else printf("Data tidak ada!\n");

getch();

return 1;

}

Dari program diatas, terlihat bahwa dilakukan perulangan untuk mengakses semua elemen array data satu persatu berdasarkan indeksnya.

• Program menggunakan sebuah variabel flag yang berguna untuk menadai ada atau tidaknya data yang dicari dalam array data.  Hanya bernilai 0 atau 1.
• Flag pertama kali diinisialiasasi dengan nilai 0.
• Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.
• Semua elemen array data akan dibandingkan satu persatu dengan data yang dicari dan diinputkan oleh user.

1.1  Pencarian Beruntun dengan Sentinel

·         Pengertian

Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian beruntun yang mangkus. Nilai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel.

· Algoritma

Procedure SeqSearchWithSentinel(input L: LarikInt, input n: integer, input x: integer, output idx: integer)

DEKLARASI

     I: integer

ALGORITMA

L[n+1]  ← X   {sentinel}

I ← 1

While (L[i] ≠ x) do

                 I ← i+1

Endwhile

If idx = n+1 then

                 idx  ← -1

else

                 idx ← 1

endif

·         Contoh

#include <stdio.h>

#include <conio.h>

void main(){

 int data[7] = {3,12,9,-4,21,6};

 int cari,i;

printf("masukkan data yang ingin dicari = ");scanf("%d",&cari);

data[6] = cari;

   i=0;

 while(data[i] != cari) i++;

 if(i<6) printf("Data ada!\n"); else printf("Data tidak ada!\n");

getch;

return 1;

}

1.1  Pencarian Biner (binary search)

·         Pengertian

Terdapat metode pencarian pada data terurut yang paling efficient, yaitu metode pencarian bagidua atau pencarian biner (binary search). Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.

BST adalah binary tree yang mana data di dalamnya tersusun sedemikian rupa sehingga pada setiap subtree di dalamnya berlaku:

setiap data di subtree kiri < data root subtree < setiap data di subtree kanan.

• Algoritma

class BinaryNode {

      void printInOrder( )‏

      {

              if( left != null )‏

           left.printInOrder( );                               // Left

              System.out.println( element );            // Node

              if( right != null )‏

               right.printInOrder( );                          // Right

   }

}

class BinaryTree {

   public void printInOrder( )‏

   {

              if( root != null )‏

              root.printInOrder( );

   }

}

Prinsip dari pencarian biner dapat dijelaskan sebagai berikut :

1. mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2.
2. Kemudian data yang dicari dibandingkan dengan data tengah.
3. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
4. Jika lebih besar, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.
5. Demikian seterusnya sampai data tengah sama dengan yang dicari.

Algoritma pencarian biner dapat dituliskan sebagai berikut : 

•  Contoh

1.    L  ← 0

2.   R ← N - 1

3.   ketemu ← false

4.   Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8   

5.   m ← (L + R) / 2 83

6.    Jika (Data[m] = x) maka ketemu ← true

7.    Jika (x < Data[m]) maka R ← m – 1 Jika (x > Data[m]) maka L  ← m + 1

8.   Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

int binary_search(int cari){

int l,r,m;

 l = 0;

   r = n-1;

 int ktm = 0;

 while(l<=r && ktm==0){

                m = (l+r)/2;

               if(data[m] == cari) ktm=1;

               else if (cari < data[m]) r=m-1;

               else l=m+1; {

 if(ktm==1) return 1; else return 0;

}         

}                     

}

JENIS ALGORITMA PENCARIAN

  Dalam istilah bahasa inggris biasanya searching tuh artinya adalah pencarian sesuatu hal. Nah, kalau dalam bahasa pemograman, pencarian (searching) merupakan suatu tindakan untuk mendapatkan suatu data dalam kumpulan data. Kita bisa cari contoh yang simple aja dalam kehidupan sehari-hari  kita, mungkin kita ingin mencari suatu kata dalam kamus bahasa inggris, jika dicari satu persatu pasti kita akan kewalahan kali yah, bahkan bisa saja seharian kata yang kita cari tuh nggak ditemukan, capek banget kan?? hal itu akan menguras banyak waktu. Dengan adanya abjad A sampai dengan Z di pinggir kamus, maka kita dengan mudah dapat mencari kata tersebut. Hal itu kita bisa sebut dengan “Searching”. Dengan mengibaratkan “Searching” dalam kehidupan sehari-hari , maka kita akan lebih mudah memahami kata searching atau pencarian.

Dalam keperluan nya untuk mencari data, terdapat beragam algoritma pencarian (search algorithm). Mungkin, kalian bertanya-tanya, apa sih algoritma pencarian itu. Algoritma pencarian adalah “algoritma yang menerima sebuah argumen ‘a’ dan mencoba untuk menemukan sebuah rekaman yang memiliki kunci ‘a’. Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam memory komputer ataupun yang berada dalam penyimpanan ekternal (hardisk). Pencarian yang dilakukan terhadap data yang berada dalam komputer di kenal dengan pencarian internal sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian ekternal. Pencarian internal meliputi Pencarian sekuensial (sequential search) dan pencarian biner (binary search).



Pencarian Sekuensial

“Sequential search atau Pencarian sekuensial” bisa disebut dengan pencarian linear yang merupakan model pencarian yang paling simpel dan sederhana banget deh yang dapat dilakukan terhadap suatu kumpulan data. Suatu tekhnik pencarian dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.

Biar kalian lebih paham secara konsep, penjelasannya adalah sebagai berikut :
Keunggulan dari pencarian sekuensial ini adalah jika data yang dicari terletak di indeks array terdepan maka waktu dalam pencarian nya sangat cepat, dalam artian waktu yang minim sekali. Keburukannya adalah kalau jika data indeks array nya yang dicari paling belakang, maka waktu yang dicari tuh lama banget (maksimal).

Terdapat L yang merupakan larik yang berisi n buah data ( L[0],L[1]…….L[n-1]) dan k adalah data yang akan dicari. Pencarian dilakukan untuk menemukan L[i] = k dengan i adalah bilangan indeks terkecil yang memenuhi kondisi 0<= k <=n-1. Tentu saja bahwa data yang di cari tidak ditemukan. Jika misalnya terdapat angka 4, maka ditulis ada, sedangkan jika dimunculkan angka 6, namun angka 6 tidak ada maka akan muncul tulisan tidak ada. Berikut merupakan program yang telah dibuat sebelumnya : L = {4,12,9,-2,12,7,1,100} Tahukah kamu dimana posisi 12 yang pertama ? Nah, dalam hal ini k adalah 12 dan k ditemukan berupa indeks 2. Angka 12 yang pertama akan dipilih oleh program, karena secara logika angka 12 merupakan data yang pertama muncul. Coba deh kamu bayangin aja misalnya dalam antrian, orang yang mengantri di depan akan duluan mendapatkan giliran

Pencarian terhadap data urut “ Pencarian Binari ( Binary Search)” :

“Pencarian Sekuensial” akan memakan banyak waktumu apabila mencari data indeks array yang paling akhir dan ditambah lagi kalau datanya tu banyak banget Apalagi kumpulan data udah dalam keadaan urut, Untuk mengatasi masalah ini dan untuk menyingkat waktu terdapat algoritma yang dirancang agar pencarian data dilakukan secara efesien. Metode yang digunakan dikenal dengan sebutan “pencarian biner atau binary search”. Metode ini merupakan tekhnik pencarian data dalam dengan cara membagi dua bagian setiap kali terjadi proses pengurutan.

Data yang dicari harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama besar atau berbeda 1 jika jumlah data semula ganjil. Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama, jika lebih besar dari data tengah maka akan diulang dari awal dengan +1, jika lebih kecil maka sebaliknya, dari data tengah maka -1. Dalam hal ini ada empat kemungkinan yang terjadi yaitu :

1. Data yang dicari sama dengan elemen terakhir pada bagian pertama dalam larik. Jika kondisi ini terpenuhi, data yang dicari berarti ditemukan. Data dicari dari posisi satu sampai posisi akhir N. jika tidak diketemukan maka data akan terus mencari sampai menemukan data yang sama.
2. Data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam lari. Pada keadaan ini, pencarian diteruskan pada bagian pertama.
3. Data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua.
4. Pada pengurutan biner, data akan dibandingkan dengan data yang ditengahnya, data tengah dicari dengan menjumlahkan posisi awal dengan posisi akhir kemudian hasil jumlah data tersebut dibagi menjadi 2. Data tersebut akan dibandingkan dengan data yang ditengah apakah akan lebih besar atau lebih kecil

Untuk mengetahui kekurangan dan kelebihan masing-masing metode, saya akan mengambi kesimpulan dari penjelasan diatas.

“Pencarian Sekuensial (sequential search)” :

1. Relatif lebih cepat dan efisien, dapat menghemat waktumu karena pencarian datanya cepat.
2. Untuk data yang terbatas tetapi kurang cepat untuk data dalam jumlah besar (pencarian datanya lama banget, apalagi mencari indeks array yang paling akhir)
3. Algoritma-Nya agak sederhana
4. Beban komputasi nya cenderung lebih besar

“Pencarian Biner (binary search)” :

1. Sangat rumit, membutuhkan waktu yang lebih banyak.
2. Untuk data dalam jumlah besar, waktu searching lebih cepat tetapi data harus sudah di-sorting lebih dulu (  dalam keadaan terurut ), jadi mesti mengurutkan data terlebih dulu.
3. Algoritma-Nya agak rumit, tapi hasilnya bisa memuaskan kamu lho, soalnya agak cepat dalam pencarian datanya
4. Beban komputasi-nya lebih kecil, tidak baik untuk data berangkai

Pencarian List

Algoritma pencarian list adalah algoritma pencarian paling dasar. Tujuannya adalah mencari sebuah elemen dari sebuah himpunan dengan suatu kunci (kemungkinan memuat informasi yang terkait dengan kunci).