Bubble Sort

Algoritma untuk sorting data, atau kata lainnya mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending atau Descending).  Algoritma Bubble Sort adalah algoritma sorting paling sederhana. proses pengurutannya mirip seperti gelembung. Terdapat proses pertukaran atau istilah kerennya swapping.

Membuat urutan pada angka yang masih acak, baik dari yang terbesar ataupun dari yang terkecil (ascending / descending)

Algoritma ini seolah olah menggeser satu per satu elemen dari kenan ke kiri atau kiri ke kanan. tergantung jenis pengurutannya. Ketika suatu proses telah selesai, maka bubble sort akan mengalami proses, demikian seterusnya.

Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan,serta tercapai pengurutan yang telah diinginkan

     5  1  4  2  8
Kondisi awal adalah pada posisi J = 0. Pertama, kita bandingkan antara Bil[0] dengan Bil[1]. Bil[0] = 5 sedangkan Bil[1] = 1. Berdasarkan aturan bubble sort, isi dari Bil[0] tidak sesuai letaknya karena lebih besar dari isi Bil[1]. Sehingga, kita perlu menukar isi dari dua elemen array ini, sampai Bil[0] = 1 dan Bil[1] = 5 (perhatikan baris pada J = 1). Langkah berikutnya kita membandingkan Bil[1] dengan Bil[2]. Bil[1] = 5 dan Bil[2] = 4, sehingga kembali kita harus menukar isi dari elemen ini (perhatikan baris J = 2). Hal ini terus dilakukan sampai pada perbandingan Bil[3] dengan Bil[4].

  Algoritma :
1. Tentukan jumlah bilangan yang akan diinput
2. Inputkan bilangan 4, 2, 3, 8, 5
3. Bandingkan bilangan 1> / < bilangan 2
4. Jika benar pindahkan bilangan 2 ke bilangan siap
5. Pindahkan bilangan 1 ke bilangan 2
6. Pindahkan bilangan sisip ke bilangan 1
7. Jika tidak lanjutkan proses
8. Bandingkan bilangan 2> / < bilangan 3
9. Jika benar pindahkan bilangan 3 ke bilangan siap
10. Pindahkan bilangan 2 ke bilangan 3
11. Pindahkan bilangan sisip ke bilangan 2
12. Jika tidak lanjutkan proses
13. Ulangi langkah no 3 hingga hasil sesuai yang 
      diinginkan 

Sorting

Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting adalah proses pengurutan.

1. Pengurutan internal (internal sort), yaitu   pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai pengurutan tabel

2. Pengurutan eksternal (external sort), yaitu pengurutan datayang disimpan dalam memori sekunder, biasanya databervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.

2 Metode sorting diantaranya adalah :
1. Selection Sort
2. Insertion Sort

1. Selection Sort

Inti dari algoritme selection sort adalah menemukan elemen tertinggi dan terendah di array acak lalu menempatkannya di posisi yang semestinya.

Diketahui array A=[7,5,4,2]A=[7,5,4,2] akan disortir dengan urutan ascending (urutan naik).

Elemen terendah pada array, 22, akan dicari dan ditukar posisinya dengan elemen di posisi teratas, yaitu 77. Sekarang pencarian dilakukan untuk menemukan elemen terendah yang ada di array awal yang belum beraturan dan menempatkannya di posisi kedua, dan seterusnya. 

Komplesitas Waktu:

Untuk menemukan elemen terendah dari array berukuran NN elemen, pembanding N−1N−1diperlukan. Setelah menempatkan elemen terendah di posisi semestinya, ukuran array acak berkurang ke N−1N−1 lalu pembanding N−2N−2 diperlukan untuk menemukan nilai terendah di array acak.

Maka dari itu

(N−1)(N−1) + (N−2)(N−2) + …….……. + 11 = (N⋅(N−1))/2(N⋅(N−1))/2 pembanding dan NN bertukar hasil di kompleksitas keseluruhan O(N2)O(N2).

2. Insertion Sort

Konsep insertion sort berdasarkan pada gagasan bahwa satu-persatu elemen dari elemen input hanya akan digunakan sekali pada setiap iterasi untuk menemukan posisi yang semestinya.

Teknik ini melakukan iterasi pada elemen input dan menjadikan array yang disortir lebih besar pada tiap iterasi. Insertion sort membandingkan suatu elemen dengan elemen yang memiliki nilai tertinggi dalam array yang disortir.

Jika elemen pembanding bernilai lebih besar, maka elemen tersebut akan menggantikan tempat elemen yang lebih kecil dan elemen yang lebih kecil akan menjadi elemen pembanding sampai posisi yang tepat ditemukan. Cara ini dilakukan dengan memindahkan semua elemen yang lebih besar terhadap elemen sebanyak satu posisi.

Karena 7 adalah elemen pertama dan tidak ada elemen lain sebagai pembanding, 7 tetap berada di posisinya. Sekarang saat beralih ke 4, 7 merupakan elemen tertinggi di daftar tersortir dan bilangan tersebut lebih besar dibandingkan 4. Jadi, 4 ditempatkan ke posisi yang tepat yaitu sebelum 7. Sama halnya dengan 5, karena 7 (elemen terbesar di daftar tersortir) lebih besar dibandingkan 5, kita akan menempatkan 5 ke posisi semestinya. Terakhir, untuk 2, semua elemen ada di sisi kiri dari 2 (daftar tersortir) berpindah satu posisi karena semua bilangan lebih besar daripada 2, lalu 2 ditempatkan di posisi pertama. Array tersebut akan menjadi array tersortir.

Komplesitas Waktu:

Pada skenario terburuk, semua elemen dibandingkan dengan semua elemen lain pada array tersortir. Untuk elemen NN akan ada N2N2 pembanding. Oleh karena itu, kompleksitas waktu adalah O(N2)

Graph

 Graph adalah suatu struktur data yang  berbentuk network / jaringan dimana hubungan antara elemen-elemennya  adalah many-to-many . contoh dalam kehidupan sehari-hari yang berbentuk graph ini cukup banyak , misalnya: hubungan dosen dengan mahasiswa, dimana satu dosen bisa mengajar  lebih dari satu mahasiswa, dan satu mahasiswa dapat memiliki lebih dari satu dosen.

Graph terdiri dari Node ( VERTEX) dan ARC ( EDGE ). Yang dimaksud dengan Node adalah elemen graph yang berisi informasi sedangkan ARC (Edge ) adalah Path yang menghubungkan dua buah node. Dua buah node yang dihubungkan  dengan edge juga disebut Adjacent Node

Suatu subset / bagian dari Graph dinamakan SubGraph. Sedangkan yang disebut dengan Path adalah hubungan dari kumpulan node-node dimana tiap node dengan node berikutnya dihubungkan dengan Edge. Sebuah path dikatakan simple  path bila setiap node hanya “muncul” satu kali dalam path tersebut.

Graph dibedakan  atas dua tipe , yaitu :

Ø Undirected GRAPH

Jika sepasang node yang membentuk edge  dalam graph tidak berarah seperti ditunjukkan oleh gambar di bawah ini :

Ø Directed Graph ( DiGraph )

Jika sepasang  node yang berbentuk edge dalam Graph mempunyai arah.

Representasi Graph

Graph dapat direpresentasi dengan dua cara yaitu : Adjancency List dan Adjacency Matrix. Dengan mempergunakan gambar di bawah ini sebagai contoh maka representasi graph dengan masing-masing cara dapat dijelaskan sebagai berikut :

1. Adjancency List

Direpresentasikan sebagai suatu list bisa dinyatakan  dengan LINKED-LIST atau ARRAY 

--------------------------------------------------
      NODE                  EDGE LIST
--------------------------------------------------
     a                               b    c
     b                               c    d   e

     c                               b    e   f
     d                              b    e   
     e                              b    c    d   f
     f                               c     e
---------------------------------------------------

2. Adjancency Matrix

Direpresentasikan dengan array 2 dimensi. Tipe komponen dari Array bisa digunakan BOOLEAN atau INTEGER ( untuk WEIGHTED GRAPH )

---------------------------------------------------------
|      |   a    |    b   |    c   |    d  |   e    |    f    |
---------------------------------------------------------
a      |   0    |   1    |    1   |  0    |    0    |   0   |
b      |   1    |   0    |    1   |  1    |    1    |   0   |
c      |    1   |    0   |    0    |  0    |    1   |   1   |
d      |   0    |   1    |    0    |  0    |    1   |   0   |
e      |   0    |   1    |    1    |  1    |    1   |   1   |
f       |   0    |   0    |    1    |   0   |    0   |   0   |
----------------------------------------------------------

1) Breadth-First Search 

Inti dari Breadth First Search(BFS) sendiri adalah pencarian yang dimulai dari root A. Pertama kita periksa root-nya A, setelah itu node – node yang bertetanggaan dengan A. Setelah selesai baru kita periksa semua node tetangga A yang bertentanggaan lagi, dan seterusnya. Selanjutnya kita harus mengikuti semua tetangga dari A dengan cermat, jangan sampai ada satu node yang diproses lebih dari satu kali. Semuanya dapat dilakukan dengan bantuan queue yang menyimpan node yang menunggu untuk diproses dan dengan menggunakan field STATUS untuk mengetahui status dari node.

Algoritmanya:

1. Inisialisasi semua node dalam keadalam ready. (STATUS = 1).

2. Letakkan root in queue dan ganti statusnya menjadi tunggu (STATUS = 2).

3. Ulangi langkah 4 dan 5 sampai queue kosong:

4. Pindahkan depan node N di queue. Proses N dan ganti statusnya menjadi sudah diproses (STATUS=3).

5.  Tambahkan ke belakang dari queue semua tetangga dari N yang dalam status ready saja (STATUS=1), lalu ganti statusnya (STATUS=2)

6. Exit

Adjacecy List

A:          F, C, B

B:          G, C

C:           F

D:          C

E:           D, C, J

F:           D

G:          C, E

J:           D, K

K:          E, G

2. Depth-First Search

Ide dari DFS ini hampir sama dengan BFS, hanya saja pada DFS kita akan menggunakan struktur

data Stack. Prosesnya pun sama dengan menggunakan ketiga status yang kita gunakan juga pada

BFS.

Contoh DFS :

Misalkan kita akan mencari semua
node yang bisa di jangkau 
oleh node J :

a. push J kedalam stack

       STACK : J

b. pop, dan cetak elemen teratas J,

kemudian push kedalam stack semua 

neighbor J (yang berada pada status ready)

       PRINT : J       STACK : D, K

Program Tree C++

Saya kali ini akan membuat program Tree melalui program C++
Berikut contoh codingan program Tree C++ :

#include<stdio.h>

typedef struct node{

 char data;

 node *kiri;

 node *kanan;

};

node *akar=NULL;

addNode(node **akar, char isi) {

 if((*akar)==NULL){

 node *baru;

 baru= new node;

 baru->data = isi;

 baru->kiri = NULL;

 baru->kanan = NULL;

 (*akar)=baru;

 }

}

preOrder(node *akar) {

 if(akar !=NULL) {

 printf("%c ", akar->data);

 preOrder(akar->kiri);

 preOrder(akar->kanan);

 }

}

inOrder(node *akar) {

 if(akar !=NULL) {

 inOrder(akar->kiri);

 printf("%c ", akar->data);

 inOrder(akar->kanan);

 }

}

postOrder(node *akar) {

 if(akar !=NULL) {

 postOrder(akar->kiri);

 postOrder(akar->kanan);

 printf("%c ", akar->data);

 }

}

main(){

char abjad;

printf("\n\n\tPosisi Awal Tree:\n\n");

printf("\t       R\n\t      / \\\n\t     A   E\n\t    /\n\t   S\n\t  / \\\n\t I   T\n\n");

addNode(&akar,abjad='R');

addNode(&akar->kiri,abjad='A');

addNode(&akar->kanan,abjad='E');

addNode(&akar->kiri->kiri,abjad='S');

addNode(&akar->kiri->kiri->kiri,abjad='I');

addNode(&akar->kiri->kiri->kanan,abjad='T');

 printf("Tampilan PreOrder  : ");

 preOrder(akar);

 printf("\nTampilan InOrder   : ");

 inOrder(akar);

 printf("\nTampilan PostOrder : ");

 postOrder(akar);

}

Contoh Gambar Program Tree C++ yang sedang di jalankan :

Sekian dari saya semoga bermanfaat ....