Sorting

Sorting alias pengurutan, merupakan suatu hal yang sangat dibutuhkan dalam
pemrograman tingkat tinggi. Ada 5 metode sorting, yaitu:

1. Buble Sort

Bubble Sort merupakan metode pengurutan data dengan prinsip: data indeks
ke i dibandingkan dengan data indeks (i+1), apabila data di index ke i lebih besar
(tidak sesuai) dari data di indeks (i+1) maka data akan ditukar. Demikian seterusnya
hingga semua data dalam keadaan terurut (sesuai). Proses dasar yang terjadi dalam
algoritma ini adalah proses pertukaran nilai (swapping).

2. Selection Sort

Selection Sort merupakan algoritma pengurutan atau sorting yang sederhana

namun memiliki performa yang baik (One of the simplest sorting algorithms),
algoritma ini bisa disebut kombinasi antara searching dan sorting. Untuk melakukan
sorting atau pengurutan secara ascending (menaik dari kecil ke besar), elemen (nilai)
yang paling kecil di antara elemen yang belum urut, disimpan indeksnya, selanjutnya
dilakukan pertukaran anatara nilai elemen dengan nilai indeks yang disimpan tersebut
dengan nilai elemen yang paling depan (pertama). Sedangkan untuk sorting
descending (menurun dari besar ke kecil), elemen yang paling besar yang disimpan
indeksnya kemudian ditukar.

Selection Sort disukai karena kesederhanaan algoritmanya dan performanya

yang lebih bagus dari beberapa algoritma lain yang lebih rumit. Algoritma ini dapat di
ilustrasikan bekerja seperti dibawah ini:

 Pertama cari data terkecil (data dengan nilai terkecil) dari semua data. kemudian
ditukar nilainya dengan data pertama.
 Kemudian cari data terkecil dari data kedua sampai data yang terakhir, kemudian
ditukar nilainya dengan data kedua (data terkecil kedua ditukan posisinya dengan data
kedua).
 Kemudian cari data terkecil dari data ketiga sampai data terakhir, lalu tukar nilainya
dengan data yang ketiga.
 Begitu seterusnya sampai semua data menjadi terurut. Apabila ada N buah data yang
akan kita diurutkan, maka kita butuh N-1 langkah pengurutan, dengan data yang
terakhir, yaitu data ke N tidak perlu diurutkan sebab nilainya sudah pasti yang
terkecil.

3. Insertion Sort
 Insertion Sort merupakan algoritma sorting, terutama untuk mengurutkan data
dengan jumlah elemen sedikit. Dimana Input berupa deretan angka sejumlah n buah
data dan Output berupa permutasi (pengurutan) sejumlah n angka dari input, dimana
hasilnya berupa data yang sudah terurut secara ascending maupun descending.

Proses yang terjadi pada pengurutan dengan Insertion Sort adalah dimulai dari
data ke-2 kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama
dianggap memang sudah benar pada tempatnya. Ilustrasinya mirip seperti saat
menyisipkan kartu di permainan kartu. Dimulai dengan tangan kiri yang kosong dan
kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan
diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi
yang benar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan
kiri) secara berurutan.

4. Counting Sort

Counting sort merupakan algoritma soring (pengurutan) yang dapat dilakukan

apabila data dapat dinyatakan sebagai bilangan yang menyatakan besarannya.
Rentang nilai bilangan itu tidak boleh terlalu besar, karena akan dibuat array yang
besarnya sama dengan rentangnya. Ide Counting sort seperti kita melakukan
perhitungan pemilu yaitu dengan mencatat frekuensi atau banyaknya kemunculan
data. Namun metode ini hanya cocok digunakan bila data yang digunakan bertipe
integer dan dibatasi pada range tertentu. Biasanya counting sort hanya digunakan
untuk mengurutkan angka.

 Keungggulan Algoritma Counting Sort adalah dapat mengurutkan dengan waktu yang
lebih singkat, karena tidak membandingkan dengan elemen lain.

 Kelemahan Algoritma Counting Sort adalah menggunakan array yang terlalu banyak.

5. Shell Sort

Shell sort 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.

Shell Sort merupakan salah satu algoritma pengurutan yang lebih handal
dibandingkan Selection Sort dan Bubble Sort. Kehandalannya yaitu: “Membagi deret
data menjadi dua bagian. Masing-masing bagian diurutkan menggunakan Bubble
Sort. Tidak menggunakan iterasi melainkan increment. Perulangan diakukan sesuai
nilai increment.”
 Proses pengurutan dengan Shell sort dapat disimulasikan sebagai berikut:

Pertama menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu
N/2. Data pertama dibandingkan dengan data dengan jarak N/2. Apabila data pertama
lebih besar dari data ke N/2 tersebut maka kedua data tersebut ditukar. Kemudian data
kedua dibandingkan dengan jarak yang sama yaitu N/2. Demikian seterusnya sampai
seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data
ke-(j + N/2).

Pada proses berikutnya, digunakan jarak (N/2) / 2 atau N/4. Data pertama
dibandingkan dengan data dengan jarak N/4. Apabila data pertama lebih besar dari
data ke N/4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua
dibandingkan dengan jarak yang sama yaitu N/4. Demikianlah seterusnya hingga
seluruh data dibandingkan sehingga semua data ke-j lebih kecil dari data ke-(j + N/4).

Pada proses berikutnya, digunakan jarak (N/4) / 2 atau N/8. Demikian

seterusnya sampai jarak yang digunakan adalah 1.

Algoritma metode Shell dapat dituliskan sebagai berikut:

1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j=0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9
8. Jika (Data[j] > Data [j + Jarak] maka tukar Data[j], Data [j + Jarak], Sudah = true
9. j=j+1
 DAFTAR PUSTAKA

[Link]
[Link]
[Link]
[Link]
[Link]
[Link]