PENGURUTAN DATA ( SORTIR )

Sort adalah suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menurut suatu aturan tertentu. Biasanya pengurutan terbagi menjadi 2 yaitu : ascending 9pengurutan dari karakter / angka kecil ke karakter / angka besar) dan descending (pengurutan dari karakter / angka besar ke karakter / angka kecil).

Ada banyak cara yang dapat dilakukan untuk melakukan proses pengurutan dari paling tinggi ke paling rendah atau sebaliknya. Untuk masalah pengurutan pada array kita tidak bisa langsung menukar isi dari variabel yang ada, tetapi menggunakan metode penukaran(swap).

Perhatikan contoh berikut ini :
Umpamakan bahwa score[1]= 10 dan score[2]= 8 dan Anda ingin menukar nilai-nilai mereka sehingga score[1]= 8 dan score[2]= 10. Anda tidak bisa langsung menukar isi variable tersebut, seperti cara ini:

score[1] = score [2] ;
score[2] = score[1];

cara yang tepat adalah ;
temp = score[1]
score[1] = score[2];
score[2] = temp;

Untuk melakukan proses pengurutan dapat menggunakan beberapa metode antara lain:
o Pengantar Pengurutan Data
o Metode Bubble Sort
o Metode Pengurutan Seleksi
o Pengurutan dengan Penyisipan
o Pengurutan dengan Penyisipan Biner
o Metode Quick Sort
o Metode Merge Sort

Pengantar Pengurutan Data
Proses pengurutan banyak ditemukan dalam komputer. Hal itu karena data yang sudah urut akan lebih cepat untuk dicari. Untuk membentuk data yang tidak urut menjadi data yang urut, terdapat berbagi algoritma yang bisa digunakan. Beberapa algoritma akan dijelaskan pada bab ini.
Perlu diketahui bahwa pengurutan sendiri dapat dilakukan terhadap data yang secara keseluruhan diletakkan dalam memori ataupun terhadap data yang tersimpan pada pengingat eksternal. Pada bab ini pengurutan pada katagori pertama saja yang akan dibahas.
Di dalam pengurutan data terdapat istilah ascending dan descending. Pengurutan dengan dasar dari nilai yang kecil menuju ke nilai yang besar disebut ascending (urut naik), sedangkan yang disusun atas dasar dari nilai besar ke kecil disebut descending (urut turun).



Gambar Pengurutan

Metode Bubble Sort
Metode bubble sort, merupakan metode tersederhana untuk melakukan pengurutan data, tetapi memiliki kinerja yang terburuk untuk data yang besar. Pengurutan dilakukan dengan membandingkan sebuah bilangan dengan seluruh bilangan yang terletak sesudah bilangan tersebut. Penukaran dilakukan kalau suatu kriteria dipenuhi.

Sebagai contoh, terdapat kumpulan seperti berikut.
25 57 48 37 12 92 80 33
Contoh proses pengurutan dengan urut naik ditunjukkan pada gambar 11.2 sampai gambar 11.3.


Gambar Pengurutan tahap pertama




Gambar Pengurutan tahap kedua

Jika jumlah data adalah n, maka terjadi n-1 tahap pengurutan. Berarti pada contoh di di atas diperlukan 7 tahap pengurutan. Gambar 11.4 memperlihatkan setelah 7 tahap pengurutan dilakukan.


Gambar Keadaan untuk setiap tahap pengurutan

Contoh Implementasi pengurutan dengan metode bubble sort baik dalam bentuk algoritma dan program.

Algoritma :
SUBRUTIN bubble_sort(L,n)
Untuk tahap = 1 s/d n-1
Untuk j  0 s/d n-tahap-1
Jika L[j] > L[j+1] MAKA
// Lakukan penukaran
tmp  L[j]
L[j]  L[j+1]
L[j+1]  tmp
AKHIR – JIKA
AKHIR – UNTUK
AKHIR – UNTUK
AKHIR – SUBRUTIN

Contoh Pada contoh Gambar terlihat bahwa sebenarnya tidak diperlukan n-1 tahap untuk mengurutkan data. Pada tahap kelima data sebenarnya sudah terurutkan. Oleh karena itu metode bubble sort dapat diperbaiki agar begitu data sudah urut dan walaupun n-1 tahap belum terpenuhi, pengurutan segera diakhiri. Hal ini dapat dilaksanakan dengan melakukan pemeriksaan apakah masih ada penukaran data atau tidak. Kalau dalam suatu tahap ternyata tidak terjadi pertukaran data, maka iterasi segera dihentikan. Cobalah untuk mengimplementasikannya.

Algoritma :
SUBRUTIN bubble_sort(L,n)
Tahap  1
Ada_penukaran  BENAR
ULANG SELAMA tahap  n-1 DAN ada_penukaran
Ada_penukaran  SALAH
UNTUK j  0 S/D n-tahap-1
JIKA L[j]  L[j+1] MAKA
Ada penukaran  BENAR

// Lakukan penukaran
tmp  L[j]
L[j]  L[j+1]
L[j+1]  tmp
AKHIR – JIKA
AKHIR – UNTUK
Tahap  tahap + 1
AKHIR – ULANG
AKHIR – SUBRUTIN

Metode Pengurutan Seleksi
Pengurutan seleksi (selection sort) mempunyai mekanisme seperti berikut : Mula-mula suatu penunjuk (diberi nama posAwal), yang menunjuk ke lokasi awal pengurutan data, diatur agar berisi indeks pertama dalam larik. Selanjutnya dicari bilangan terkecil yang terletak antara posisi sesudah yang ditunjuk oleh petunjuk tersebut hingga elemen yang terakhir dalam larik. Lokasi bilangan ini ditunjuk oleh posMin. Lalu tukarkan nilai bilangan terkecil tersebut dengan nilai yang ditunjuk posAwal. Proses seperti itu diulang dari posAwal bernilai 0 hingga n-2, dengan n menyatakan jumlah elemen dalam larik.


Gambar Contoh Pengurutan Seleksi

Contoh Cobalah untuk mengimplementasikan subrutin pengurutan seleksi baik dalam bentuk algoritma dan program.

Algoritma :
SUBRUTIN selection_sort (L,n)
UNTUK posAwal = 0 S/D n-2
PosMin  posAwal
UNTUK j  posAwal + 1 S/D n-1
JIKA L [posMin]  L[j] MAKA
PosMin  j
AKHIR – JIKA
AKHIR – UNTUK
//Tukarkan
tmp  L[posAwal]
L[posAwal]  L[posMin]
AKHIR – UNTUK
AKHIR – SUBRUTIN

Pengurutan dengan Penyisipan
Pengurutan dengan penyisipan (insertion sort) adalah suatu metode yang melakukan pengurutan dengan cara menyisipkan data yang belum urut ke dalam bagian data yang telah diurutkan. Konsep ini biasa dilakukan pada permainan kartu. Ketika sebuah kartu baru didapatkan (hasil pembagian dari pengocokan kartu) kartu akan disisipkan oleh pemain pada posisi yang tepat sehingga penambahan kartu tersebut membuat semua kartu tetap terurutkan.



Gambar Mengurutkan kartu dengan metode penyisipan kartu 7 disisipkan sehingga susunan kartu yang sebelumnya sudah urut tetap urut

Contoh Bila L adalah larik dengan n elemen, mula-mula L[0] (elemen pertama) dianggap sebagai kumpulan data yang telah diurutkan, yang terdiri atas 1 buah data. Kemudian dilakukan penyisipan data dari L[1] sampai dengan L[n-1] ke dalam kumpulan data dari L[0] sampai dengan L[k-1] dengan 1 k  n. Dalam hal ini penyisipan dilakukan pada tempat yang tepat sehingga data pada L[0] sampai dengan L[k] menjadi urut.

Algoritma :
SUBRUTIN selection_sort (L,n)
UNTUK k  1 S/D n-1
X  L[k]
//Sisipkan x ke dalam L[0..k-1]
I  k – 1
Ketemu  SALAH
ULANG SEMUA I  0 DAN TIDAK ketemu
JIKA x  L[I] MAKA
L[i + 1]  L[i]
i  i – 1
SEBALIKNYA
Ketemu = BENAR
AKHIR – JIKA

L[i+1]  x
AKHIR – ULANG
AKHIR – UNTUK
AKHIR – SUBRUTIN

Pengurutan dengan Penyisipan Biner
Contoh Penyisipan pada insertion_sort dapat dibuat lebih efisien mengingat penyisipan dilakukan pada data yang telah urut. Pencarian dapat dilakukan dengan menggunakan metode pencarian biner yang telah dibahas pada bab 11. Setelah posisi untuk penyisipan ditemukan, semua elemen yang berada di sebelah kanan posisi tempat data akan disisipkan perlu digeser ke kanan.

Algoritma :
SUBRUTIN binary_insertion (L,n)
UNTUK k  1 S/D n-1
X  L[k]

//Sisipkan x ke dalam L[0..k-1]
kiri  0
kanan  k-1

ULANG SELAMA (kiri  kanan)
Tengah  (kiri + kanan) / 2 // Pembagian bulat
JIKA x  L[tengah] MAKA
Kanan  tengah – 1
SEBALIKNYA
Kiri  tengah + 1
AKHIR – JIKA
//Melakukan penggeseran
UNTUK j  k-1 S/D kiri
L[j+1]  L[j]
AKHIR – UNTUK
L[kiri]  x
AKHIR – ULANG
AKHIR – UNTUK
AKHIR – SUIBRUTIN

Metode Quick Sort
Quick sort adalah suatu metode pengurutan yang membandingkan suatu elemen (pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen yang lain yang lebih kecil daripada picot terletak disebelah kiri pivot sedangkan elemen yang besar dari pivot diletakkan di sebelah kanan pivot.
Sehingga sedemikian terbentuk dua sub list yaitu yang terletak disebelah kiri pivot dan senelah kanan pivot.
List yang disebelah kiri pivot juga diterapkan aturan seperti pivot,yaitu membandingkan elemen yang lainnya lagi, kalu lebih kecil di letakkan sebelah kiri,kalau lebih besar dilletakkan di sebelah kanan. Hal ini juga berlaku untuk list yang letakknya disebelah kanan.

Quick Sort adalah metode pengurutan data yang dikemukan pertama kali oleh C.AR Hoare pada tahun 1962. Metode ini menggunakan strategi “pecah-pecah” dengan mekanisme seperti berikut : Larik L[p..r] (dengan indeks terkecil adalah p dan indeks terbesar yaitu r) disusun ulang (dipartisi) menjadi dua buah larik A[p..q] dan A[q+1..r] sehingga setiap elemen dalam A[q+1..r]. Selanjutnya kedua larik tersebut diurutkan secara rekursif. Dengan sendirinya kombinasi kedua larik tersebut membentuk larik dengan data yang telah urut.

Contoh Implementasi quick sort dapat dilihat di bawah ini.

Algoritma :
SUBRUTIN quick_sort (L,p,r]
JIKA p  partisi (L,p,r)
Quick_sort (L,p,r)
Quick_sort (L,q+1,r)
AKHIR – JIKA
AKHIR – SUBRUTIN

Untuk mengurutkan isi keseluruhan larik L, diperlukan pemanggilan seperti berikut :

Quick_sort (L,0,jumlah_elemen(L)-1)

Subrutin partisi sendiri seperti berikut :
SUBRUTIN partisi (L,p,r)
x L[p]
i p
j r
ULANG SAMPAI BENAR
ULANG SELAMA L[j]  x
j  j – i
AKHIR – ULANG
ULANG SELAMA L[I]  x
i i +1
AKHIR-ULANG
JIKA ij MAKA
//Tukarkan L[i] dengan L[j]
tmp=L[i]
L[i]  L[j]
L[j] tmp
SEBALIKNYA
NILAI – BALIK j
AKHIR-JIKA
AKHIR-ULANG
AKHIR-SUBRUTIN

Pertama-tama xL[q] dipakai untuk membagi larik L[p..r] menjadi dua bagian (disebut pemartisian) dengan kondisi semua elemen bagian kiri selalu lebih kecil daripada nilai elemen pivot dan nilai semua elemen bagian kanan selalu lebih kecil daripada nilai elemen pivot. Pemartisian dilakukan dengan menggunakan varibel i dan j. Dalam hal ini i berupa petunjuk yang bergerak naik, sedangkan j adalah penunjuk bergerak turun. Variabel j bergeser turun secara terus-menerus sehingga L[j]  elemen pivot, sedangkan i digeser naik secara terus-menerus sampai memenuhui kondisi L[j]  elemen pivot. Proses pengulangan dilakukan sampai nilai i  j. Pada keadaan seperti ini nilai balik subrutin partisi berupa j. Gambar 11.12 memberikan contoh pemartisian larik menjadi dua bagian.


Gambar Ilustrasi pemartisian larik

Bila masing-masing bagian dikenakan operasi pemartisian, akhirnya akan diperoleh data yang urut.

Merge sort
Merge sort ialah metode pengurutan yang membandingkan elemen satu dengan elemenyang lain, apabila nilainya,lebih kecil maka datanya ditampung di elemen yang lain lagi.
Elemen pertama array dibandingkan dengan elemen pertama array B.jika elemen unsur arrayA lebih kecil dibandingkan elemen pertama unsur array B,isi dari array dipindahkam ke array c yang baru. Kemudian indeks array a kemudian bertambah dan tidak perlu dibandingkan lagi. Jika,isidari arrayB lebih kecil dari arrayA, maka isi dari arrayB dipindahkan ke arrayC dan array B bertambah.