Algoritma K-Means Clustering

 K-Means adalah teknik yang cukup sederhana dan cepat dalam pekerjaan pengelompokkan data (clustering). Prinsip utama dari teknik ini adalah menyusun k buah prototipe/pusat massa (centroid)/rata-rata (mean) dari sekumpulan data berdimensi n. Teknik ini mensyaratkan nilai k sudah diketahui sebelumnya (a priori). Algoritma k-means dimulai dengan pembentukan prototipe cluster di awal kemudian secara iteratif prototipe cluster ini diperbaiki hingga konvergen (tidak terjadi perubahan yang signifikan pada prototipe cluster). Perubahan ini diukur menggunakan fungsi objektif J yang umumnya didefinisikan sebagai jumlah atau rata-rata jarak tiap item data dengan pusat massa kelompoknya. Secara lebih detil algoritma k-means adalah seperti berikut :

1. inisialisasi nilai J (misal MAXINT)
2. Tentukan prototipe cluster awal (bisa secara acak ataupun dipilih salah satu secara acak dari koleksi data)
3. Masukkan tiap satuan data ke dalam kelompok yang jarak dengan pusat massa-nya paling dekat
4. ubah nilai pusat massa tiap cluster sebagai rata-rata (mean) dari seluruh anggota kelompok tersebut
5. Hitung fungsi objektif J
6. jika nilai J sama dengan sebelumnya, berhenti atau ulangi langkah 3

Sumber: Buku Konsep Data Mining

Data Mining: Clustering

Clustering adalah proses mengelompokkan objek berdasarkan informasi yang diperoleh dari data yang menjelaskan hubungan antar objek dengan prinsip untuk memaksimalkan kesamaan antar anggota satu kelas dan meminimumkan kesamaan antar kelas/cluster. Tujuannya menemukan cluster yang berkualitas dalam waktu yang layak. Clustering dalam data mining berguna untuk menemukan pola distribusi di dalam sebuah data set yang berguna untuk proses analisa data. Kesamaan objek biasanya diperoleh dari kedekatan nilai-nilai atribut yang menjelaskan objek-objek data, sedangkan objek-objek data biasanya direpresentasikan sebagai sebuah titik dalam ruang multidimensi.

Dengan menggunakan clustering, dapat diidentifikasi daerah yang padat, pola-pola distribusi secara keseluruhan dan keterkaitan yang menarik antara atribut-atribut data. Dalam data mining usaha difokuskan pada metode-metode penemuan untuk cluster pada basisdata berukuran besar secara efektif dan efisien. Banyaknya pendekatan clustering menyulitkan dalam menentukan ukuran kualitas yang universal. Namun, beberapa hal yang perlu diperhatikan adalah input parameter yang tidak menyulitkan user, cluster hasil yang dapat dianalisa, dan skalabilitas terhadap penambahan ukuran dimensi dan record dataset. Secara garis besar ada beberapa kategori algoritma clustering yang dikenal yaitu:

a. Metode Partisi, dimana pemakai harus menentukan jumlah k partisi yang diinginkan lalu setiap data dites untuk dimasukkan pada salah satu partisi sehingga tidak ada data yang overlap dan satu data hanya memiliki satu cluster. Contohnya: algoritma K-Means.

b. Metode Hierarki, yang menghasilkan cluster yang bersarang artinya suatu data dapat memiliki cluster lebih dari satu. Metode ini terbagi menjadi dua yaitu buttom-up yang menggabungkan cluster kecil menjadi cluster lebih besar dan top-down yang memecah cluster besar menjadi cluster yang lebih kecil. Kelemahan metode ini adalah bila salah satu penggabungan/pemecahan dilakukan pada tempat yang salah, tidak akan didapatkan cluster yang optimal. Contohnya: Agglomerative (FINDIT, PROCLUS), Divisive Hierarchical Clustering (CLIQUE, MAFIA, ENCLUE).

Sumber: Buku Konsep Data Mining

Algoritma CT-Pro

Algoritma CT-PRO merupakan salah satu algoritma pengembangan dari FP-Growth. Perbedaannya terdapat pada langkah kedua dimana FP-Growth membuat FP-Tree sedangkan CT-PRO membuat Compressed FP-Tree (CFP- Tree )[8]. Pada tahap mining algoritma CT-PRO juga menggunakan pendekatan bottom-up dimana item pada item tabel dan CFP-Tree dilakukan scan dari jumlah terkecil hingga terbesar. Algoritma CT-PRO memiliki tiga tahap yaitu:

1. Menemukan item-item yang frequent

2. Membuat struktur data CFP-Tree

3. Melakukan mining frequent patterns
Langkah-langkah kerja algoritma CT-Pro:

1.      Mencari Frequent item, pada tahap ini terjadi proses-proses sebagai berikut:

-          Dari dataset yang ada, dilakukan seleksi berdasarkan minimum support yang ditentukan sehingga menghasilkan frequent item.

-          Dari frequent item yang telah terbentuk, dihitung frekuensi kemunculan setiap item sehingga menghasilkan Global Item tabel.

2.      Membangun CFP-Tree, pada tahap ini terjadi proses-proses sebagai berikut:

-          Frequent item yang telah didapatkan, diurutkan berdasarkan Global Item tabel yang ada secara menurun (diurutkan mulai dari item berfrekuensi terbesar hingga terkecil).

-          Dengan frequent item yang telah terurut ini dibentuk Global CFP-Tree, aturan pembentukan Global CFP-Tree sebagai berikut:

a.       CFP-Tree terdiri dari tree yang memiliki root yang mewakili index dari item dengan tingkat kemunculan tertinggi dan kumpulan subtree sebagai anak dari root.

b.      Jika I = {i1,i2, …, ik} adalah kumpulan dari frequent item dalam transaksi, item dalam transaksi akan dimasukkan  ke dalam CFP-Tree dimulai dari root subtree yang merupakan i1 dalam

b.item tabel.

c.       Root dari CFP-Tree merupakan level-0 dari tree.

d.      Setiap node dalam CFP-Tree memiliki empat field utama yakni item-id, parent-id, count yang merupakan jumlah item pada node tersebut, dan level yang menunjukkan struktur data tree pada node tersebut dimulai dari item yang terdapat pada item tabel dengan level yang terdapat pada CFP-Tree .

3.      Mining, pada tahap ini terjadi proses-proses sebagai berikut:

-          Pada tahap mining ini, algoritma CT-Pro bekerja dengan melakukan bottom -up mining sehingga Global Item tabel diurutkan mulai dari item berfrekuensi terkecil hingga terbesar.

-          Untuk setiap item yang terdaftar pada Global Item tabel yang telah diurutkan, dilakukan pencarian  node yang berkaitan dengan item tersebut pada Global CFP-Tree. Dari semua node yang ditemukan untuk setiap item inilah yang disebut dengan Local Frequent item dan digunakan untuk membuat Local Item Tabel.

-          Pada pembuatan local item tabel ini juga dilakukan berdasarkan jumlah minimum support yang telah ditentukan.

-          Setelah itu, dibuat Local CFP-Tree berdasarkan Local Item Tabel yang terbentuk. Aturan pembentukan Local CFP-Tree sama dengan pembentukan Global CFP-Tree, yang membedakan adalah pada Global CFP-Tree yang digunakan dalam pembentukan tree-nya adalah  Global Item tabel yang terbentuk dari Global Item tabel data sedangkan pada Local CFP-Tree yang digunakan dalam pembentukan tree-nya adalah Local Item tabel yang terbentuk dari Local Frequent item.

-          Dari Local CFP-Tree dibentuk frequent pattern sesuai dengan item yang dimining.

Dari frequent pattern dihitung masing-masing item yang memenuhi dihitung confidencenya. Apabila memenuhi minimum confidence maka masing-masing item yang bersangkutan dijadikan sebagai knowledge.

Sumber: Buku TA-Parama Fadli Kurnia (IT Telkom/113090065)

Algoritma FP-Growth

Algoritma FP-Growth adalah cara alternatif untuk menemukan itemsets sering tanpa menggunakan generasi calon, sehingga meningkatkan kinerja. Untuk begitu banyak menggunakan membagi-dan-menaklukkan strategi  . Inti dari metode ini adalah penggunaan struktur data khusus bernama sering-pola pohon (FP-pohon), yang mempertahankan informasi asosiasi itemset.

Dengan kata sederhana, algoritma ini bekerja sebagai berikut: pertama kompres database masukan menciptakan sebuah instance FP-Tree untuk mewakili item sering. Setelah langkah pertama membagi database dikompresi menjadi satu set database kondisional, masing-masing terkait dengan satu pola yang sering. Akhirnya, masing-masing database tersebut ditambang secara terpisah. Menggunakan strategi ini, FP-Growth mengurangi biaya pencarian mencari pola singkat rekursif dan kemudian concatenating kemudian dalam pola yang sering panjang, menawarkan selektivitas yang baik.

Dalam database besar, itu tidak mungkin untuk memegang FP-pohon di memori utama. Sebuah strategi untuk mengatasi masalah ini adalah untuk pertama partisi database menjadi satu set database yang lebih kecil (disebut database diproyeksikan), dan kemudian membangun sebuah FP-pohon dari masing-masing database yang lebih kecil.

Sumber: Buku Konsep Data Mining

Algoritma Aplriori

Persoalan association rule mining terdiri dari dua sub persoalan :
a. Menemukan semua kombinasi dari item, disebut dengan frequent itemsets, yang memiliki support     yang lebih besar daripada minimum support.
b. Gunakan frequent itemsets untuk men-generate aturan yang dikehendaki.Semisal,  ABCD dan AB adalah frequent, maka didapatkan aturan AB -> CD jika rasio dari upport(ABCD) terhadap support(AB) sedikitnya sama dengan minimum confidence. Aturan ini memiliki minimum support karena ABCD adalah frequent.
          Algoritma Apriori yang bertujuan untuk menemukan frequent itemsets dijalankan pada sekumpulan data. Pada iterasi ke -k, akan ditemukan semua itemsets yang memiliki k items, disebut dengan k -itemsets. Tiap iterasi berisi dua tahap. Misal Oracle Data Mining Fk merepresentasikan himpunan dari frequent k -itemsets, dan Ck adalah himpunan candidate k-itemsets (yang potensial untuk menjadi frequent itemsets). Tahap pertama adalah men-generate kandidat, dimana himpunan dari semua frequent (k- 1) itemsets, Fk-1, ditemukan dalam iterasi ke-(k-1), digunakan untuk men-generate candidate itemsets Ck. Prosedur generate candidate memastikan bahwa Ck adalah superset dari himpunan semua frequent k-itemsets. Struktur data hash-tree digunakan untuk menyimpan Ck. Kemudian data di-scan dalam tahap penghitungan support. Untuk setiap transaksi, candidates dalam Ck diisikan ke dalam transaksi, ditentukan dengan menggunakan struktur data hash-tree hashtree dan nilai penghitungan support dinaikkan. Pada akhir dari tahap kedua, nilai Ck diuji untuk menentukan yang mana dari candidates yang merupakan frequent. Kondisi penghitung (terminate condition) dari algoritma ini dicapai pada saat Fk atau Ck+1 kosong.

Sumber: Buku Konsep Data Mining

Association Rule Mining

Mining association rules atau pencarian aturan-aturan hubungan antar item dari suatu basis data transaksi atau basis data relasional, telah menjadi perhatian utama dalam masyarakat basis data. Tugas utamanya adalah untuk menemukan suatu himpunan hubungan antar item dalam bentuk A1A...AAm => B1A...ABn dimana A, ( for i E {1,...,m}) dan B; ( for j C {1,...,n} ) adalah himpunan atribut nilai, dari sekumpulan data yang relevan dalam suatu basis data. Sebagai contoh, dari suatu himpunan data transaksi, seseorang mungkin menemukan suatu hubungan berikut, yaitu jika seorang pelanggan membeli selai, ia biasanya juga membeli roti dalam satu transaksi yang sama. Oleh karena proses untuk menemukan hubungan antar item ini mungkin memerlukan pembacaan data transaksi secara berulang-ulang dalam sejumlah besar data-data transaksi untuk menemukan pola-pola hubungan yang berbeda-beda, maka waktu dan biaya komputasi tentunya juga akan sangat besar, sehingga untuk menemukan hubungan tersebut diperlukan suatu algoritma yang efisien dan metodemetode tertentu.

         Analisis asosiasi atau association rule mining adalah teknik data mining untuk menemukan aturan assosiatif antara suatu kombinasi item. Contoh dari aturan assosiatif dari analisa pembelian di suatu pasar swalayan adalah dapat diketahuinya berapa besar kemungkinan seorang pelanggan membeli roti bersamaan dengan susu. Dengan pengetahuan tersebut pemilik pasar swalayan dapat mengatur penempatan barangnya atau merancang kampanye pemasaran dengan memakai kupon diskon untuk kombinasi barang tertentu. Karena analisis asosiasi menjadi terkenal karena aplikasinya untuk menganalisa isi keranjang belanja di pasar swalayan, analisis asosiasi juga sering disebut dengan istilah market basket analysis 

          Fungsi Association Rules seringkali disebut dengan "market basket analysis", yang digunakan untuk menemukan relasi atau korelasi diantara himpunan item. Market Basket Analysis adalah Analisis dari kebiasaan membeli customer dengan mencari asosiasi dan korelasi antara item-item berbeda yang diletakkan customer dalam keranjang belanjaannya. Fungsi ini paling banyak digunakan untuk menganalisa data dalam rangka keperluan strategi pemasaran, desain katalog, dan proses pembuatan keputusan bisnis. Tipe association rule bisa dinyatakan sebagai misal : "70% dari orangorang yang membeli mie, juice dan saus akan membeli juga roti tawar". Aturan asosiasi mengcapture item atau kejadian dalam data berukuran besar yang berisi data transaksi. Dengan kemajuan teknologi, data penjualan dapat disimpan dalam jumlah besar yang disebut dengan "basket data." Aturan asosiasi yang didefinisikan pada basket data, digunakan untuk keperluan promosi, desain katalog, segmentasi customer dan target pemasaran. Secara tradisional, aturan asosiasi digunakan untuk menemukan trend bisnis dengan menganalisa transaksi customer.
          Berdasarkan definisi di [6] maka pencarian pola kaidah asosiasi mengunakan dua buah parameter nilai yaitu dukungan (support) dan keterpercayaan (confidence) yang memiliki nilai antara 0% - 100 %. Berikut sedikit penjelasan mengenai dukungan dan keterpercayaan.
          Sebagai contoh terdapat relasi I berisi sejumlah kumpulan item yang kemudian dikatakan sebagai itemset, dimana masing–masing itemset terdiri dari sekumpulan atribute bertipe boolean I1, I2, …, In. Dan basis data transaksi D yang berisi transaksi T, adalah himpunan dari I atau T Í I. Dimana transaksi T pada basis data transaksi D memiliki sebuah atribut yang unik yang dinotasikan dengan TID. Dalam konteks ini, A dan B merupakan itemset dari transaksi T, jika dan hanya jika A Í T dan B Í T. Sehingga jumlah A dinotasikan ó (A) merupakan jumlah Support (support count) itemset A pada basis data transaksi D. Kaidah asosiasi A› B, jika dan hanya jika A I, B I dan A B 0. Sehingga A› B memiliki Support s pada transaksi T, dimana S merupakan persentase itemset A È B pada basis data transaksi D. Dan A› B memiliki Confidence C pada transaksi T, dimana C merupakan persentase jumlah itemset A yang terdapat pada relasi I, yang diikuti itemset B. Dukungan kaidah asosiasi A› B dinyatakan dengan :
           Support (A› B) = P(AÈB) (xx)
           Sedangkan keterpercayaan kaidah asosiasi A› B
           dinyatakan dengan :
           Confidence (A› B) = P(A|B) (xx)
           dimana :A dan B adalah frequent itemset memiliki jumlah dukungan lebih besar
sama dengan batas ambang dukungan minimum).

Sumber: Buku Konsep Data Mining

Model Data Mining

Macam - Macam Model Data Mining

A. Metode Prediksi
Dengan menggunakan beberapa variabel untuk memprediksi nilai yang belum diketahui (unknown) atau nilai selanjutnya (future) atau variabel lain.

Contoh :

1. Classification

• Pada persoalan klasifikasi, kita memiliki sejumlah kasus (sampel data) dan ingin mempresiksi beberapa class yang ada pada sampel data tersebut.
• Tiap isntan data berisi banyak atribut, dimana masing-masing atribut memiliki satu dari beberapa kemungkinan nilai.
• Hanya satu atribut diantara banyak aribut tersebut yang disebut atribut target, sedangkan atribut yang lain disebut sebagai atribut prediktor.

2. Regression
3. Deviation Detection

B. Metode Deskripsi
Menemukan pola pendeskripsian data yang dapat diinterpretasikan oleh manusia.

Contoh :

1. Clustering

• Teknik yang berguna untuk mengeksplorasi data
• digunakan pada saat banyak kasus dan tidak memiliki pengelompokan secara alami. (Dalam hal ini algoritma data mining dapat digunakan untuk mencari pengelompokan yang ada pada peta).
• Clustering model berbeda dari model prediktif dikarenakan pada clustering tidak perlu ada atribut target.
• Clustering juga dapat diorganisasi ke dalam sturktur hirarkikal akan mendefinisikan taksonomi dari data.

2. Association Rule Discovery

• Sering disebut "Market Basket Analysis" yang digunakan untk menemukan relasi atau korelasi diantara himpunan item-item.
• Fungsi ini paling banyak digunakan untuk menganalisa data dalam rangka keperluan strategi pemasaran, desain katalog, dan proses pembuatan keputusan bisnis.
• Bisa dinyatakan sebagai, misal : "70 % dari orang-orang yang memebeli mie, juice dan saus akan membeli juga roti tawar."

3. Sequential Pattern Discovery

Sumber: Buku Konsep Data Mining

Data Mining

Pengertian Data Mining menurut para ahli :
Definisi data mining berdasarkan [JK06] adalah proses mengekstraksi pola-pola yang menarik (tidak remeh-temeh, implisit, belum diketahui sebelumnya, dan berpotensi untuk bermanfaat) dari data yang berukuran besar. Ada beberapa istilah yang mempunyai kemiripan dengan data mining, yaitu ekstraksi pengetahuan, analisis pola, pengerukan data, dan lain-lain. Ada yang berpendapat data mining merupakan sinonim dari istilah knowledge discovery in database (KDD).

Data mining adalah serangkaian proses untuk menggali nilai tambah berupa informasi  yang selama ini tidak diketahui secara manual dari suatu basisdata.  Informasi yang dihasilkan diperoleh dengan cara mengekstraksi dan mengenali pola yang penting atau menarik dari data yang terdapat dalam basisdata.

Manfaat Data Mining :
Classification, Menentukan karakteristik dari kelompok tertentu.
Clustering, Identifikasi kelompok/groups dari item-tem yangberbagi satu karakteristik. Clustering berbeda dengan classification,dimana tidak ada penentuan terlebih dulu karakteristik
Association, Identifikasi relationships antara event-event yangterjadi pada suatu saat.
Sequencing, Identifies relationships yang ada sepanjang satuperiode waktu.
Forecasting, Estimasi nilai2 masadatang berdasarkan patternsdalam sekumpulan besar data.
Regression, Memetakan sebuah data item pada satu variableprediksi.
Time Series analysis, menguji sebuah nilai atas variasinya sepanjang waktu.

Tujuan Data Mining :
tujuan dari data mining adalah menemukan hubungan-hubungan ataupola-pola yang mungkin memberikan indikasi yang bermanfaat. Kehadiran data mining dilatar belakangi oleh berlimpahnya data(overload data) yang dialami oleh berbagai institusi, perusahaanatau organisasi. Berlimpahnya data ini merupakan akumulasi datatransaksi yang terekam bertahun-tahun. Data–data tersebut merupakan  data  transaksi yang umumnya diproses menggunakan aplikasi komputer yang biasa disebut On Line Transaction Processing).

Data mining juga dilatarbelakangi oleh atau adanya ledakan informasi (explotion information) dari berbagai media terutama internet. Delapan puluh persen informasi yang disajikan media internet dalam bentuk tak terstruktur (unstructured information). Media internet menyajikan informasi dalam berbagai format file, bahasa, dan bentuk penyajian seperti teks, gambar, suara ataupun  video. Kendala lainyang melatarbelakangi adalah tidak dilengkapinya informasi dengan metadata yang terstandarisasi atau bahkan tidak menyertakannya sama sekali.

Pertumbuhan yang pesat dari akumulasi data/informasi itu telah menciptakan kondisi dimana suatu institusi memiliki bergunung-gunung data tetapi  miskin informasi yang bermaanfaat(“rich of data but poor of information”). Tidak jarang “gunung” data itu dibiarkan begitu saja seakan-akan menjadi  “kuburan data” (datatombs). Pertanyaannya sekarang, apakah gunung data tersebut akan dibiarkan, tidak berguna lalu dibuang, ataukah dapat ditambang untuk menemukan “emas” yaitu informasi yang lebih bermanfaat. Jawabnya ya, data mining hadir untuk menjawab tantangan tersebut.

Sumber: Buku Konsep Data Mining

Mesin Karakter

Suatu mesin karakter adalah mesin yang dapat memproses pita karakter dan memiliki elemen-elemen sebagai berikut:

1.      PITA KARAKTER yang merupakan kumpulan karakter yang diakhiri tanda titik atau karakter NULL

2.      POINTER yang merupakan petunjuk posisi karakter pada pita

3.      Jendela CURRENT CHARACTER(CC) yang akan menampilkan karakter yang sedang ditunjuk oleh POINTER

4.      Tombol START yang menempatkan POINTER mesin ke awal pita

5.      Tombol ADVANCE yang akan memajukan pointer ke karakter selanjutnya pada pita karakter

6.      Lampu EOP(End Of  Pita) yang menunjukan apakah POINTER ada di akhir pita atau tidak. Lampu EOP akan menyala jika POINTER ada di akhir pita dan mengembalikan nilai True,jika sebaliknya akan mengembalikan nilai False.

 

Sumber: Buku Algoritma dan Pemrograman

Algoritma Quick Sort

Quick Sort adalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma algoritma divide and conquer.

Algoritma ini terdiri dari 4 langkah utama:

1. Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.
2. Ambil sebuah elemen yang akan digunakansebagai pivot point (poin poros).  (Biasanya elemen yang paling kiri.)
3. Bagi struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar daripada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.
4. Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.

Sumber: Buku Algoritma dan Pemrograman

Algoritma Merge Sort

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut,

1. Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
2. Untuk membentuk sebuah list terurut dari duabuah list terurut membutuhkan langkah yangl ebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh:hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudahterurut.

Algoritma Merge Sort sederhananya, dapat ditulis berikut:

1. Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
2. Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
3. Gabung 2 sublist kembali menjadi satu list terurut.

Sumber: Buku Algoritma dan Pemrograman

Algoritma Insertion Sort

Cara kerja insertion sort sebagaimana namanya.Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan.  Dariproses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian yang belum di-sorting.

Algoritma Insertion Sort dapat dirangkum sebagai berikut:

1. Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
2. Bandingkan nilainya dengan elemen sebelumnya.
3. Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1).
4. Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.
5. Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
6. Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).

Sumber: Buku Algoritma dan Pemrograman

Algoritma Selection Sort

Algoritma sorting sederhana yang lain adalahSelection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksianelemen struktur data. Untuk sorting ascending(menaik), elemen yang paling kecil di antara elemenelemenyang belum urut, disimpan indeksnya,kemudian dilakukan pertukaran nilai elemen denganindeks yang disimpan tersebut dengan elemen yangpaling depan yang belum urut. Sebaliknya, untuksorting descending (menurun), elemen yang paling. besar yang disimpan indeksnya kemudian ditukar.

Algoritma selection sort dapat dirangkum sebagaiberikut:

1. Temukan nilai yang paling minimum (atau sesuaikeinginan) di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum.
2. Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data yang belum diurutkan.
3. Ulangi langkah di atas untuk bagian struktur datayang tersisa.

Sumber : Buku Algoritma dan Pemrograman

Algoritma Bubble Sort

Bubble Sort merupakan cara pengurutan yangsederhana. Konsep dari ide dasarnya adalah seperti“gelembung air” untuk elemen struktur data yangsemestinya berada pada posisi awal. Cara kerjanyaadalah 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). Algoritma sortingini disebut juga dengan comparison sort dikarenakanhanya mengandalkan perbandingan nilai elemen untukmengoperasikan elemennya.

Algoritma bubble sort dapat diringkas sebagaiberikut, jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:

1. Lakukan traversal untuk membandingkan dua elemen berdekatan. Traversal ini dilakukan dari belakang.
2. Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses traversal berikutnya sampai bertemu dengan bagian struktur data yang telah diurutkan.
3. Ulangi langkah di atas untuk struktur data yang tersisa.

Sumber : Buku Algoritma dan Pemrograman

Algoritma Sorting

Pengertian Sorting sort

Sorting Sort adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu.

Pada umumnya terdapat 2 cara pengurutan data yaitu

– Ascending : Pengurutan dilakukan mulai dari nilai terkecil menuju nilai terbesar

– Descending: Pengurutan dilakukan mulai dari nilai terbesar menuju nilai terkecil

Ada beberapa macem metoda pengurutan data diantaranya :

 

    Bubble Sort

    Selection Sort

    Insertion Sort

    Merge Sort

    Quick Sort

 

Sumber: Buku Algoritma dan Pemrograman

Binary Search

Konsep
(a)    Merupakan metode pencarian pada data terurut yang paling efisien.
(b)   Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
(c)    Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. data yang disimpan didalam larik harus sudah terurut.
Algoritma
Algoritma pencarian biner dapat dituliskan sebagai berikut:
(a)    L ← 0
(b)   R ← N – 1
(c)    Ketemu ← false
(d)   Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8
(e)    m ← (L + R) / 283
(f)    jika (Data[m]) maka ketemu ← true
(g)   jika (x < Data[m]) maka R ← m – 1
(h)   jika (x > Data[m]) maka L ← m + 1
(i)     jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak maka data tidak ditemukan.

Sumber : Buku Algoritm dan Pemrograman

Algoritma Sequential Search

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

Sumber: Buku Algoritma dan Pemrograman