NPM : 59414563
KELAS : 1ia17
MATA KULIAH : Algoritma dan Pemrograman A
DOSEN : Kunto Bayu A, S.T.
Pengertian Sorting
Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:
1. Urut naik (ascending)
Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar
2. Urut turun (descending)
Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.
Mengapa harus melakukan sorting data? Ada banyak alasan dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data tersebut tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka kita semakin mudah untuk menyisipkan data atapun melakukan penggabungan data.
Metode-metode sorting meliputi:
1. Bubble Sort
2. Selection Sort
3. Quick Sort
4. Insertion Sort
5. Merge Sort
6.Heap Sort
setelah mengerti tentang pengertian dari Sorting itu sendiri, sekarang kita masuk ke metode-metode sorting.
1. Bubble Sort
Bubble Sort merupakan metode pengurutan yang sering digunakan dengan metode yang paling sederhana. pada metode ini, Pengurutan dilakukan dengan cara membandingkan masing-masing item / data dalam suatu list secara berpasangan, lalu menukar data tersebut jika diperlukan, dan mengulanginya sampai akhir list secara berurutan dengan sempurna, sehingga tidak ada lagi data yang dapat ditukar.
2. Selection Sort
Selection Sort merupakan metode pengurutan dengan cara membaca seluruh elemen secara berurutan dan mencari nilai terendah. Kemudian membandingkan dan menukar elemen yang terpilih tersebut dengan elemen ke-a. Nilai dari a dimulai dari 1 ke n. Dimana n adalah jumlah total elemen dikurangi 1.
3. Quick Sort
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort.
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa, sehingga nilai variabel Sementara berada di suatu posisi ke I yang memenuhi kondisi sebagai berikut :
- Semua elemen di posisi ke 1 sampai dengan ke I-1 adalah lebih kecil atau sama dengan Sementara.
- Semua elemen di posisi ke I+1 sampai dengan ke N adalah lebih besar atau sama dengan Sementara.
4. Insertion Sort
Insertion Sort merupakan algoritma yang efisien untuk mengurutkan angka yang mempunyai jumlah elemen sedikit. Dimana:- Input : deretan angka sejumlah n buah
- Output : permutasi (pengurutan) sejumlah n angka dari input yang sudah terurut secara ascending maupun descending
Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.
Metode ini mengurutkan bilangan-bilangan yang telah dibaca; dan berikutnya secara
berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut.
- Output : permutasi (pengurutan) sejumlah n angka dari input yang sudah terurut secara ascending maupun descending
Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.
Metode ini mengurutkan bilangan-bilangan yang telah dibaca; dan berikutnya secara
berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut.
5. Merge Sort
Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.
Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.
6. Heap Sort
Heap adalah sebuah binary tree dengan ketentuan sebagai berikut :
Tree harus complete binary tree
- Semua level tree mempunyai simpul maksimum kecuali pada level terakhir.
- Pada level terakhir, node tersusun dari kiri ke kanan tanpa ada yang
dilewati.
Perbandingan nilai suatu node dengan nilai node child-nya mempunyai ketentuan berdasarkan
- Max Heap mempunyai ketentuan bahwa nilai suatu node lebih besar atau sama dengan ( >= ) dari nilai childnya.
- Min Heap mempunyai ketentuan bahwa nilai suatu node lebih kecil atau sama dengan ( <= ) dari nilai childnya.
Sumber :
Tidak ada komentar:
Posting Komentar