[METODE PENGURUTAN DATA]

Pengertian Sort

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.

Metode Pengurutan Data

1.      Pengurutan data berdasarkan penyisipan dan penjagaan terurut.

a.       Insertion Sort

Insertion sort adalah algoritma sorting sederhana yang membangun array akhir diurutkan (atau daftar) satu item pada suatu waktu. Hal ini jauh lebih efisien dalam daftar besar daripada algoritma yang lebih canggih seperti quicksort, heapsort, atau menggabungkan semacam. Namun, insertion sort memberikan beberapa keuntungan:

Wikipedia pelaksanaan: Bentley menunjukkan C versi tiga baris, dan lima-line versi yang dioptimalkan [1]: 116.

Ø  Efisien untuk (cukup) set data kecil

Ø  Lebih efisien dalam praktek daripada kebanyakan lainnya sederhana kuadrat (yaitu, O (n2)) algoritma seperti pemilihan jenis atau bubble sort

Ø  Adaptive, yaitu, efisien untuk data set yang sudah substansial diurutkan: kompleksitas waktu O (nk) ketika setiap elemen dalam input tidak lebih dari k tempat jauh dari posisi diurutkan nya

Ø  Stabil; yaitu, tidak mengubah urutan relatif elemen dengan kunci yang sama

Ø  Di tempat; yaitu, hanya membutuhkan jumlah konstan O (1) ruang memori tambahan

Ø  online; yaitu, dapat mengurutkan daftar seperti itu menerimanya

Ø  Ketika orang-orang secara manual memilah sesuatu (misalnya, setumpuk kartu remi), sebagian besar menggunakan metode yang mirip dengan insertion sort. [2]

Contoh grafis insertion sort.

Insertion sort iterates, mengkonsumsi satu elemen input setiap pengulangan, dan tumbuh daftar keluaran diurutkan. Setiap iterasi, insertion sort menghapus satu elemen dari input data, menemukan lokasi itu milik dalam daftar diurutkan, dan memasukkan ke sana. Ini mengulangi sampai tidak ada unsur masukan tetap.

Sortasi biasanya dilakukan di tempat, dengan iterasi atas array, tumbuh daftar diurutkan belakangnya. Pada setiap array posisi, cek nilai ada terhadap nilai terbesar dalam daftar diurutkan (yang kebetulan sebelahnya, dalam array-posisi sebelumnya diperiksa). Jika lebih besar, ia meninggalkan unsur di tempat dan bergerak ke depan. Jika lebih kecil, ia menemukan posisi yang benar dalam daftar diurutkan, menggeser semua nilai yang lebih besar untuk membuat ruang, dan memasukkan ke dalam posisi yang benar.

Array yang dihasilkan setelah k iterasi memiliki properti di mana pertama k + 1 entri diurutkan ("+1" karena masuknya pertama dilewati). Dalam setiap iterasi masuknya sisa pertama input dihapus, dan dimasukkan ke dalam hasil pada posisi yang benar, sehingga memperpanjang hasil

dengan setiap elemen yang lebih besar dari x disalin ke kanan seperti yang dibandingkan terhadap x.

Varian yang paling umum dari insertion sort, yang beroperasi pada array, dapat digambarkan sebagai berikut:

1. Misalkan ada sebuah fungsi yang disebut Insert dirancang untuk memasukkan nilai ke urutan diurutkan di awal array. Ini beroperasi dengan mulai pada akhir urutan dan pergeseran setiap elemen satu tempat ke kanan sampai posisi yang cocok ditemukan unsur baru. Fungsi ini memiliki efek samping Timpa nilai yang tersimpan setelah urutan diurutkan dalam array.

2. Untuk melakukan semacam penyisipan, mulai dari elemen paling kiri dari array dan memanggil Insert untuk menyisipkan setiap elemen ditemui dalam posisi yang benar. Urutan memerintahkan di mana elemen dimasukkan disimpan pada awal array di set indeks yang sudah diperiksa. Setiap penyisipan menimpa nilai tunggal: nilai yang dimasukkan.

Pseudocode dari algoritma lengkap berikut, di mana array berbasis nol: [1]: 116

for i ← 1 to length(A) - 1

    j ← i   

    while j > 0 and A[j-1] > A[j]

        swap A[j] and A[j-1]

        j ← j - 1

    end while

end for

Loop luar berjalan di atas semua elemen kecuali yang pertama , karena awalan tunggal elemen A [ 0 : 1 ] adalah sepele diurutkan , sehingga invarian bahwa saya pertama + 1 entri diurutkan benar dari awal . Batin lingkaran bergerak elemen A [ i] ke tempat yang benar sehingga setelah loop , i pertama + 2 unsur diurutkan .

Setelah memperluas " Swap " operasi - tempat seperti t ← A [ j ] ; A [ j ] ← A [ j - 1 ] ; A [ j - 1 ] ← t ( dimana t adalah variabel sementara ) , versi yang sedikit lebih cepat dapat diproduksi yang bergerak A [ i ] untuk posisinya dalam satu pergi dan hanya melakukan satu tugas dalam lingkaran dalam tubuh : [ 1 ] : 116

Loop batin yang baru bergeser unsur ke kanan untuk membersihkan tempat untuk x = A [ i ] .

Perhatikan bahwa meskipun praktek umum adalah untuk menerapkan di tempat , yang mengharuskan memeriksa unsur-unsur di -order , urutan pengecekan ( dan menghapus ) elemen masukan sebenarnya sewenang-wenang . Pilihan dapat dilakukan dengan menggunakan hampir pola apapun , asalkan semua elemen input akhirnya diperiksa ( dan dihapus dari input ) .

b.      Tree Sort

Metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output: PreOrder, InOrder, dan PostOrder.

Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dan sebagainya. Dalam tree sort ada istilah akar atau root dan daun atau leaf.

2.      Pengurutan data berdasarkan perbandingan

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

Proses dalam Bubble sort dilakukan sebanyak N-1 langkah (pass) dengan N adalah ukuran array. Pada akhir setiap langkah ke – I , array L[0..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut L[0..I] dan bagian yang belum terurut L[I+1..N-1]. Setelah langkah terakhir, diperoleh array L[0..N-1] yang terurut menaik.

b.      Exchange Sort

Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. Jadi waktu untuk melakukan proses sorting lebih cepat. Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama dengan buble sort.

Contoh procedure exchange sort :

Procedure asc_buble (var data :array; jmldata:integer);

Var

i,j : integer;

begin

for i := 2 to jmldata do

for j :=jmldata downto i do

if data [j] <  data [j-1] then

tukardata (data[j], data [j-1] ) ;

end;

3.      Pengurutan data berdasarkan prioritas.

a.       Selection Sort

Pada algoritma selection sort mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection sort ini membandingkan elemen yang saat ini dengan suatu elemen yang berikutnya hingga elemen yang terakhir. Apabila ditemukan elemen lain yang lebih kecil dari elemen yang saat ini maka dicatat posisinya dan kemudian ditukar.

Algoritma Selection Sort (Ascending)

a.       Tampung data ke-i

b.      Seleksi data terkecil

c.       Cek apakah data yang ditampung lebih besar dari data, hasil seleksi (data terkecil).

d.      Jika pengecekan langkah 3 bernilai “true” : lakukan pertukaran posisi antara data yang ditampung dengan data terkecil.

e.       Ulangi langkah 1 sampai 4, hingga nilai i sama dengan n.

b.      Heap Sort

Metode heap sort adalah metode dari pengembangan tree. Heap sort memiliki kecepatan O(NlogN). Heap sort melakukan suatu pengurutan menggunakan suatu struktur data yang di sebut heap. Heap memiliki kompleksitas yang besar dalam pembuatan kodenya, tetapi heap sort mampu mengurutkan data-data yang sangat banyak dengan waktu yang cepat. Dalam sorting biasanya mempunyai sebuah aturan, berikut adalah aturan dari heap sort :

1.      Untuk mengisikan heap dimulai dari level 1 sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka tidak boleh mengisi dibawahnya.

2.      Heap dlm kondisi terurut apabila left child <> parent.

3.      Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap.

4.      Bila menghapus heap dgn mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.

Berikut adalah langkah-langkahnya dari metode heap sort. Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah yaitu insert_heap dan build_heap,

Ø  Insert_heap :

Pada bagian ini bertujuan untuk penghapusan suatu simpul pada heap tree. pemilihan sebuah simpul untuk ditempatkan di posisi yang lebih atas, dan menjaga tree tersebut tetap sebuah heaptree.

Berikut langkahnya :

1.      Setiap simpul yang dihapus(low) dicari anaknya yang memiliki kunci terbesar/terkecil(large)

2.      Anak dengan kunci yang lebih besar dipromosikan ke tempat simpul yang di hapus.

Langkah 1 dan 2 akan di lakukan berulang kali sampai simpul yang dihapus tidak punya anak lagi atau simpul yang ingin dipromosikan lebih besar/kecil daripada anak dari simpul yang dihapus yang memiliki kunci terbesar/terkecil.

Ø  Build Heap :

Pada bagian ini kita akan merapikan data-data yang telah acak tadi, sehingga membentuk heap yang sempurna. kita dapat menggunakan fungsi insert_heap untuk memasukkan setiap masukan ke bagian heap yang terdiri dari semua masukan yang masuk. Sehingga jadilah heap yang sempurna.

Algoritma untuk heap sort :

function heapSort(a, count) is

input: sebuah larik tidak terurut a dengan panjang length

(pertama letakkan a dalam max-heap) heapify(a, count)

end := count -1

while end > 0 do

remove ( )

reheapify ( )

end := end – 1

4.      Pengurutan data berdasarkan pembagian dan penguasaan

a.       Quick Sort

Quicksort merupakan Algoritma Sorting yang dikembangkan oleh Tony Hoare yang, secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan O(n²), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).

Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritma sorting yang stabil.

Algoritma

Quicksort merupakan Algoritma Pembagi. Pertama sekali quicksort membagi list yang besar menjadi dua buah sub list yang lebih kecil: element kecil dan element besar. Quicksort kemudian dapat menyortir sub list itu secara rekursif.

Langkah-Langkah pengerjaannya ialah:

1. Ambil sebuah elemen, yang disebut dengan pivot, pada sebuah daftar.
2. Urutkan kembali sebuah list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut Partition.
3. Sub list kemudian disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen yang lebih besar.

Kasus dasar dari rekusrif ialah list dari besaran nol atau satu, yang tidak perlu untuk di sorting.

Versi Sederhana

Dalam Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut:

 function quicksort('array')

if length('array') ≤ 1

          return 'array'  // an array of zero or one elements is already sorted

       select and remove a pivot value 'pivot' from 'array'

       create empty lists 'less' and 'greater'

       for each 'x' in 'array'

                 if 'x' ≤ 'pivot' then append 'x' to 'less'

              else append 'x' to 'greater'

        return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

Contoh keseluruhan dari quicksort pada kumpulan acak dari angka. Element yang gelap merupakan pivot. Pivot selalu dipilih sebagai element terakhir pada partisi. Bagaimanapun, selalu memilih elemen terakhir pada partisi sebagai pivot sehingga hasil pada kasus terburuk () pada daftar yang telah diurutkan, atau daftar yang serupa. Karena elemen yang sama memotong hingga pada akhir dari prosedur soring pada jumlah yang besar, versi dari algoritma quicksort yang memilih pivot sebagai elemen tengah berjalan lebih cepat dari pada algortima yang dijelaskan pada diagram ini pada sejumlah besar angka.

Perlu diperhatikan bahwa kita hanya memeriksa elemen dengan membandingkan mereka pada elemen yang lain. Prosedur ini disebuk Sorting Pembandingan. Jenis ini juga merupakan jenis sorting yang stabil (asumsikan bahwa untuk setiap method menerima elemen pada urutan aslinya dan pivot yang dipilih merupakan elemen terakhir dari nilai yang sama).

Kebenaran dari algoritma partisi didasari pada dua argumen berikut:

• Pada setiap iterasi, seluruh elemen diproses selama ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai pivot, setelah pivot lebih besar dari nilai pivot (Invarian Loop).

Kebenaran dari keseluruhan algortima dapat dibuktikan dengan penyederhanaan fakta: untuk elemen nol atau satu, algoritma tidak akan mengubah data; untuk jumlah data yang lebih besar, algoritma akan menghasilkan dua bagian, elemen yang kurang dari pivot dan elemen yang lebih besar dari nya, data ini sendiri akan diurutkan secara hipotesa rekursif.

Contoh dari penerapan Quicksort.

Partisi ditepat bekerja pada daftar yang kecil. Elemen kotak merupakan element pivot, elemen berwarna biru merupakan elemen yang bernilai kecil atau sama, dan elemen yang berwarna merah lebih besar.

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

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

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

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

Algoritma Merge Sort

Merge Sort (A,p,r)

Dimana A = lariknya

             P= Posisi Indeks 1

            r : posisi indeks 2

qß(p+r)/2                                                                                 T(n) = 2

Merge Sort (A,p,r)                                                      n

   if p < r then                                                              1

      q¬(p+r)/2                                                               (n/2)

      Merge-Sort(A, p, q)                                 T(n/2)

      Merge-Sort(A, q+1, r)                              (divide + (n/2)

      Merge(A, p, q, r)                                      combine (O) karena linear.

5.      Pengurutan berkurang menurun.

a.       Shell Sort

Metode ini disebut juga dengan metode pertambahan menurun. 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

REFERENSI

http://en.wikipedia.org/wiki/Insertion_sort (2 April 2015; 15.30)

http://mathbits.com/MathBits/CompSci/Arrays/Exchange.htm (4 April 2015; 09.30)

https://thenurulazizah.wordpress.com/artikel-2/13-metode-sorting/ (4 April 2015; 10.30)