Tools BasisData, Pengenalan DDL & DML

Setting Operation, Multiple Relation & Subquery Bersarang

View, Ordering, Grouping, Having, Procedure & Function

Trigger, Ranking & Intergrasi DataBase

Join (Natural, Outer & Inner)

Pengantar SQL & Modifikasi DataBase

Macam-Macam Sorting Algoritma Dan Pemrograman C++

Macam-Macam Sorting

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.

Bubble Sort

Bubble Sort merupakan cara pengurutan yang sederhana. Konsep dari ide dasarnya adalah seperti “gelembung air” untuk elemen struktur data yang semestinya berada pada posisi awal.
Cara kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping) terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal tersebut, nilai dari dua elemen struktur data dibandingkan. Jikaternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap). 

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

Algoritmanya :

void quickSort(Object array[], int leftIdx, int rightIdx) { int pivotIdx; /* Kondisi Terminasi */ if (rightIdx > leftIdx) { pivotIdx = partition(array, leftIdx, rightIdx); quickSort(array, leftIdx, pivotIdx-1); quickSort(array, pivotIdx+1, rightIdx); } }

Diagram Quick Sort

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

Algoritmanya :

void mergeSort(Object array[], int startIdx, int endIdx) { if (array.length != 1) { //Membagi rangkaian data, rightArr dan leftArr mergeSort(leftArr, startIdx, midIdx); mergeSort(rightArr, midIdx+1, endIdx); combine(leftArr, rightArr); } }

Graf & Pohon

PENGERTIAN GARAF

            Graf adalah salah satu jenis Struktur data yang terdiri dari titik (vertex) dan garis (edge), dimana        dalam tersebut, vertex-vertex yang dihubungkan oleh edge, hingga menjadi suatu kesatuan yang                disebut graf.

Algoritma Djikstra 

A. Definisi Algoritma Djikstra

Algoritma  Dijkstra,   (penemunya   adalah   seorang   ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.

B. Tujuan Algoritma Dijkstra

1.    Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.

2.    Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.

3.    Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.

C. Urutan Logika Algoritma Dijkstra

1.    Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).

2.    Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.

3.    Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.

4.    Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

5.    Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

Contoh :

Titik mengambarkan lokasi dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama tentukan titik yang akan menjadi nomor kode (node) awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, lalu akan dilakukan pengembangan pencarian dari satu titik ke titik selanjutnya (tahap demi tahap).

Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai 

SORTING (PENGURUTAN)

Sorting secara umum bisa didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting merupakan satu dari banyak pekerjaan komputer yang dilakukan, yang diteliti secara luas, dan memiliki banyak algoritma yang berbeda yang dibangun. Sorting (mengurutkan) data memiliki dampak yang sangat penting dalam pencarian. Data yang tidak terurut harus dicari secara normal menggunakan suatu pembacaan sekuensial (sequential scan) dari semua data. Data yang telah terurut membiarkan dirinya untuk dicari menggunakan teknik pencarian yang sederhana. 

Secara umum ada 2 jenis sorting, yaitu secara Ascending (terurut naik) dan Descending (terurut turun). Dalam hal pengurutan data yang bertipe string atau char, nilai data dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence) seperti yang dinyatakan dalam tabel ASCII. Tujuan pengurutan data adalah untuk mempermudah pencarian data. Pengurutan data menjadi sesuatu yang penting dalam ilmu komputer karena waktu yang diperlukan untuk melakukan proses pengurutan perlu dipertimbangkan.  

Data yang akan diurutkan tentu sangat bervariasi baik dalam hal banyak data maupun jenis datanya. Sayangnya, tidak ada satu algoritma yang terbaik untuk setiap situasi yang kita hadapi. Bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain : banyak data yang akan diurutkan, kapasitas pengingat apakah mampu menyimpan semua data yang dimiliki, dan tempat penyimpanan data.

Pengurutan Internal (Internal Sorting)

Algoritma Internal Sorting seringkali mengklasifikasikan berdasarkan jumlah dari pekerjaan yang diminta untuk mengurutkan urutan elemen. Banyaknya pekerjaan mengarah pada dua operasi dasar dari sorting : membandingkan dua elemen dan memindahkan suatu elemen dari satu tempat ke tempat lainnya. Teknik internal sorting yang utama dibagi ke dalam 3 kategori dengan tanggung jawab ke pekerjaan yang dibutuhkan untuk mengurutkan suatu urutan dari n elemen-simple sort, advanced sort dan radix sort.

A. TEKNIK PENGURUTAN SEDERHANA ( SIMPLE SORT

     TECHNIQUES)
 Selection Sort ( Metode Seleksi )

Operasi dasar dalam suatu selection sort adalah seleksi dari elemen yang terkecil (atau yang terbesar) dari urutan suatu elemen. Gambar berikut akan menggambarkan proses untuk suatu urutan.

Ascending 

• Cek seluruh elemen array, temukan nilai terkecil (1) dan tukarkan posisinya dengan posisi nilai yang tersimpan pada posisi pertama dari array (3)
• Temukan nilai terkecil kedua (2), dan tukarkan posisinya dengan nilai yang berada pada posisi kedua (10)
• .

• Dua elemen biru pertama tidak akan berubah lagi sebab mereka sudah merupakan nilai terkecil pertama dan kedua dalam array tsb.

• Sekarang, ulangi dengan cara/proses “pilih dan tukar

Algoritma

Procedure selectsort(var r:list; n: integer); Var j, k, small: integer; Begin  If n > 1  Then begin   For k := 1 to n – 1 do   Begin    Small := k;    For j := k + 1 to n do    If r[j] < r[small]     Then small := j;    Swap(r[k], r[small])   End   End End;

 

Logika dari prosedur SelectSort adalah kekhususan dari algoritma pengurutan sederhana, yang terdiri atas loop luar (outer loop) dan loop dalam (inner loop). Dalam prosedur SelectSort masing-masing diimplementasikan menggunakan Pascal untuk membangunnya. Inner loop dieksekusi mengikuti nomor waktu :

Outer loop dieksekusi sebanyak n-1 kali. Masing-masing eksekusi dari inner loop memerlukan satu perbandingan dan satu nomor yang tidak diketahui. Masing-masing eksekusi dari outer loop memerlukan satu perubahan. Total usha yang dilakukan :

Perubahan = n – 1

Perbandingan = ½ n( n - 1 )

Yang perlu diperhatikan bahwa usaha yang diperlukan, seperti yang diukur oleh perbandingan dan perubahan, adalah pengurutan independen dari data yang diurutkan. Pada sisi negatif, SelectSort memerlukan  O(n2) perbandingan tidak perduli bagaimana inisial data diurutkan. Sisi positifnya, ia tidak pernah memerlukan lebih dari O(n) perpindahan. Inilah yang membuat SelectSort sebagai metode yang baik untuk elemen yang besar (yang mahal untuk perpindahan) dengan pilihan pengurutan yang pendek (mudah untuk dibandingkan).

      Bubble Sort

Operasi dasar dalam Exchange Sort adalah menukarkan sepasang elemen yang berdekatan. Metode ini mudah dipahami dan diprogram, tetapi tidak efisien. Secara keseluruhan proses pengurutan terdiri dari satu nomor yang melintasi data.  Masing-masing lintasan dimulai pada suatu akhir dari array dan bekerja ke akhir yang lainnya. Masing-masing pasangan elemen yang keluar dari urutan ditukarkan. Gambar berikut akan menggambarkan proses dari pengurutan secara ascending (dari kecil ke besar ).

Proses pertama(1, 3, 7, 6, 5) menjadi (1, 3, 7, 6, 5)(1, 3, 7, 6, 5) menjadi (1, 3, 7, 6, 5)(1, 3, 7, 6, 5) menjadi (1, 3, 6, 7, 5)(1, 3, 6, 7, 5) menjadi (1, 3, 6, 5, 7)Proses kedua(1, 3, 6, 5, 7) menjadi (1, 3, 6, 5, 7)(1, 3, 6, 5, 7) menjadi (1, 3, 6, 5, 7)(1, 3, 6, 5, 7) menjadi (1, 3, 5, 6, 7)(1, 3, 5, 6, 7) menjadi (1, 3, 5, 6)

Lintasan pertama memindahkan elemen terbesar ke posisi ke-n, membentuk list terurut pertama. lintasan kedua hanya memikirkan n-1 elemen. Lintasan kedua memindahkan elemen terbesar kedua ke posisi n – 1. Oleh karena itu lintasan ketiga hanya perlu memperhatikan n – 2 elemen. Secara umum setelah i melintas elemen terbesar ke i akan berada pada posisi terakhir, maka lintasan i + 1 hanya perlu memperhatikan i – 1 elemen. Dalam metode ini elemen yang kecil berpindh secara pelan, atau menggelembung, kearah atas. Oleh karena itu teknik pengurutan ini sering disebut dengan buble sort. 

Jika tidak ada perubahan yang terjadi selama satu lintasan  yang melintasi data maka data diurutkan dan proses berhenti. Pengecekan dilakukan untuk melihat jika ada suatu perubahan yang terjadi pada lintasan dengan menggunakan variable boolean sorted. Pada awal setiap  lintasan sorted diset ke true. Jika terjadi suatu perubahan, kemudian sorted diset ke false (pada kenyatannya, sorted diset ke false setiap suatu  perubahan terjadi., tidak hanya pertama kali).

Algoritma

Procedure exchangesort(var r: list; n: integer); Var j, k, small: integer;  Sorted: boolean; Begin  K := n; sorted := false;  While (k > 1) and (not sorted) do  Begin   Sorted := true;   For j := 1 to k – 1 do    If r[j] > r[j+1]    Then begin     Swap(r[j],r[j + 1]);     Sorted := false    End;    K := k – 1  End; End;

Dalam prosedur exchangesort loop keluar diimplementasikan dengan satement while dalam Pascal, dan loop ke dalam dengan statement for dalam Pascal. Loop kedalam dieksekusi mengikuti nomor waktu :

dimana ksorted adalah nomor dari eksekusi dari loop keluar sebelum disana ada lintasan selama disana tidak ada perubahan. Loop kedalam memiliki satu perbandingan dan beberapa kali perubahan. Performa terbaik yang terjadi ketika ksorted adalah 1. Hal ini berarti tidak ada perubahan yang terjadi karena data asli telah diurutkan. Nomor perbandingan digunakan oleh prosedur exchange sort untuk menentukan :

Performa terburuk yang terjadi ketika  ksorted adalah n – 1. loop dalam kemudian dieksekusi mengikuti nomor waktu : Ketika menterjemahkan eksekusi loop kedalam pertukaran dan perbandingan, maka akan diperoleh : · worst case (kejadian terburuk) pertukaran = ½ n(n-1) perbandingan = ½ n(n-1) · sorted data (data terurut) pertukaran = 0 perbandingan = n - 1 Suatu ExchangeSort memiliki dua kekurangan. Pertama, inner loop mengandung  suatu pertukaran yang memerlukan tiga perubahan. Dalam SelectSort tidak ada perpindahan dalam inner loop. Kedua, ketika suatu elemen dipindahkan, ia selalu dipindahkan ke posisi terdekat. Dalam SelectSort suatu elemen mungkin berpindah ke jarang yang jauh dan selalu berpindah ke  posisi yang diurutkan. Jadi ExchangeSort  algoritma pengurutan terlam.

Insertion Sort ( Metode Penyisipan Langsung )

Operasi dasar dalam insertion sort adalah penyisipan suatu elemen tunggal kedalam urutan elemen yang telah diurutkan sehingga hasil dari urutan masih tetap terurut. Gambar tersebut mengilutrasikan proses yang terjadi pada 5 elemen, dengan setiap elemennya merupakan bilangann integer.  Data yang digunakan untuk input merupakan array 5 bilangan integer (gambar (a)). Ketika elemen ke lima, 235, diperhatikan, …  Dalam transisi dari gambar (a) ke gambar (b) terjadi penysisipan 45 ke dalam daftar elemen yang telah diurutkan. Sealama 45 kurang dari 235, penyisipan 45 merupakan puncak dari daftar. Sebagaimana ditampilkan dalam gambar (b), segmen yang terurutkan mempunyai panjang dua. 

Transisi dari gambar (b) ke gambar (c) diselesaikan dengan memasikkan 182 ke dalam daftar elemen yang telah diurutkan. Selama 182 terletak diantara 35 dan 235, 182 disisipkan diantara 45 dan 235 dengan memindahkan 45 ke atas yang menciptakan suatu ruangan. Daftar subset yang terurut tersebut sekarang mempunyai panjang tiga.  Gambar (d) diperoleh dengan menyisipkan 205 ke dalam daftar elemen yang telah diurutkan, dilakukan dengan memindahkan 45 dan 182 naik untuk menjadikan ruangan. Terakhir, gambar (e) diperoleh dengan memasukkan 390 ke dalam daftar elemen (dengan panjang empat) yang telah terurut. 

Gambar mengilustrasikan prosedur yang terdapat pada algoritma insertion sort. Algoritma melakukan penyisipan dengan melakukan dibawah elemen untuk disisipkan. Setiap elemen yang kecil dibandingankan dengan elemen yang akan disispkan posisinya dinaikkan satu tingkat. Selama elemen yang ditemukan lebih besar dibandingkan dengan elemen yang akan disisipkan, pencarian akan dihentikan dan penyisipan terjadi didepan elemen yang besar.

contoh:

contoh lain : 
12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13

Algoritma      

Procedure insertsort(var r; list; n: integer); Var j, k, save: integer; Begin  For k := n – 1 downto 1 do  Begin   j := k + 1;save := r[k];   r[n + 1] := save;      while save > r[j] do begin    r[j – 1] := r [j];    j := j + 1;   end; r[j – 1] := save end; end;

           

Perulangan sebelah luar dari prosedur insertsort selalu dieksekusi sebanyak n-1 kali. Banyakanya ekseskusi yang terjadi pada perulangan sebelah dalam tergantung pada nilai k dan urutan data. Dalam kasus data yang telah diurutkan, perulangan sisi dalam tidak pernah dieksekusi. Dalam kasus terburuk akan dieksekusi sebanyak :

Dengan memberikan semua inisial pengurutan data yang mungkin terjadi, rata-rata perulangan dalam yang terjadi dieksekusi setengah dari kasus terburuk. Hal tersebut terjadi karena perulangan sisi dalam pada prosedur insertsort memeriksa daftar yang telah terurut dicari elemen pertama yang lebih besar dari satu yang disipkan. Rata-rata perintah tersebut menguji setengah dari daftar yang ada.  Insertsort perulangan sisi dalam membutuhkan usaha yang lebih besar dibandingkan dengan selectsort perulangan sisi dalam – satu perpindahan melawan tidak ada perpindahan sama sekali. Tapi membutuhkan usaha yang lebih kecil dibandingkan dengan exchangesort.

Untuk elemen yang pendek, pemindahan dalam perulangan sisi dalam lebih dari diseimbangkan dengan seringkali hanya mengeksekusi setengah perulangan sisi dalam, dan insertosrt memberikan kinerja yang lebih baik.  Karena overhead yang rendaj dan kinerja yang cukup tinggi untuk dtaa terurut, insertsort akan dikombinasikan dengan quicksort untuk menghasilkan algoritma pengurutan internal serbaguna yang terbaik untuk saat ini. Sejauh ini, pengurutan data yang disimpan dalam doubly linked list tidak dibahas, bab selanjutnya membahas tentang implementasi insertion sort pada linked list. 

sumber :

http://yogapratama1205.blogspot.com/2015/06/penjelasan-tentang-sorting-selection.html

http://yogapratama1205.blogspot.com/2015/06/penjelasan-tentang-sorting-selection.html

https://www.geeksforgeeks.org/insertion-sort/

PENGERTIAN BINARY SEARCH

         Binary search adalah metode pencarian suatu data atau elemen di dalam suatu array dengan kondisi data dalam keadaan terurut. Proses pencarian binary search hanya dapat dilakukan pada sekumpulan data yang sudah diurutkan terlebih dahulu. Prinsip dari binary search terhadap N elemen dapat dijelaskan seperti berikut:

      1. Tentukan posisi awal = 0 dan posisi akhir = N-1.

      2. Hitung posisi tengah = (posisi awal + posisi akhir)/2. 

      3. Bandingkan data yang dicari dengan elemen posisi tengah.

      4. Jika sama maka catat posisi dan cetak kemudian berhenti.

     5. Jika lebih besar maka akan dilakukan pencarian kembali kebagian kanan dengan posisi awal  =  

          posisi tengah +1 dan posisi akhir tetap kemudian ulangi mulai poin 2.

      6. Jika lebih kecil maka akan di lakukan pencarian kembali ke bagian kiri dengan nilai posisi awal

     tetap dan nilai posisi akhir  = posisi tengah-1 kemudian ulangi mulai poin 2.

    Proses pencarian dilakukan untuk mengetahui apakah data yang dicari terdapat pada sekumpulan data yang ada. Selain untuk mengetahui keberadaan data, informasi yang lain yang bisa didapat adalah letak dari data tersebut. Adapun jenis pencarian yaitu:
Pencarian Bagi Dua (Binary Search)
Pencarian Beruntun (Sequential Search)

Binary Search
 Binary search atau pencarian bagi dua adalah salah satu metode pencarian data salah satu nya Linear Search yang bisa kalian lihat sendiri pada link disamping ,Binary search mempunyai kelebihan dan kekurangan bila dibandingkan dengan Linear search , salahn satu nya binary search pencarian nya lebih cepat tapi agak sedikit susah untuk di mengerti bila dibandingkan dengan Linear Search yang lumayan simpel .
            Sebenarnya binary Search ini sering kita terapkan pada kehidupan kita sehari - hari . salah satu contoh nya yaitu , Saat kita mencari kata di kamus maka kita akan membuka buku itu menjadi dua bagian , dan membuka nya lagi menjadi dua bagian dan seterus nya sampai ketemu , bagaimana jika kalian ingin mencari suatu kata di kamus dengan menggunakan metode linear search ? tentu akan sangat lama ,karena linear search konsep pencarian dengan beruntun dari halaman pertama sampai terakhir dan sebalik nya secara terurut , jadi tidak mungkin mencari nya dengan linear search .
Jadi binary search ini sangat dianjurkan untuk digunakan saat mencari data yang data nya banyak .

                                                                         

    contoh program:

  #include <iostream>

  #include <conio.h>

  #include <iomanip>   

      

  using namespace std;

  int main()

{

    //Pendeklarassian variabel

    int nilai[20];

    int i,j,n;

    int temp, awal, akhir, tengah, bilangan;

    //Proses penginputan data

    cout<<"Banyak Bilangan: ";

    cin>>n;

    for(i=0;i<n;i++)

    {

        cout<<"Elemen ke-"<<i<<" =";

        cin>>nilai[i];

    }

    cout<<"\n\nElemen sebelum diurut  = ";

    for(i=0;i<n;i++)

    {

        cout<<setw(3)<<nilai[i];

    }

    //Proses pengurutan data

    for(i=0;i<n-1;i++)

    {

        for(j=i+1;j<n;j++)

        {

            if(nilai[i]>nilai[j])

            {

                temp = nilai[i];

                nilai[i]=nilai[j];

                nilai[j]=temp;

            }

        }

    }

    cout<<"\nElemen Setelah Di Urut = ";

    for(i=0;i<n;i++)

    {

        cout<<setw(3)<<nilai[i];

    }

    cout<<"\nIndeks Elemen           =";

    for(i=0;i<n;i++)

    {

        cout<<setw(3)<<i;

    }

    cout<<"\n\nMasukan data Yang Akan Anda Cari: ";

    cin>>bilangan;

    //Proses pencarian data

    awal = 0;

    akhir =n-1;

    do

    {

        tengah = (akhir+awal)/2;

        if(bilangan < nilai[tengah])

        {

            akhir = tengah -1;

        }

        else

        {

            awal = tengah +1;

        }

    }

    while((akhir>=awal)&&(nilai[tengah] !=bilangan));

    {

        if (nilai[tengah]==bilangan)

        {

            cout<<"\nData "<<bilangan<<" Ada dalam Array";

            cout<<"Pada posisi "<<tengah;

        }

        else

        {

            cout<<"\nData "<<bilangan<<" tidak ada dalam array\n";

        }

    }

    getch();

    return 0;

          sumber:  https://www.geeksforgeeks.org/binary-search/

         http://mimpi-kecilku.blogspot.com/2015/06/pengertian-binary-search-dan-contoh.html