SORTING

Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun
kembali humpunan obyek menggunakan aturan tertentu. Mnurut Microsoft Book-shelf,
definisi algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data
ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.
Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu
• urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling
besar
• urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling
kecil.
Contoh : data bilangan 5, 2, 6 dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan
turun menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau
lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence) seperti
dinyatakan dalam tabel ASCII (Lampiran)
Keuntungan dari data yang sudah dalam keadaan terurutkan antara lain :
• data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk
dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita
mudah melakukan pengeekan apakah ada data yang hilang
• melakukan komppilasi program komputer jika tabel-tabel simbol harus dibentuk
• mempercepat proses pencarian data yang harus dilakukan berulang kali.
48
Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data
yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi,
bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi
tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan.
Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara
lain:
• banyak data yang diurutkan
• kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki
• tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan
yang lain.
Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan. Metode
pengurutan yang digunakan dapat diklasifikasikan menjadi dua katagori yaitu :
• pengurutan internal, yaitu pengurutan dengan menggunakan larik (array). Larik
tersimpan dalam memori utama komputer
• pengurutan eksternal, yaitu pengurutan dengan menggunakan berkas (sequential
access file). Berkas tersimpan dalam pengingat luar, misalnya cakram atau pita
magnetis.

Macam-macam Sorting:

• Buble Sort :

Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.

• Selection Sort :

Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

• Insertion Sort :

Algoritma insertion sort pada dasarnya 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.

• Shell Sort :

Merupakan algoritma yang stau jenis dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir

author: wikipedia

• Merge Sort :

Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan
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.

author : Swfung8

• Quick Sort :

Algoritma ini berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
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.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

Author: Matt Chan

• Heap Sort:

Heap sort adalah sorting yang menggunakan struktur data heap, dengan nilai parent selalu lebih besar dari pada nilai childnya.
Algoritma:

1. Buat suatu heap.
2. Ambil isi dari root masukkan kedalam sebuah array.
3. Hapus element root dengan mempertahankan properti heap.
4. Ulangi sampai tree menjadi kosong

author : Swfung8

• Bucket Sort :

Algoritma:

• Cari nilai maksimum dan minimum di 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

• Radix Sort:

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.
Radix sortmerupakan sebuah algoritma pengurutan yang mengatur pengurutan nilai tanpa melakukan beberapa perbandingan pada data yang dimasukkan.