1231039-Algoritma: February 2013

Sorting

Algoritma sorting

Dalam Ilmu Komputer, Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical. Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini:

Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.
Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan.

Sejak permulaan komputasi, masalah pengurutan ini telah menarik penelitian yang serius, mungkin dikarenakan kerumitan dari penyelesaian secara efisien disamping mudah, dan dengan statemen yang kita mengerti. Sebagai contoh, bubble sort pertama sekali ditemukan pada tahun 1956. Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritma sorting baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006). Algoritma sorting sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritma untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritma inti

Quick sort

Quicksort merupakan Algoritma Sorting yang dikembangkan oleh Tony Hoare yang, secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan O(n²), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).
Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritma sorting yang stabil.

^{Merge sort / Urut gabung}

^{Urut gabung atau sering juga disebut dalam istilah Inggrisnya merge sort merupakan algoritma pengurutan dalam ilmu komputer
yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian
data yang tidak memungkinkan untuk ditampung dalam memori komputer
karena jumlahnya yang terlalu besar yg dikenal dengan cara conquer and divide. Algoritma ini ditemukan oleh John
von Neumann pada tahun 1945.}

Bubble sort

bubble sort adalah sorting yang dilakukan dengan cara mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar, jika pengurutan ascending.

Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar, jika pengurutan descending
Untuk mengurutkan bilangan diperlukan variabel array yang digunakan untuk menampung semua bilangan yang akan diurutkan.
Proses pengurutan dilakukan dengan membandingkan semua elemen array satu persatu.

Contoh :
20 12 35 11 17 9 58 23
Dalam metode bubble sort, pengurutan demulai dengan membandingkan elemen pertama untuk mendapatkan angka terbesar. Lalu angka tersebut ditempatkan pada elemen terakhir.
Kedua :
5 6 3 8
5 6 3 8
5 3 6 8
5 3 6 8

Pada akhir proses kedua ini, bilangan terbesar kedua menempatkan tempat yang sesuai.

Ketiga :
5 3 6 8
3 5 6 8
3 5 6 8
3 5 6 8

Bila proses ini dilanjutkan, tidak ada pertukaran tempat lagi bagi bilangan – bilangan tersebut, sebab bilangan tersebut telah selesai disusun.

Seletion sort

Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan pada index terkecil , pada putaran kedua akan dicari data kedua terkecil dan akan ditempatkan pada index kedua terkecil.
Selama proses, perbandingan dan pengubahanhanya dilakukan pada index pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Contoh:

Diberikan data awal
22 10 15 3 8 2

Proses

22 10 15 3 8 2

2 10 15 3 8 22
2 3 15 10 8 22

2 3 8 10 15 22

Hasil : 2 3 8 10 15 22

Insertion Sort

Mirip dengan cara orang mengurutkan kartu,selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengandata terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan ( diinsert) diposisi yang seharusnya.Pada penyisipan elemen, maka elemen-elemenlain akan bergeser ke belakang

Contoh :

Diberikan data awal
22 10 15 3 8 2

Proses
22 10 15 3 8 2
10 22 15 3 8 2
10 15 22 3 8 2
10 15 3 22 8 2
10 3 15 22 8 2                       Hasil : 2 3 8 10 15 22
3 10 15 22 8 2
3 10 15 8 22 2
3 10 8 15 22 2
3 8 10 15 22 2
3 8 10 15 2 22
3 8 10 2 15 22
3 8 2 10 15 22
3 2 8 10 15 22
2 3 8 10 15 22

source : wikipedia
             http://www.scribd.com/doc/32772607/Sorting
             http://noviapermata23.blogspot.com/2012/03/apa-itu-bubble-sort.html

Array / Matrix

Array adalah suatu variabel yang terdiri dari sekumpulan data dimana data-data tersebut mempunyai tipe data yang sama. Setiap data disimpan dalam alamat memori yang berbeda-beda dan disebut dengan elemen array. Setiap elemen mempunyai nilai indek sesuai dengan urutannya. Melalui indek inilah kita dapat mengakses data-data tersebut. Indek dari elemen array ini, baik dalam bahasa C++ maupun Java dimulai dari 0, bukan 1 seperti dalam bahasa Pascal.
Array memiliki 3 contoh :

Satu Dimensi
Dua Dimensi
Banyak Dimensi

Array satu dimensi adalah kumpulan elemen-elemen yang identik, yang tersusun dalam satu baris. Elemen mimiliki tipe yang sama tetapi isi dari elemen bisa sama dan berbeda

Dua Dimensi / Banyak dimensi biasa sering digunakan untuk menampilkan grafik yang berdasarkan kriteria-kriteria tertentu. contoh seperti deklarasi matrix.

Pengertian Matriks

Matriks adalah kumpulan bilangan, simbol, atau ekspresi, berbentuk persegi panjang yang disusun menurut baris dan kolom. Bilangan-bilangan yang terdapat di suatu matriks disebut dengan elemen atau anggota matriks.

Contoh matriks dengan 2 baris dan 3 kolom yaitu

$\begin{bmatrix}1 & 9 & -13 \\20 & 5 & -6 \end{bmatrix}.$

Pemanfaatan matriks misalnya dalam menemukan solusi sistem persamaan linear. Penerapan lainnya adalah dalam transformasi linear, yaitu bentuk umum dari fungsi linear, misalnya rotasi dalam 3 dimensi.

Matriks seperti halnya variabel biasa dapat dimanipulasi, seperti dikalikan, dijumlah, dikurangkan dan didekomposisikan. Dengan representasi matriks, perhitungan dapat dilakukan dengan lebih terstruktur.

$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \!$

Operasi Dasar

Penjumlahan dan pengurangan matriks

Penjumlahan dan pengurangan matriks hanya dapat dilakukan apabila kedua matriks memiliki ukuran atau tipe yang sama. Elemen-elemen yang dijumlahkan atau dikurangi adalah elemen yang posisi atau letaknya sama.

$a_{ij} \pm b_{ij} = c_{ij}\!$

atau dalam representasi dekoratfinya

$\begin{bmatrix} {3} & {4} \\ {6} & {5} \\ \end{bmatrix} \!$

$\begin{bmatrix} (a_{11} \pm b_{11}) & (a_{12} \pm b_{12}) & (a_{13} \pm b_{13}) \\ (a_{21} \pm b_{21}) & (a_{22} \pm b_{22}) & (a_{23} \pm b_{23}) \\ \end{bmatrix} = \begin{bmatrix} c_{11} & c_{12} & c_{13} \\ c_{21} & c_{22} & c_{23} \\ \end{bmatrix} \!$

Perkalian skalar

Matriks dapat dikalikan dengan sebuah skalar.

$\lambda\cdot A := (\lambda\cdot a_{ij})_{i=1, \ldots , m; \ j=1, \ldots , n}$

Contoh perhitungan :

$5 \cdot \begin{pmatrix} 1 & -3 & 2 \\ 1 & 2 & 7 \end{pmatrix} = \begin{pmatrix} 5 \cdot 1 & 5 \cdot (-3) & 5 \cdot 2 \\ 5 \cdot 1 & 5 \cdot 2 & 5 \cdot 7 \end{pmatrix} = \begin{pmatrix} 20 & -15 & 10 \\ 5 & 10 & 35 \end{pmatrix}$

Perkalian matriks

Matriks dapat dikalikan, dengan cara tiap baris dikalikan dengan tiap kolom, lalu dijumlahkan pada baris yang sama.

$c_{ij}=\sum_{k=1}^m a_{ik}\cdot b_{kj}$

Contoh perhitungan:

$\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{pmatrix} \cdot \begin{pmatrix} 6 & -1 \\ 3 & 2 \\ 0 & -3 \end{pmatrix} = \begin{pmatrix} 1 \cdot 6 + 2 \cdot 3 + 3 \cdot 0 & 1 \cdot (-1) + 2 \cdot 2 + 3 \cdot (-3) \\ 4 \cdot 6 + 5 \cdot 3 + 6 \cdot 0 & 4 \cdot (-1) + 5 \cdot 2 + 6 \cdot (-3) \\ \end{pmatrix} = \begin{pmatrix} 12 & -6 \\ 39 & -12 \end{pmatrix}$

Source : Wikipedia

Set / himpunan

Dalam matematika, Set / himpunan adalah segala koleksi benda-benda tertentu yang dianggap sebagai satu kesatuan. Walaupun hal ini merupakan ide yang sederhana, tidak salah jika himpunan merupakan salah satu konsep penting dan mendasar dalam matematika modern, dan karenanya, studi mengenai struktur kemungkinan himpunan dan teori himpunan, sangatlah berguna.

Teori himpunan, yang baru diciptakan pada akhir abad ke-19, sekarang merupakan bagian yang tersebar dalam pendidikan matematika yang mulai diperkenalkan bahkan sejak tingkat sekolah dasar. Teori ini merupakan bahasa untuk menjelaskan matematika modern. Teori himpunan dapat dianggap sebagai dasar yang membangun hampir semua aspek dari matematika dan merupakan sumber dari mana semua matematika diturunkan.

Notasi Himpunan / Set

Simbol	Arti
$\{ \}$ atau $\varnothing$	Himpunan kosong
$\cup$	Operasi gabungan dua himpunan
$\cap$	Operasi irisan dua himpunan
$\subseteq$ , $\subset$ , $\supseteq$ , $\supset$	Subhimpunan, Subhimpunan sejati, Superhimpunan, Superhimpunan sejati
$A^C$	Komplemen
$\mathcal{P}(A)$	Himpunan kuasa


		Kardinalitas Kardinalitas dari sebuah himpunan dapat dimengerti sebagai ukuran banyaknya elemen yang dikandung oleh himpunan tersebut. Banyaknya elemen himpunan $\{apel, jeruk, mangga, pisang\}$ adalah 4. Himpunan $\{p, q, r, s\}$ juga memiliki elemen sejumlah 4. Berarti kedua himpunan tersebut ekivalen satu sama lain, atau dikatakan memiliki kardinalitas yang sama. Dua buah himpunan A dan B memiliki kardinalitas yang sama, jika terdapat fungsi korespondensi satu-satu yang memetakan A pada B. Karena dengan mudah kita membuat fungsi $\{(apel,\,p),\,(jeruk,\,q),\,(mangga,\,r),\,(pisang,\,s)\}$ yang memetakan satu-satu dan kepada himpunan A ke B, maka kedua himpunan tersebut memiliki kardinalitas yang sama. Jenis - jenis Set union union adalah dimana kedua himpunan di gambungkan isinya. contoh : A { 1.2.3.4.5} B { 3.4.6.7.8} unionnya adalah { 1.2.3.4.5.6.7.8} Intersections intersection adalah dimana ada isi yang sama. contoh : A { 1.2.3.4.5} B { 3.4.6.7.8} Intersectionya adalah {3.4} Complements complement adalah dimana himpunan yang satu memiliki anggota yang tidak dimiliki himpunan yang lain. contoh : A { 1.2.3.4.5} B { 3.4.6.7.8} complement A adalah {1.2.5} sedangkan complement B adalah {6.7.8} Source : wikipedia