NPM : 59414226
Kelas : 1IA17
Mata Kuliah : Algoritma dan Pemrograman 1A
Dosen : Kunto Bayu A, ST
Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif. Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data.
Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna. Berikut macam-macam sorting:
- Bubble Sort
Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.
Bubble sort merupakan algoritma pengurutan / metode sorting paling sering digunakan dengan metode pengurutan paling sederhana. pada metode bubble sort, Pengurutan yang dilakukan dengan cara membandingkan masing-masing item / data dalam suatu list secara berpasangan, lalu menukar item tersebut jika diperlukan, dan mengulanginya sampai akhir list secara berurutan dengan sempurna, sehingga tidak ada lagi item yang dapat ditukar.
berikut contoh bubble sort :
- Selection Sort (Ascending)
Selection Sort merupakan metode pengurutan dengan cara memlilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih tersebut dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah :
1. Mencari data terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya dengan data pertama.
2. mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.
3. mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga
4. dan seterusnya sampai semua data turut naik. apabila terdapat n buah data yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya.
- Metode Penyisipan Langsung (Straight Insertion Sort) / Insertion sort
Insertion sort merupakan salah satu metode sorting dengan cara menyisipkan / insert. Pada dasarnya insertion sort memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan tersebut.
berikut contoh insertion Sort :
- Metode Penggabungan/Merge Sort
Metode Penggabungan (Merge Sort)
Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari
metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang
sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table
sehingga dalam keadaan urut.
Divide = Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
Conquer = setiap bagian dengan memanggil prosedur merge sort secara rekursif
Contoh
- Quick Sort
Quick sort merupakan metode pengurutan dengan algoritma berdasarkan pola divide-and-conquer.
Algoritma ini hanya memiliki 2 langkah sebagai berikut :
-Divide = bisa dikatakan Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
-Conquer = dengan cara Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array
berikut contoh quick sort :
- Metode Shell (Shell Sort)
Metode ini disebut juga dengan metode pertambahan menurun (diminishing
increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga
sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara
membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian
dilakukan penukaran bila diperlukan
berikut contoh shell sort :
- Heap sort
Heap sort merupakan metode sorting yang menggunakan struktur data heap, dengan nilai parent selalu lebih besar dari pada nilai childnya.
adapun langkah algoritma nya sebagai berikut :
Buat suatu heap
Ambil isi dari root, lalu masukkan kedalam sebuah array.
Hapus element root dengan mempertahankan properti heap.
Ulangi sampai tree menjadi kosong
Berikut contoh Heap Sort :
- Bucket Sort
Bucket Sort merupakan algoritma sorting yang mempartisi deret angka menjadi beberapa deret yang kemudian dianalogikan menjadi ember.
Algoritma nya sebagai berikut :
Cari nilai maksimum dan minimum di dalam array.
Inisialisasi array bucket Daftar <> unsur (ukuran maxValue – minValue + 1)
Pindahkan elemen dalam array untuk bucket
Write bucket keluar (dalam rangka) ke array yang asli
berikut contoh bucket sort :
- Radix Sort
Radix Sort adalah metode sorting yang ajaib yang mana mengatur pengurutan nilainya tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Secara umum yang proses yang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu dan dalam tiap kategorinya dilakukan pengklasifikasian lagi dan seterusnya sesuai dengan kebutuhan.
Secara kompleksitas waktu, radix sort termasuk ke dalam Divide and Conquer.Namun dari segi algoritma untuk melakukan proses pengurutan, radix sort tidak termasuk dalam Divide and Conquer.
Sumber
Tidak ada komentar:
Posting Komentar