Metode Sorting Dalam Pemrograman

Nama : Maulana Aji Pratama
NPM : 56414461
Kelas : 1IA17
Mata Kuliah : Algoritma & Pemrograman A
Dosen : Kunto Bayu A, ST.

Metode Sorting Dalam Pemrograman

Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting adalah proses pengurutan.

Beberapa algoritma untuk melakukan sorting:

◦ Bubble sort

◦ Selection sort

◦ Insertion sort

◦ Shell sort

◦ Merge sort

◦ Quick sort

◦ Heap sort

◦ Bubble Sort

Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan “mengapung” untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan “diapungkan” (ke indeks terkecil), artinya diangkat ke “atas” (indeks terkecil) melalui pertukaran. Karena
algoritma ini melakukan pengurutan dengan cara membandingkan elemen-elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.

◦ Selection Sort

Algoritma Selection sort memilih elemen maksimum/minimum array, lalu menempatkan elemen maksimum/minimum itu pada awal atau akhir array (tergantung pada urutannya ascending/descending). Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-based sorting.
Seperti pada algoritma Bubble Sort, proses memilih nilai maksimum /minimum dilakukan pada setiap pass. Jika array berukuran N, maka jumlah pass adalah N-1.
Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :

Algoritma pengurutan maksimum (maximum selection sort), yaitu memilih elemen maksimum sebagai basis pengurutan.

Algoritma pengurutan minimum (minimum selection sort), yaitu memilih elemen minimum sebagai basis pengurutan.

◦ Insertion Sort

Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort.

Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai “pass“), dengan indeks dimulai dari 0.

Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.

◦ 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. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :

Pertama-tama adalah 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 daripada 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

◦ Merge Sort

MergeSort adalah algoritma yang berdasarkan strategi divide-and-conquer. Algoritma ini tediri dari dua bagian utama, yaitu bagian pembagian list menjadi sublist-sublist yang lebih kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut.

1) Divide: membagi masalah menjadi beberapa submasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),

2) Conquer: memecahkan (menyelesaikan) masing-masing submasalah (secara rekursif), dan

3) Combine: mengabungkan solusi masing-masing submasalah sehingga membentuk solusi masalah semula.

◦ Quick Sort

Quick sort merupakan metode pengurutan dengan algoritma berdasarkan pola divide-and-conquer.

Algoritma ini hanya memiliki 2 langkah sebagai berikur :

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:

◦ 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

sumber:
http://eprints.undip.ac.id/19736/1/sorting.pdf
http://thenurulazizah.wordpress.com/artikel-2/13-metode-sorting/
http://dodik99.blogspot.com/2014/03/macam-macam-jenis-metode-sorting.html