Sorting (Buble dan Quick Sort)

Politala 2A

SORTING (Bubble dan Quick Sort)

A. Bubble Sort

1. Definisi Bubble Sort

Bubble Sort ini merupakan proses pengurutan yang secara berangsur-angsur berpindah ke posisi yang tepat karena itulah dinamakan Bubble yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang terbesar ke yang terkecil (ascending) atau sebaliknya (descending). Secara sederhana, bisa didefenisikan algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data disebelahnya secara terus menerus sampai dalam satu iterasi tertentu tidak ada lagi perubahan. Untuk belajar algoritma Bubble Sort ini kita hanya perlu memahami cara yang digunakan untuk mengurutkan data, sederhananya algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Algoritma Bubble Sort merupakan proses pengurutan yang secara berangsur-angsur memindahkan data ke posisi yang tepat. Karena itulah, algoritma ini dinamakan “bubble” atau yang jika diterjemahkan ke dalam Bahasa Indonesia, artinya yaitu gelembung. Fungsi algoritma ini adalah untuk mengurutkan data dari yang terkecil ke yang terbesar (ascending) atau sebaliknya (descending). Metode pengurutan gelembung (Bubble Sort) ini terinspirasi oleh gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung sabun yang lebih ringan ketimbang berat jenis air, maka gelembung sabun akan selalu terapung ke atas permukaan. Prinsip inilah yang dipakai pada algoritma pengurutan gelembung.

Secara sederhana, bisa didefinisikan bahwa algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data di sebelahnya secara terus menerus sampai pada satu iterasi tertentu dimana tidak ada lagi perubahan yang signifikan. Sebelum kita masuk untuk membuat program, berikut ini adalah syarat dan langkah-langkah yang harus diperhatikan pada metode Bubble Sort :

a. Jumlah iterasi sama dengan banyaknya bilangan dikurang 1.

b. Di setiap iterasi, jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan.

c. Dalam algoritma Bubble Sort, meskipun deretan bilangan tersebut sudah terurut, proses sorting akan tetap dilakukan.

d. Tidak ada perbedaan cara yang berarti untuk teknik algoritma Bubble Sort Ascending dan Descending.

1. Algoritma Buble Sort

Alg.Buble Sort(Ascending)

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

{for(j=n-1;j>=i+1;j--)

{if data[j]<data[j-1]

{buble = data[j]

Data[j] = data [j-1]

Data[j-1] = buble }

}

}

2.  Contoh Program

a) Listing Program

 

 

b) Hasil Running

 

B.  Quick Sort

1.  Definisi Quick Sort

Quicksort adalah algoritma pengurutan cepat yang tidak hanya digunakan dalam dunia pendidikan, tetapi banyak diterapkan secara prkaktik. Rata-rata,  biasanya memiliki kompleksitas O (n log n), membuat quicksort sangat cocok untuk mengurutkan volume data yang besar. Ide dari algoritma ini cukup sederhana dan ketika kita menyadarinya, kita dapat menulis quicksort secepat bubblesort.

Strategi divide-and-conqueror digunakan di dalam quicksort. Di bawah ini akan dijelaskan langkah-langkahnya :

a. Pilih nilai pivot

Kita ambil nilai di tengah-tengah elemen sebagai sebagai nilai dari pivot, tetapi bisa nilai mana saja.

b. Partisi

Atur ulang semua elemen sedemikian rupa, lalu semua elemen yang lebih rendah daripada pivot dipindahkan ke sebelah kiri dari array/list dan semua elemen yang lebih besar dari pivot dipindahkan ke sebelah kanan dari array/list.  Nilai yang sama dengan pivot dapat diletakkan di mana saja dari array. Ingat, mungkin array/list akan dibagi dalam bagian yang tidak sama.

c. Urutkan semua bagian (kiri/kanan)

Aplikasikan algoritma quicksort secara rekursif pada bagian sebelah kiri dan kanan.

1) Keunggulan Quick sort:

Secara umum memiliki kompleksitas O(n log n).

a) Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.

b) Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti mergesort dan heapsort.

c) Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.

d) Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

2) Kekurangan Quick short

a) Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).

b) Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).

c) Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).

d) Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.

e) Pada bahasa pemrograman, quicksort ada dalam pustaka stdlib.h untuk bahasa C, dan class TList dan TStringList dalam Delphi (Object Pascal) maupun FreePascal.

2. Algoritma Quick Sort

Alg.Quick Sort(Data,left,right)

1) i=left, j=right

pivot= data[tengah] = data[left+right/2]

2) Ketentuan partisi

a. data[i] < pivot = i++

b.  data [j] > pivot = j—

i<=j = data [i] ß data[j]

i++;j—

3) Rekursif

Left < j à quicksort (data,left,j)

I < right à quicksort (data,i,right)

3) Contoh Program

a) Listing Program

 

b) Hasil Running

Penerapan Kasus sehari-hari pada Graf dan Pohon

Politala 2A

GRAF DAN POHON

A. Definisi Graf dan Pohon

Pohon (tree) adalah graf tak-berarah terhubung yang tidak memuat sirkuit sederhana. Menurut definisi di atas, suatu pohon merupakan graf yang terhubung,  tak  berarah,  dan  tidak  memuat  sirkuit,  ini merupakan tiga kriteria utama untuk pohon. Pohon adalah bentuk  khusus dari  suatu  graf  yang banyak  diterapkan untuk  berbagai  keperluan. Misalnya struktur  organisasi suatu perusahaan,  silsilah  suatu  keluarga,  skema sistem gugur suatu pertandingan, dan ikatan kimia suatu molekul adalah  jenis  graf  yang  tergolong  sebagai  pohon.  Pada pohon,  simpul-simpul  yang  berderajat  satu  dinamakan daun  (leave),  sedangkan  simpul  yang  derajatnya  lebih besar  daripada  satu dinamakan  simpul  cabang  (branchnode) atau simpul internal (internal node) dan kumpulan pohon-pohon  yang  terpisahkan  satu  sama  lain  disebut hutan (forest)  Dalam struktur data, pohon  memegang  peranan  yang cukup penting. Struktur ini biasanya digunakan terutama untuk  menyajikan  data  yang  mengandung  hubungan hierarkykal antara elemen-elemen mereka.Bentuk  pohon  khusus  yang  lebih  mudah  dikeloladalam  komputer  adalah  pohon  binary.  Bentuk  ini merupakan bentuk pohon yang umum. Sebuah pohon binar T  didefinisikan  terdiri  dari  sebuah himpunan hingga  elemen  yang  disebut simpul [2], sedemikian sehingga :

a.       T adalah hampa (disebut pohon null) atau

b.      T mengandung simpul R yang dipilih disebut akar (root) dari T, dan simpul sisanya membentuk 2 pohon binary T1 dan T2 yang saling lepas.

B. Sifat-sifat Pohon

Misalkan  G  =  (V, E)  adalah graf tak-berarah sederhana dan  jumlah  simpulnya  n.  Maka,  semua  pernyataan  dibawah ini adalah ekivalen :

a. G adalah pohon.

b. Setiap  pasang  simpul  di dalam  G terhubung  dengan lintasan tunggal.

c. G terhubung dan memiliki m = n – 1 buah sisi.

d. G tidak  mengandung  sirkuit  dan  memiliki  m  =  n  – 1 buah sisi.

e. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

f. G terhubung dan semua sisinya adalah jembatan.

C. Pohon Merentang (Spanning Tree)

Suatu  pohon  rentangan  atau spanning  tree  adalah  suatu subgraf dari graf G yang mengandung semua simpul dariG dan merupakan suatu pohon [3]. Pohon merentang darigraf  terhubung  adalah  upagraf  merentang  yang  berupa pohon. Artinya, setiap vertex terletak di pohon, tetapi tidak ada  siklus  (atau  loop)  terbentuk.  Di  sisi  lain,  setiap jembatan dari G harus milik T.Sebuah  pohon rentang  dari  graf  terhubung  G  juga dapat didefinisikan sebagai satu set maksimal tepi G yang berisi siklus tidak ada, atau sebagai seperangkat minimal tepi  yang menghubungkan  semua  titik.  Dalam  bidang-bidang tertentu teori grafik sering berguna untuk mencaripohon  rentang  minimum  dari  sebuah  graf  berbobot. Masalah  optimasi  lain  di  pohon  mencakup  juga  telah dipelajari, termasuk mencakup pohon maksimum, pohon minimum  yang  mencakup  setidaknya  simpul  k,  pohon rentang minimum dengan di tepi k paling per titik (Gelar-Dibatasi Spanning Tree) , pohon merentang dengan jumlah daun terbesar  (erat kaitannya dengan terkecil terhubung mendominasi set ), pohon merentang dengan daun paling sedikit (berkaitan erat dengan masalah jalan Hamilton ), dengan rentang diameter pohon minimal, dan dilatasi mini-mum spanning tree Perhatikan graf G  dibawah ini  dengan  beberapa  pohon perentang dari graf G tersebut yaitu T1, T2, dan T3.

1. Algoritma Kruskal

Algoritma Kruskal adalah algoritma pohon rentang minimum yang menemukan tepi dengan bobot sekecil mungkin yang menghubungkan dua pohon di hutan. Ini adalah algoritma serakah dalam teori grafik karena ia menemukan pohon spanning minimum untuk grafik tertimbang yang terhubung yang menambah kenaikan biaya busur pada setiap langkah. Ini berarti ia menemukan subset dari tepi yang membentuk pohon yang mencakup setiap titik , di mana total berat semua tepi di pohon diminimalkan. Jika grafik tidak terhubung, maka ia akan menemukan hutan spanning minimum (pohon spanning minimum untuk setiap komponen yang terhubung ).

Langkah Algoritma Kruskal : 

1)      Atur tepi berat : paling berat pertama dan terberat terakhir

2)      Pilih yang ringan tidak diperiksa tepi dari diagram

3)      Tambahkan tepi memilih ini ke pohon, jika hal itu tidak akan membuat siklus

4)      Menghentikan proses kapanpun n-1 tepi lebih ditambahkan ke pohon-pohon

a)      Listing Program

b)      Hasil Running Program

2. Algoritma Dijkstra

Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif. Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G. Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Langkah-langkah Algoritma Dijkstra :

1) Tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap.

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

3) Set semua node yang belum dilalui  dan set node awal sebagai “Node keberangkatan”

4) Dari node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru

5) Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah dilalui sebagai “Node dilewati”. Node yang dilewati tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

6) Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah e.

a) Listing Program

b) Hasil Running Program

Referensi 

https://www.researchgate.net/publication/322423546_APLIKASI_GRAF_POHON_PADA_ALGORITMA_HUFFMAN diakses pada tanggal 29 mei 2019 pukul 14.29 wita

https://www.slideshare.net/zaenalmustofa54943/makalah-algoritma-kruskal

diakses pada tanggal 29 mei 2019 pukul 13.56 wita

https://mti.binus.ac.id/2017/11/28/algoritma-dijkstra/

diakses pada tanggal 29 mei 2019 pukul 13.58 wita

NORMALISASI

Politala 2A

NORMALISASI

A. Pengertian Normalisasi

Normalisasi adalah proses penyusunan table-tabel yang tidak redudan (dobel), yang dapat menyebabkan anomali pada saat terjadi operasi manipulasi data seperti tambah, hapus, dan ubah. Masalah-masalah yang timbul dalam pembuatan tabel yang disebut dengan anomali. Anomali adalah proses pada basis data yang mempunyai efek samping yang tidak diharapkan. Contoh : ketidakkonsistenan data, suatu data hilang pada saat dihapus, dll.

Ada dua fungsi normalisasi, yaitu :

1. Dapat digunakan sebagai metodologi dalam menciptakan desain database

2. Dapat digunakan sebagai verifikasi terhadap hasil desain database yang telahdibuat, baik menggunakan E-R Model atau menggunakan model relasi, seperti yang anda buat diatas atau dari model yang lain

B. Tujuan Normalisasi

Tujuan Normalisasi dapat dibagi menjadi 3, yaitu :

1. Normaliasi diperlukan agar kerelasian dalam basis data menjadi mudah dimengerti, mudah dipelihara, mudah memprosesnya, dan mudah untuk dikembangkan sesuai dengan kebutuhan baru.

2. Normalisasi mengharuskan relasi pada suatu basis data dalam bentuk normal.

3. Bentuk normal sendiri merupakan seperangkat aturan yang dikenakan dan harus dipenuhi oleh relasi basis data pada setiap level normalisasi.

C. Jenis-jenis Anomali

Ada 3 jenis Anomali :

1. Anomali peremajaan

Anomali ini terjadi bila ada perubahan pada sejumlah data yang mubazir, tetapi tidak seluruhnya diubah

2. Anomali Penyisipan

Anomali ini terjadi pada saat penambahan data ternyata ada elemen yang kosong dan elemen tsb justru menjadi key.

3.  Anomali Penghapusan

Anomali ini terjadi apabila dalam satu baris/ tuple ada data yang akan dihapus sehingga akibatnya terdapat data lain yang hilang. Contoh pada table kursus data Jumlah Siswa 10 akan dihapus dengan data kursus perancis karena sudah tidak ikut kursus lagi sehingga akibatnya data kursus bahasa perancis dan biaya 80000 akan ikut terhapus.

D. Bentuk Normal 1nf

Bentuk Normal Pertama (1NF) Bentuk normal pertama dikenakan pada entity yang belum normal (Unnormalized Form). Bentuk tidak normal merupakan kumpulan data yang akan di rekam, tidak ada keharusan mengikuti suatu format tertentu, dapat saja tersebut tidak lengkap atau terduplikasi. Data dikumpulkan apa adanya sesuai dengan kedatangannya.

Tahapan yang harus dilakukan pada 1NF adalah:

a.       Hilangkan pengulangan kelompok data dalam suatu tabel.

b.      Buatkan tabel tersendiri untuk setiap set data terkait.

c.       Identifikasikan setiap set data yang akan dijadikan sebagai primary key.

Pada tahap ini, jangan menggunakan beberapa field dalam satu tabel untuk menyimpan data yang sama. Misalnya, untuk menulusuri item persediaan yang berasal dari dua sumber penjual, bisa jadi data item persediaan tersebut tersimpan di kolom Kode Penjual 1 dan Kode Penjual 2. Jika misalnya ada penambahan penjual ketiga, maka tidak dianjurkan untuk menambahkan field Kode Penjual 3. Sebagai gantinya, letakkan semua informasi penjual dalam satu tabel terpisah yang disebut table Penjual, kemudian hubungkan table Penjual dengan table Persediaan berdasarkan Kode Penjual (sebagai primary key-nya).

E. Bentuk Normal 2nf

Tahapan yang harus dilakukan pada 2NF adalah:

a.       Buat tabel terpisah untuk sekumpulan nilai yang berlaku pada beberapa data.

b.      Hubungkan tabel tersebut melalui foreign key.

Data yang saling berkaitan harus tergantung pada primary key. Sebagai contoh adalah Alamat Pelanggan dalam sebuah Sistem Akuntansi. Alamat Pelanggan tidak hanya dibutuhkan oleh tabel Pelanggan itu sendiri, tetapi juga oleh tabel Pesanan, Pengiriman, Faktur, Piutang, dan Pembayaran. Agar tabel Pesanan, Pengiriman, Faktur, Piutang, dan Pembayaran dapat menggunakan data Alamat Pelanggan di table Pelanggan, maka di masing-masing table tersebut perlu ditambahkan field Kode Pelanggan sebagai foreign key-nya. Perhatikan data Class# dan data Student# pada table hasil 1NF tersebut. Data Class# secara fungsi tidak tergantung pada Student# (sebagai primary key), dengan demikian hubungan data antara dua field tersebut belum belum memenuhi bentuk 2NF. Untuk mengubahnya menjadi 2NF, hilangkan redudansi data dan pisahkan menjadi beberapa tabel 

F. Bentuk Normal 3nf 

Tahapan yang harus dilakukan pada 3NF adalah menghilangkan data pada field yang tidak tergantung pada primary key. Sebagai contoh pada Sistem Akuntansi di 2NF di atas. Jika pada tabel Pesanan, Pengiriman, Faktur, Piutang, dan Pembayaran terdapat data Nama, Alamat, Kota, Kode Pos, Nomor Telepon, dan Nomor Fax Pelanggan; padahal data Nama, Alamat, Kota, Kode Pos, Nomor Telepon, dan Nomor Fax Pelanggan sudah ada di table Pelanggan; maka data-data tersebut harus dihilangkan dari table Pesanan, Pengiriman, Faktur, Piutang, dan Pembayaran. Perhatikan tabel Students hasil 2NF. Sebenarnya data nomor ruangan pada field Adv-Room secara fungsional tergantung pada tabel Advisor karena suatu saat bisa terjadi perubahan pada nomor ruangan tersebut. Untuk mengantisipasinya, data Adv-Room dipindahkan ke tabel Advisor 

G. Bentuk Normal Boyce-Codd (BCNF)

Meskipun sudah ada Bentuk Normal Keempat (4NF) yang juga disebut Boyce Codd Normal Form (BCNF), Bentuk Normal Kelima (5NF), dan Bentuk Normal Kenam (6NF); tapi bentuk-bentuk normal ini jarang digunakan sebagai bahan pertimbangan dalam praktek 5 mendesain suatu database. Kecuali jika database yang didesain sangatlah kompleks.


Link video tentang materi terkait ada dibawah ini, silahkan kunjungi :
https://www.youtube.com/watch?v=L4nfjB4f_Is