Sorting

Sorting (Pengurutan Data)

• Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.
• Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
• Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

Contoh:

• Data Acak : 5 6 8 1 3 25 10
• Ascending : 1 3 5 6 8 10 25
• Descending : 25 10 8 6 5 3 1

Metode Pengurutan Data

1. Pengurutan berdasarkan perbandingan (comparison-based sorting)

• Bubble sort,exchange sort

2. Pengurutan berdasrkan priorita prioritas (priority queue sorting method)

• Selection sort, heap sort (menggunakan tree)

3. Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

• Insertion sort, tree sort

4. Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

• Quick sort, merge sort

5. Pengurutan berkurang menurun (diminishing increment sort method)

• Shell sort (pengembangan insertion)

1. Bubble Sort

• Bubble sort adalah salah satu pengurutan metode exchanging yang bersifat langsung dan termasuk jenis pengurutan yang paling sederhana. Nama bubble sort ini berasal dari sifat elemen terbesar yang selalu naik ke atas (ke akhir dari list) seperti bubble
• Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
• Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.
• Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
• Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya, asc atau desc.
• Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya, asc atau desc
• Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.
• Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Ide dari bubble sort adalah sebagai berikut :

1. Algoritma dimulai dari elemen paling awal.
2. 2 buah elemen pertama dari list dibandingkan.
3. Jika elemen pertama lebih besar dari elemen kedua,dilakukan pertukaran
4. Langkah 2 dan 3 dilakukan lagi terhadap elemen kedua dan ketiga, seterusnya sampai ke ujung elemen
5. Bila sudah sampai ke ujung dilakukan lagi ke awal sampai tidak ada terjadi lagi pertukaran elemen.
6. Bila tidak ada pertukaran elemen lagi, maka list elemen sudah terut
   

Berikut adalah contoh psudocode untuk bubble sort dengan urutan membesar :

procedure bubbleSort( A : list of
integer )
do
swapped := false
for i = 1 to length( A ) - 1 do:
if A[ i ] > A[ i + 1 ] then
tukar ( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
end procedure

Di dalam loop dilakukan pengecekan terhadap tiap elemen mulai elemen pertama dan kedua, elemen kedua dan ketiga, dan seterusnya sampai elemen sebelum terakhir. Bila masih terjadi pertukaran (swapped = true) dilakukan pengecekan lagi sampai tidak terjadi pertukaran (swapped = false) yang berarti semua elemen dalam list tersebut sudah terurut membesar.

Contoh penerapannya :

8 6 3 7 9 1 belum terurut
6 3 7 8 1 9 setelah loop pertama
3 6 7 1 8 9 setelah loop kedua
3 6 1 7 8 9 seteleh loop ketiga
3 1 6 7 8 9 seteleh loop keempat
1 3 6 7 8 9 setelah loop kelima (terurut)

Pada algoritma ini, kasus terbaik terjadi saat semua elemen sudah terurut (kompleksitas = O(n)) di mana hanya terjadi pengecekan pada setiap elemen, sehingga penelusuran hanya dilakukan satu kali saja. Keuntungan lain dari algoritma ini adalah dapat dijalankan dengan cukup cepat dan efisien untuk mengurutkan list yang urutannya sudah hampir benar. Selain kasus terbaik tersebut, komleksitas untuk algoritma ini adalah O(n²). Karenanya algoritma ini termasuk sangat tidak efisien untuk dilakukan, apalagi jika pengurutan dilakukan terhadap elemen yang banyak jumlahnya. Biasanya bubble sort digunakan untuk mengenalkan konsep dari sorting algoritma pada pendidikan komputer karena idenya yang cukup sederhana. Namun owen Astrachan,seorang peneliti, mengatakan bahwa sebaiknya algoritma bubble sort ini tidak diajarkan lagi di pendidikan ilmu komputer.

Posisi setiap elemen pada bubble sort akan sangat menentukan performa saat eksekusi. Bila elemen yang terbesar disimpan di awal, maka tidak akan menimbulkan persoalan sebab elemen tersebut secara cepat akan ditukar langsung ke elemen paling terakhir.Sebaliknya jika elemen terkecil disimpan di bagian paling akhir elemen, maka akan mengakibatkan elemen tersebut akan bergerak sebanyak hanya satu pergeseran setiap masuk ke loop. Ini berarti harus dilakukan pengecekan sebanyak n kali dalam satu loop dan loop akan dijalankan sebanyak n kali juga. Kedua jenis ini biasa disebut rabbit dan turtle. Untuk menghilangkan masalah rabbit dan turtle ini, algoritma ini dikembangkan dengan menciptakan algoritma cocktail sort dan comb sort. Cocktail sort cukup baik untuk mengatasi permasalahan ini namun untuk kasus terburuk kompleksitasnya sama dengan bubble sort yaitu O(n²). Comb sort cukup baik untuk mempercepat turtle pada elemen list dan juga memiliki kompleksitas yang cukup baik, yaitu n log n, namun comb sort pun memiliki kelemahan, yaitu tidak stabil pada saat pengurutan.

Kelemahan yang lain adalah bubble sort berinteraksi dengan buruk pada computer modern saat ini. Penulisanya menghabiskan tempat dua kali lebih banyak dari insertion sort dan juga sering melakukan cache misses dan lebih banyak terjadi branch missprediction. Penelitian yang dilakukan oleh Astrachan pada pengurutan string di java juga membuktikan bahwa bubble sort lima kali lebih lambat dari insertion sort. Karenanya pada implementasinya bubble sort jarang digunakan, meskipun banyak juga algoritma lain yang dikembankan dari bubble sort ini.

Dari analisis tersebut, algoritma ini sebaiknya tidak diimplementasikan sebab termasuk tidak efisien penggunaannya, hanya baik digunakan untuk mengurutkan list yang sudah hampir terurut. Selain itu pengurutan jenis ini sangat tidak efisien dan memakan banyak waktu saat dieksekusi. Namun karena algoritma ini termasuk sederhana membuatnya cukup mudah untuk diajarkan sebagai dasar dari algoritma pengurutan.

Prosedur Bubble Sort :

Versi 1

void bubble_sort (int data[])
{
for(int i=1;i=i;j--)
{
if(data[j]


Versi 2

void bubblesort2 (int data[])

{

for(i=1;i<6;i++) j="0;j<6-1;j++)">data[j+]))

tukar(&data[j], &data[j+1]); //descending

}

}

}

2. Exchange Sort

• Sangat mirip dengan Bubble Sort
• Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort
• Pebedaan : dalam hal bagaimana membandingkan antar elemen-elemen
• Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu.Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
• Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Contoh fungsi exchange sort:


//Exchange Sort void exchange (int a[], int n)
{ int i,j; for (i=0;i<=n-1;i++) { for (j=(i+1);j if(a[i]>a[j])
tukar (a,i,j);
}
}

//Exchange Sort Function for Descending Order

void ExchangeSort(apvector &num)
{
int i, j;
int temp; // holding variable
int numLength = num.length( );
for (i=0; i< (numLength -1); i++) // element to be compared { for(j = (i+1); j < temp=" num[i];">

3. Insertion Sort

• Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
• Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
• Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang

Algoritma insertion sort adalah sebuah algoritma sederhana yang cukup efisien untuk mengurutkanbsebuah list yang hampir terurut. Algorima ini juga biasa digunakan sebagai bagian dari algoritma yang lebih canggih. Cara kerja algoritma ini adalah dengan mengambil elemen satu-per-satu dan memasukkannya di posisi yang benar seperti namanya. Pada array, list yang baru dan elemen sisanya dapat berbagi tempat di array, meskipun cukup rumit. Untuk menghemat memori, implementasinya menggunakan pengurutan di tempat yang membandingkan elemen saat
itu dengan elemen sebelumnya yang sudah diurut, lalu menukarnya terus sampai posisinya tepat. Hal ini terus dilakukan sampai tidak ada elemen tersisa di input. Seperti sudah dibahas di bagian pendahuluan, salah satu implementasinya pada kehidupan sehari-hari adalah saat kita mengurutkan kartu remi. Kita ambil kartu satu-per-satu lalu membandingkan dengan kartu sebelumnya untuk mencari posisi yang tepat.

Variasi pada umunya yang dilakukan terhadap array pada insertion sort adalah sebagai berikut :

1. Elemen awal di masukkan sembarang, lalu elemen berikutnya dimasukkan di bagian paling akhir.
2. Elemen tersebut dibandingkan dengan elemen ke (x-1). Bila belum terurut posisi elemen sebelumnya digeser sekali ke kanan terus sampai elemen yang sedang diproses menemukan posisi yang tepat atau sampai elemen pertama.
3. Setiap pergeseran akan mengganti nilai elemen berikutnya, namun hal ini tidak menjadi persoalan sebab elemen berikutnya sudah diproses lebih dahulu.

Ilustrasinya adalah sebagai berikut :

Berikut contoh prosedur code untuk insertion sort dengan urutan membesar:

procedure insertionSort(A : array of integer)
for i = 1 to length[A]-1 do
value = A[i]
j = i-1
while j >= 0 and A[j] >
value do
A[j + 1] = A[j]
j = j-1
end while
A[j+1] = value
end for
end procedure

Pertukaran yang berulang terjadi di loop while yang akan berhenti saat elemen sebelumnya sudah lebih kecil. Loop for berguna untuk melakukan insert elemen selanjutnya. Kasus terbaik pada algoritma ini adalah saat semua elemen sudah terurut. Pengecekan tiap elemen hanya dilakukan 1 kali sehingga hanya terjadi n kali loop iterate. Sedangkan kasus terburuk adalah saat list ada dalam kondisi terbalik yang membutuhkan n buah pertukaran terhadap n buah elemen, sehingga kompleksitasnya sama dengan O(n²). kompleksitas ini sama dengan kompleksitas rata-ratanya. Ini berarti untuk menghitung jumlah elemen yang sangat besar algoritma ini kurang efisien untuk digunakan. Namun untuk melakukan sorting terhadap elemen yang sedikit, algoritma ini termasuk algoritma tercepat eksekusinya. Hal ini disebabkan loop dalamnya sangat cepat.
Bila dibandingkan dengan bubble sort, keduanya memiliki kompleksitas yang sama untuk kasus terburuk,namun menurut Astrachan keduanya sangat berbeda dalam jumlah pertukaran yang diperlukan. Karenanya sekarang ini cukup banyak text book yang merekomendasikan insertion sort disbanding bubble sort.

Insertion sort ini memiliki beberapa kelebihan :

1. Implementasi yang sederhana
2. Paling efisien untuk data berukuran kecil
3. Merupakan online algorithmic, yang berarti bisa langsung melakukan sort setiap ada data baru
4. Proses di tempat (memerlukan O(1) memori tambahan)
5. Stabil.

Pada tahun 2004 Bender, Farach-Colton, and Mosteiro menemukan pengembangan baru dari algoritma ini, disebut library sort atau gapped insertion sort yang menggunakan beberapa gap kosong di sepanjang array. Dengan algoritma ini, pergeseran elemen dilakukan sampai gap tersebut dicapai. Algoritma ini cukup baik dengan kompleksitas O(n log n).

Prosedur Untuk Insertion Sort :

void insertion _sort(int data[])
{
int temp; for(int i=1;i
{
temp =data[i];
j = i - 1;
while(data[j]>temp && j>=0))
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}

4. Merge Sort

Merge Sort ini memanfaatkan fungsi merge yang mampu mengurutkan 2 buah list yang sudah terurut. List yang akan diproses dibagi-bagi dulu menjadi list yang lebih kecil. Setelah itu digabung kembali dari dua list menjadi satu, lalu digabung kembali terus sampai menjadi 2 list besar yang setelah dimerge akan menghasilkan list yang sudah terurut. Sorting jenis ini sangat baik untuk memproses jumlah elemen yang sangat banyak.

Ilustrasinya adalah sebagai berikut (implementasi dari merge sort terhadap 7 buah nilai):

Konsep dari merge sort sendiri adalah sebagai berikut :

1. Bagi list besar menjadi setengahnya
2. Lakukan hal ini secara rekursif sampai diperoleh list dengan satu elemen saja
3. List tersebut digabung lagi menjadi sebuah list besar yang sudah terurut.

Berikut ini adalah pseudocode untuk merge sort :

function mergesort(m) var list kiri, kanan, hasil if length(m) = 1 return m else var tengah = length(m) / 2 for x = m to tengah add x to kiri end for for x = m after tengah add x to kanan end for kiri = mergesort(kiri) kanan = mergesort(kanan) hasil = merge(kiri, kanan) end if return hasil

Untuk fungsi merge sendiri, ini merupakan salah satu contoh pseudocode :

function merge(kiri,kanan)
var list hasil
while length(kiri) > 0 and
length(kanan) > 0
if first(kiri) =
first(kanan)
append first(kiri) to
hasil
kiri = rest(kiri)
else
append first(kanan) to
hasil
kanan = rest(kanan)
end if
end while
if length(kiri) > 0
append rest(kiri) to hasil
end if
if length(kanan) > 0
append rest(kanan) to hasil
end if
return hasil

Merge sort memiliki kasus terburuk dan kasus rata rata. Kasus terburuk adalah saat tiap 2 elemen dibandingkan selalu dilakukan pertukaran. Bila waktu yang diperlukan untuk melakukan merge sort adalah T(n) maka untuk saat rekursif waktu yang dihabiskan adalah T(n) = 2T(n/2) + n. T (n/2) adalah waktu yang diperlukan untuk merge setengah dari ukuran list, dan ditambah n sebagai langkah dari penggabungan list. Kompleksitas waktu terburuk dan rata-rata dari merge sort adalah O(n log n), sama dengan kompleksitas terbaik dari quick sort. Untuk mengurutkan data yang sangat besar, jumlah perbandingan yang diharapkan mendekati nilai a·n di mana

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. Merge sort ini merupakan algoritma terbaik untuk mengurutkan linked list, sebab hanya memerlukan memori tambahan sebesar T(1).

Berdasarkan analisis tersebut, merge sort bisa dibilang sebagai salah satu algoritma terbaik terutama untuk mengurutkan data yang jumlahnya sangat banyak. Untuk data yang sedikit, algoritma ini sebaiknya tidak digunakan karena ada beberapa algoritma lain yang bisa bekerja lebih cepat dari merge sort.

5. Quick Sort

Quick sort merupakan divide and conquer algorithm. Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) lalu menyimpan semua elemen yang lebih kecil di sebelah kirinya dan semua elemen yang lebih besar di sebelah kanannya. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut. Algoritma ini termasuk algoritma yang cukup baik dan cepat. Hal penting dalam algoritma ini adalah pemilihan nilai tengah yang baik sehingga tidak memperlambat proses sorting secara keseluruhan.

Ide dari algoritma ini adalah sebagai berikut :

1. Pilih satu elemen secara acak
2. Pindahka semua elemen yang lebih kecil ke sebelah elemen tersebut dan semua elemen yang lebih besar ke sebelah kanannya. Elemen yang nilainya sama bisa disimpan disalah satunya. Ini disebut operasi partisi
3. Lakukan sort secara rekursif terhadap sublist sebelah kiri dan kanannya.

Berikut adalah psudocode untuk quick sort :

function quicksort(array)
var list kecil,sama,besar
if length(array) = 1
return array
end if
pilih sebuah nilai, disebut pivot
for each x in array
if x <>
to kecil end if
if x = pivot then append x
to sama end if
if x > pivot then append x
to besar end if
end for return
concatenate(quicksort(kecil), sama ,
quicksort(besar))

Setiap elemen yang akan disort selalu diperlakukan secara sama di sini, diambil salah satu elemen, dibagi menjadi 3 list, lalu ketiga list tersebut disort dan digabung kembali. Contoh kode di atas menggunakan 3 buah list, yaitu yang lebih besar, sama dan lebih kecil nilainya dari pivot. Untuk membuat lebih efisien, bisa digunakan 2 buah list dengan mengeliminasi yang nilainya sama (bisa digabung ke salah satu dari 2 list yang lain).

Kasus terburuk dari algoritma ini adalah saat dibagi menjadi 2 list, satu list hanya terdiri dari 1 elemen dan yang lain terdiri dari n-2 elemen. Untuk kasus terburuk dan kasus rata-rata, algoritma ini memiliki kompleksitas sebesar O(n log n). Jumlah rata-rata perbandingan untuk quick sort berdasarkan permutasinya dengan asumsi bahwa nilai pivot diambil secara random adalah :

Lalu bagaimana cara menentukan pivot sendiri? Kasus terbaik yang diharapkan diilustrasikan sebagai berikut :
Bagi sebuah list menjadi 4 buah. Lalu pilih 2 buah lists esdemikian rupa sehingga setiap elemennya lebih besar dari 25 % elemen terkecil dan lebih kecil dari 25% elemen terbesar. Bila nilai pivot yang dipilih secara konstan terambil dari nilai ini maka hanya diperlukan pembagian list sebanyak 2log2n kali.

Quick sort adalah pengembangan dari binary tree sort, yang lebih menghemat ruang. Cara perbandingannyamirip, hanya pengurutannya berbeda. Bila dibandingkan dengan merge sort, quick sort memiliki keuntungan di kompleksitas waktu sebesar T(log n), dibanding dengan merge sort sebesar T(n). namun quick sort tidak mampu membandingkan linked list sebaik merge sort, karena ada kemungkinan pemilihan pivot yang buruk. Selain itu pada linked list merge sort memerlukan ruang yang lebih sedikit.

Berdasarkan analisis tersebut quick sort termasuk algoritma sorting yang cukup baik, namun kita pun harus bisa memilih nilai pivot yang baik agar penggunaannya bisa optimal.

6. Selection Sort

• Merupakan kombinasi antara sorting dan searching
• Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array
• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).
• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Prosedur selection sort :

void selection_sort ( int data[] )
{
for (int i=0;i
{
pos = i;
for (int j=i+1;j
{
if (data[j] < pos =" j;//ascending">