sorting
TRANSCRIPT
TUGAS PERSENTASE1. BENI NOVIANTO 08 411 188
2. MARATUNAVINGAH 08 411 193
3. LUKMAN 08 411 206
4. FADLY RAIS. W 08 411 180
5. MUHAMMAD IKBAL. T 08 411 039
6. BUMIN. N. NASIR 08 411 115
7. ISTAMON SURBAKTI 08 411 208
8. GANANG ADY. P 08 411 190
9. RANDI SAPUTRA 08 411 194
10. NOVIJANTI A.R.TEMALURU 08 411 209
11. SEPRIANI. A. BATUBARA 08 411 158
12. JUAN S. UNIPLAITA 08 411 118
13. FERDY TANADI 08 411 156
14. BARKAH SAFARA 08 411 016
15. IGNASIUS HILIR 08 411 142
SORTING
A. PENGERTIAN
Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah.
Pada umumnya terdapat dua jenis pengurutan :- Ascending (Naik).- Descending (Turun).
Contoh :Data Acak : 22 10 15 3 8 2Terurut Ascending : 2 3 8 10 15 22Terurut Descending : 22 15 10 8 3 2`
B. METODE SORTING
Beberapa metode yang sudah umum digunakan diantaranya adalah :1. Bubble / Exchange Sort2. Selection Sort.3. Insertion Sort.4. Quick Sort.5. Heap Sort.6. Shell Sort.
1. Bubble Sort
Penguruttan Ascending jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebutt ditukar.
Penguruttan Descendiing Jiika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebutt ditukar.
Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis penguruttannya.
Ketika satu proses telah selesai, maka bubblle sortt akan mengulangi proses, demikian seterusnya dari 0 sampai dengan itterasii sebanyak n-1.
Kapan berhentinya? Bubblle sortt berhenti jika seluruh array tellah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Contoh :
• Diberikan data awal 22 10 15 3 8 2
• Proses 1
22 10 15 3 8 2 22 10 15 3 2 8 22 10 15 2 3 8 22 10 2 15 3 8 22 2 10 15 3 8 2 22 10 15 3 8
Proses 2 2 22 10 15 3 8 2 22 10 3 15 8 2 22 3 10 15 8 2 3 22 10 15 8
Proses 4
2 3 8 22 10 15 2 3 8 10 22 15
Hasil : 2 3 8 10 15 22
Proses 3 2 3 22 10 15 8 2 3 22 10 8 15 2 3 22 8 10 15 2 3 8 22 10 15
Proses 5 2 3 8 10 22 15
2 3 8 10 15 22
2. Selection Sort
Definisi• Merupakan kombinasi antara sorting dan searching• Misalnya untuk putaran pertama, akan dicari data
dengan nilai terkecil dan data ini akan ditempatkan pada index terkecil (Data[0]), pada putaran kedua akan dicari data kedua terkecil dan akan ditempatkan pada index kedua terkecil (data[1]).
• Selama proses, perbandingan dan pengubahan hanya dilakukan pada index pembanding saja, pertukaran data secara fisik terjadi pada akhir proses
Contoh :
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
• Diberikan data awal 22 10 15 3 8 2
3. Insertion Sort
Definisi :• 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 dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
• Pada penyisipan elemen, maka elemen-elemen lain 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 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
Hasil : 2 3 8 10 15 22
4. Quick SortDefinisi :Metode ini dikembangkan oleh C.A.R Hoare. Secara garis
besar metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang mempunyai N elemen. Kita pilih sembarang elemen dari data tersebut, bisanya elemen pertama, misalnya X. kemudian semua elemen tersebut disusun dengan menempatkan X pada posisi J sedemikian rupa sehingga elemen ke 1 sampai ke J-1 mempunyai nilai lebih kecil dari X dan elemen J+1 sampai ke N mempunyai nilai lebih besar dari X. Sampai saat ini kita sudah mempunyai dua sub data (kiridan kanan). Langkah berikutnya diulang untuk setiap sub data.
Contoh :
5. Heap Sort
Definisi :
• Salah satu teknik sortir yang memanfaatkan bentuk pohon binary.
• Maxheap adalah penyortiran dari besar ke kecil.
• Minheap adalah penyortian dari kecil ke besar.
Penulisan hasil sortir mengikuti langkah –langkah penghapusan hasil elemen sebagai berikut :
1.Hapus akar (root)2.Letakkan elemen data terakhir di posisi
akarnya3.Lakukan tindakan atas elemen data tersebut
seperi proses 14.Lakukan langkah 1 hingga pohon menjadi
kosong.
Max Heap
Contoh :
22 10 15 3 8 2
22
Proses 1 Proses 2
22
10
Proses 3
22
10 15
Pohon Maxheap
Proses 4
22
10 15
3
Proses 5
22
10 15
3 8
Proses 6
22
10 15
3 8 2
Sorting MaxHeap
22
10 15
3 8 2
Proses Sorting
2
10 15
3 8
= {22}
Fase 1
22
10 15
3 8 2
Fase 2
15
10 2
3 8
8
10 2
3
= {22, 15}
Fase 3
10
8 2
3
3
8 2
= {22, 15, 10}
Fase 4
8
3 2
2
3
= {22, 15, 10, 8}
Fase 5
3
2
2
= {22, 15, 10, 8, 3}
Hasil = {22, 15, 10, 8, 3, 2}
Minheap
Contoh :22 10 15 3 8 2
22
Proses 1 Proses 2
10
22
Proses 3
10
22 15
Pohon Minheap
Proses 4
3
10 15
22
Proses 5
3
8 15
22 10
Proses 6
2
8 3
22 10 15
Sorting MinHeap
2
8 3
22 10 15
Proses Sorting
15
8 3
22 10
= {2}
Fase 2
3
8 3
22 10
Fase 1
2
8 3
22 10 15
10
8 15
22
= {2, 3}
Fase 3
8
10 15
22
22
10 15
= {2, 3, 8}
Fase 4
10
22 15
15
22
= {2, 3, 8,10}
Fase 5
22
= {2, 3, 8, 10, 15, 22}
Hasil = {2, 3, 8, 10, 15, 22}
6. Shell Sort
Definisi :
Sortir ini digunakan untuk jumlah data yang besar.Dengan membagi-bagi menjadi sub-sub bagian mulai dari sedikit elemen hingga keseluruhan elemen tersebut menjadi data yang sudah urut.Sortir ini digunakan bila kapasitas memori tidak sanggup untuk menampung seluruh data yang akan disortir.
Contoh :
Diberikan data :
71,60,51,45,22,10,15,3,8,2,20,18,30,32
Pass 1 : data dibagi menjadi sub-sub yang tiap subnya berisi 2 elemen, kemudian disortir, hasilnya :
60,71 45,51 10,22 3,15 2,8 18,20 30,32
Pass 2 : gabungan dua subbagian sebelumnya menjadi 1 subbagian, kemudian disortir, hasilnya:
45,51,60,71 3,15 10,22 2,8,18,20 30,32
Pass 3 : Lakukan seperti langkah 2 hingga seluruh subbagian menjadi satu bagian.
3,10,15,22,45,51,60,71 2,8,18,20,30,32
Hasil Akhir :
2,3,8,10,15,18,20,22,30,32,45,51,60,71
