PENGURUTAN (Sorting)

Sorting merupakan suatu proses untuk menyusun kembali himpunan 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

1. 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 yang akan saya bahas kali ini meliputi :

1. Insertion Sort (Metode Penyisipan).
2. Merge Sort (Metode Penggabungan).

1. 1.      Insertion Sort (Metode Penyisipan).

Straight Insertion Sort (Metode Penyisipan langsung).

Proses pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut :

Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu(Remi/domino). Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

Algoritma penyisipan langsung dapat dituliskan sebagai berikut :

1. 1.      i ← 1
2. 2.      selama (i < N) kerjakan baris 3 sampai dengan 9
3. 3.      x ← Data[i]
4. 4.      j ← i – 1
5. 5.      selama (x < Data[j]) kerjakan baris 6 dan 7
6. 6.      Data[j + 1] ← Data[j]
7. 7.      j ← j – 1
8. 8.      Data[j+1] ← x
9. 9.      i ← i + 1

Untuk lebih memperjelas langkah-langkah Algoritma Penyisipan Langsung dapat dilihat pada tabel di bawah ini :

34

67

23

28

98

15

89

67

28

18

Jika data di atas akan diurutkan dengan urutan menaik (ascending) menggunakan metode penyisipan langsung (straight insertion) maka prosesnya adalah sebagai berikut :

Data Sisip	Hasil Pengurutan
67	34 67 23 28 98 15 89 67 28 18 Pada perulangan ke-1 data pada array indeks2 dijadikan sebagai data sisip, kemudian dibandingkan dengan data sebelumnya, jika data sebelumnya tidak ada yang lebih besar dari data sisip maka tidak ada data yang harus di geser ke belakang.
23	34 67 23 28 98 15 89 67 28 18 Pada perulangan ke-2 data pada array indeks 3 dijadikan sebagai data sisip, kemudian dibandingkan dengan data sebelumnya, terdapat dua data  yang lebih besar di banding data sisip maka dua data itu harus di geser satu tempat dan data sisip dipindah ke tempat paling depan.
28	23 34 67 28 98 15 89 67 28 18 Pada perulangan ke-3 data pada array indeks 4 dijadikan sebagai data sisip, kemudian dibandingkan dengan data sebelumnya, terdapat dua data  yang lebih besar di banding data sisip maka dua data itu harus di geser satu tempat dan data sisip dipindah ke tempat sebelum dua data yang digeser.
98	23 28 34 67 98 15 89 67 28 18 Pada perulangan ke-4 data pada array indeks5 dijadikan sebagai data sisip, kemudian dibandingkan dengan data sebelumnya, jika data sebelumnya tidak ada yang lebih besar dari data sisip maka tidak ada data yang harus di geser ke belakang.
15	23 28 34 67 98 15 89 67 28 18 Pada perulangan ke-5 data pada array indeks 6 dijadikan sebagai data sisip, kemudian dibandingkan dengan data sebelumnya, terdapat lima data  yang lebih besar di banding data sisip maka lima data itu harus di geser satu tempat dan data sisip dipindah ke tempat paling depan.
89	15 23 28 34 67 98 89 67 28 18 Pada perulangan ke-6 data pada array indeks 7 dijadikan sebagai data sisip, kemudian dibandingkan dengan data sebelumnya, terdapat satu data  yang lebih besar di banding data sisip maka satu data itu harus di geser satu tempat dan data sisip dipindah ke tempat sebelum data yang digeser.
67	15 23 28 34 67 89 98 67 28 18 Pada perulangan ke-7 data pada array indeks 8 dijadikan sebagai data sisip, kemudian dibandingkan dengan data sebelumnya, terdapat dua data  yang lebih besar di banding data sisip maka dua data itu harus di geser satu tempat dan data sisip dipindah ke tempat sebelum data yang digeser.
28	15 23 28 34 67 67 89 98 28 18 Pada perulangan ke-8 data pada arry indeks 9 dijadikan sebaga data sisip, kemudian dibandingkan dengan data sebelumnya, terdapat lima data yang lebih besar dibanding data sisip maka lima data itu harus digeser satu tempat dan data sisip dipindah ke tempat sebelum data yang digeser.
18	15 23 28 28 34 67 67 89 98 18 Pada perulangan ke-9 data pada arry indeks 10 dijadikan data sisip, kemudian dibandingkan dengan data sebelumnya, terdapat delapan data yang lebih besar dibandaing data sisip, maka delapan data itu harus digeser satu tempat dan data sisip dipindah ke tempat sebelum data yang digeser
Hasl Akhir	15 18 23 28 28 34 67 67 89 98

Di bawah ini merupakan prosedur yang menggunakan metode penyisipan langsung.

void StraighInsertSort(){

int i, j, x;

for(i=1; i<Max; i++){

x = Data[i];

j = i – 1;

while (x < Data[j]){

Data[j+1] = Data[j];

j–;        }

Data[j+1] = x;

}          }

Prosedur Pengurutan dengan Metode Penyisipan Langsung

Dari algoritma dan prosedur diatas, jumlah perbandingan (=C) minimum, rata-rata dan maksimum pada metode penyisipan langsung adalah

Cmin = N – 1

Crata-rata = (N2 + N + 2) / 4

Cmax = (N2 + N – 2) / 2

Jumlah perbandingan minimum terjadi jika data sudah dalam keadaan urut, sebaliknya jumlah perbandingan maksimum terjadi jika data dalam keadaan urut terbalik. Cara menghitung Cmin adalah dengan melihat kalang paling luar yaitu i, pengulangan ini dimulai dari 1 sampai dengan N-1 atau sama dengan N-1 Cara menghitung Cmax dengan menganggap selalu terjadi pergeseran. Kalang dalam (while) diatas akan melakukan pengulangan dari 0 sampai dengan i. Apabila hal ini dilakukan sebanyak N-1 kali, maka Cmax adalah jumlah dari deret aritmetik 2, 3, 4, …, N atau (N – 1) / 2 . (2 + N)

Cara menghitung Crata-rata adalah dengan menjumlahkan Cmin dan Cmax dan dibagi dengan 2. Jumlah penggeseran (=M) minimum, rata-rata dan maksimum untuk metode penyisipan langsung adalah :

Mmin = 2(N – 1)

Mrata-rata = (N2 + 7N – 8) / 4

Mmax = (N2 + 3N – 4) / 2

Kekurangan Dan Kelebihan Metode Penyisipan Langsung
Kelebihan	Kekurangan
Sederhana dalam penerapannya. Mangkus dalam data yang kecil. Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkandengan Quicksort. Mangkus dalam data yang sebagian sudah terurut. Lebih mangkus dibanding Bubble Sort dan Selection Sort. Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritmapengurutan tercepat pada jumlah elemen yang sedikit. Stabil.	Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik. Untuk larik yang jumlahnya besar ini tidak praktis. Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai danmengganti seluruh bagian sebelum menyisipkan elemen berikutnya. Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalampengurutan elemen dalam jumlah besar.

1. 2.      Merge Sort (Metode Penggabungan).

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Ia adalah seorang ilmuwan yang bekerja di laboratorium penelitian bola basket. Laboratorium tersebut berada jauh dari rumahnya sehingga ia memilih untuk menyewa sebuah tempat yang lebih dekat. Sebelum pindah, dia mengepak semua buku-bukunya ke dalam kardus kecil.

Begitu tiba, dia mengambil buku dan mengaturnya di rak berdasarkan urutan ketinggian buku tersebut. Dia menyadari bahwa jika dia membuka semua kardus dan memilah buku-bukuakan sangat  berantakan. Dia memutuskan bahwa ia akan memecahkan masalah ke dalam bityang lebih kecil. Pertama, dia membuka kardus dan mengatur buku di setiap kardus yangsesuai dengan ukuran tingginya. Setelah diatur, ia menggabungkan kardus-kardus tersebut. Hal itu  membuat pekerjaannya sedikit lebih mudah. Penggabungan elemen-elemen yang diurutkandari suatu himpunan yang kecil untuk mendapatkan urutan satu himpunan yang lebih  besar adalah lebih mudah daripada mengurutkan seluruh elemen himpunan yang besar bersama-sama. Maka terbentuklah jenis pengurutan data yang disebut merge sort.

Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut:

• Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
• Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut.

Algoritma Merge Sort sederhananya, dapat ditulis berikut:

• Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
• Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
• Gabung 2 sublist kembali menjadi satu list terurut.

Lebih jelas dan singkatnya, merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari 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.

1. Conquer

Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif.

1. 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.

1. 4.      Algoritma penggabungan dapat dituliskan sebagai berikut :
   1. i = 0
   2. j = 0
   3. J3 = 0
   4. Kerjakan baris 5 sampai dengan 7 selama (i < J1) atau (j < J2)
   5. J3 = J3 + 1
   6. Jika (T1[i] < T2[j]) maka T3[J3] = T1[i], i = i + 1
   7. Jika (T1[i] >= T2[j]) maka T3[J3] = T2[j], j = j + 1
   8. Jika (i > J1) maka kerjakan baris 9, jika tidak kerjakan baris 15
   9. i = j
   10. Selama (i < J2) kerjakan baris 11 sampai dengan 13
   11. J3 = J3 + 1
   12. T3[J3] = T2[i]
   13. i = i + 1
   14. Selesai
   15. j = i
   16. Selama (j < J1) kerjakan baris 17 sampai dengan 19
   17. J3 = J3 + 1
   18. T3[J3] = T1[j]
   19. j = j + 1 

Untuk lebih memperjelas langkah-langkah Algoritma Pengabungan dapat dilihat pada gambar di bawah ini :

Kelebihan Dan Kekurangan
Kelebihan	Kekurangan
Dibanding dengan algoritma lain, merge sort ini termasuk algoritma yang sangat efisien dalam penggunaannya sebab setiap list selalu dibagi bagi menjadi list yang lebih kecil, kemudian digabungkan lagi sehingga tidak perlu melakukan banyak perbandingan.	Metode Penggabungan dibutuhkan memory ekstra pada saat fase Merge, bukan menggunakan teknik ‘in-place’.

Tweet