On Senin, 01 Juni 2015
Pada pertemuan ke 9 Algoritma Pemrograman dosen membahas
mengenai, sorting dan searching.
tp pada pertemuan ke 9 ini dosen hanya fokus membahas ke sorting.
Sorting (Pengurutan):
Sorting merupakan suatu proses (operasi) yang mengurutkan data dalam suatu urutan yang dikehendaki.
Pengurutan dapat dilakukan secara ascending (urut naik) maupun descending (urut turun).
Sorting dalam ilmu komputer dibagi menjadi 4 yakni:
1. Bubble Sort
Metode sorting termudah
Cara
pengurutannya : bandingkan dua data kemudian swap. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang
tepat, seperti gelembung.
Bubble Sort mengurutkan data dengan cara membandingkan elemen
sekarang dengan elemen berikutnya. Ascending : Jika elemen sekarang lebih besar
dari elemen berikutnya maka kedua elemen tersebut ditukar/swap. Descending :
Jika elemen sekarang lebih kecil dari elemen berikutnya,
maka kedua elemen tersebut ditukar/swap.
for (i=0; i < n-1; i++){
for (j=n-1; j > i; j--) {
if (X[j] < X[j-1]) {
tmp = X[j];
X[j] = X[j-1];
SWAP
X[j-1] = tmp;
}
}
}
2. Selection Sort
Cara
pengurutannya : seleksi data yang ada kemudian dilakukan swap (pertukaran
posisi).
Pada Ascending : seleksi data terkecil kemudian swap. Pada
descending : seleksi data terbesar kemudian swap.
Algoritma Selection Sort (Ascending)
- Tampung data ke-i
- Seleksi data terkecil
- Cek apakah data yang ditampung lebih besar dari data hasil
seleksi (data terkecil).
- Jika pengecekan langkah 3 bernilai “true” : lakukan pertukaran posisi antara data yang ditampung dengan data
terkecil.
- Ulangi langkah 1 sampai 4, hingga nilai i sama dengan n.
3. Insertion Sort
Cara pengurutannya : dimulai dari data
ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka
akan ditempatkan (diinsert) diposisi yang seharusnya.
Ascending : ketika perbandingan ambil data yang paling kecil.
Descending : ketika perbandingan ambil data yang paling
besar.
Algoritma Insertion Sort (Ascending)
- Ambil satu data ke-i simpan di temp
- Bandingkan data temp dengan data yang ada disebelah kiri satu per-satu
- Cek apakah data temp lebih kecil dari data sebelah kiri.
- Jika langkah sebelumnya bernilai “true” : lakukan pergeseran data satu-persatu
kemudian pada posisi yang tepat sisipkan data temp.
- Ulangi langkah sebelumya, hingga i sama dengan n.
for(i=1;i<n;i++){
t=X[i];
----->>>> Ambil data pertama
for (j =i-1; j >= 0; j--) {
if (t < X[j]){
X[j+1] = X[j]; ----->>> Penggeseran Data
X[j]=t;
Pergeseran data
Ambil data pertama
}
else {
X[j+1] = t;
break;
}}}
4. Merge Sort(Merging)
Cara
pengurutannya : memecah proses menjadi sub-proses. Bagi dua deret data, bandingkan, kemudian gabungkan (begitu seterusnya sampai selesai). Teknik
pemecahan proses menggunakan rekursif.
Permasalahan utama dipecah menjadi sub-masalah, kemudian
solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama. Mengimplementasikan
konsep rekursi. 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.
