 Tujuan

› Pengurutan data dalam struktur data sangat penting

terutama untuk data yang bertipe data numerik ataupun
karakter.
› Pengurutan dapat dilakukan secara ascending (urut naik)
dan descending (urut turun)
› Pengurutan (Sorting) adalah proses pengurutan data yang
sebelumnya disusun secara acak sehingga tersusun secara
teratur menurut aturan tertentu
Contoh:
› Data Acak : 5 6 8 1 3 2 5 10
› Ascending : 1 2 3 5 6 8 10 25
› Descending : 25 10 8 6 5 3 2 1
 Deklarasikan secara global:
int data[100];
int n; //untuk jumlah data

 Langkah menukar isi dua elemen array yang

berindex i dengan isi array berindex j . :
int tmp;
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
 Bubble Sort
 Insertion Sort
 Selection Sort
 Quick Sort
 Metode sorting termudah
 Diberi nama “Bubble” karena proses pengurutan secara berangsur-
angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung
yang keluar dari sebuah gelas bersoda.
 Bubble Sort mengurutkan data dengan cara membandingkan elemen
sekarang dengan elemen berikutnya.
 Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua
elemen tersebut ditukar, jika pengurutan ascending.
 Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua
elemen tersebut ditukar, jika pengurutan descending
 Algoritma ini seolah-olah menggeser satu per satu
elemen dari kanan ke kiri atau kiri ke kanan, tergantung
jenis pengurutannya.
 Ketika satu tahap proses telah selesai, maka bubble sort
akan mengulangi proses, demikian seterusnya.
 Kapan berhentinya? Bubble sort berhenti jika seluruh
array telah diperiksa dan tidak ada pertukaran lagi yang
bisa dilakukan, serta tercapai perurutan yang telah
diinginkan.
  Proses 1
1.1- 22 10 15 3 8 2 bandingkan

1.2- 22 10 15 3 2 8 tukarkan

1.3- 22 10 15 2 3 8
1.4- 22 10 2 15 3 8
1.5- 22 2 10 15 3 8
1.6- 2 22 10 15 3 8

-Pengecekan dilakukan dari data yang paling akhir.

-Data terakhir dibandingkan dengan data didepannya, jika data didepannya
lebih besar maka dilakukan penukaran.
  Proses 2 Tidak ada penukaran
karena 3 < 8
2.1- 2 22 10 15 3 8
2.2- 2 22 10 15 3 8
2.3- 2 22 10 3 15 8
2.4- 2 22 3 10 15 8 Pengurutan berhenti karena dari
Proses 1 ini telah didapatkan uruta
2.5- 2 3 22 10 15 8 Data dengan data pertama terkeci

-Pengecekan 2 3 22 10 15 8
dilakukan kembali dari data yang paling akhir.
-Data terakhir dibandingkan dengan data didepannya, jika data didepannya
lebih besar maka dilakukan penukaran.
 Proses 3
2 3 22 10 15 8
2 3 22 10 8 15
2 3 22 8 10 15 Pengurutan berhenti karena dari
Proses ini telah didapatkan urutan
2 3 8 22 10 15 Data dengan data kedua terkecil
 Proses 4
2 3 8 22 10 15
2 3 8 22 10 15
2 3 8 10 22 15 Pengurutan berhenti karena dari
Proses ini telah didapatkan urutan
2 3 8 10 22 15 Data dengan data ketiga terkecil
 Proses 5
2 3 8 10 22 15
2 3 8 10 15 22 Pengurutan selesai
void bubble_sort()
{
for(int i=0;i<n;i++)
{ Ini adalah langkah untuk ascending
for(int j=n-1;j>=i;j--)
Jika descending maka tanda ‘< ‘diubah
{
menjadi ‘>’
if(data[j]<data[j-1]) {
int tmp;
tmp = data[j];
data[j] = data[j-1];
data[j-1] = tmp; }//tukar(j,j-1);
}
}
}
 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.
 Proses 1
0 1 2 3 4 5
22 10 15 3 8 2
10 22 15 3 8 2

 Proses 2
0 1 2 3 4 5
10 22 15 3 8 2
10 15 22 3 8 2
 Proses 3
0 1 2 3 4 5
10 15 22 3 8 2
10 15 3 22 8 2
10 3 15 22 8 2
3 10 15 22 8 2
 Proses 4
0 1 2 3 4 5
3 10 15 22 8 2
3 10 15 8 22 2
3 10 8 15 22 2
3 8 10 15 22 2
 Proses 5
0 1 2 3 4 5
3 8 10 15 22 2
3 8 10 15 2 22
3 8 10 2 15 22
3 8 2 10 15 22
3 2 8 10 15 22
2 3 8 10 15 22
void insertion_sort()
{
for(int i=1;i<n;i++)
{
int j = i -1;
while(data[j]>data[j+1] && j>=0)
{
int tmp; //tukar(data[j+1],data[j]);
tmp = data[j+1];
data[j+1] = data[j];
data[j] = tmp;
j--;
}
}
}
 Tabel Perbandingan Kecepatan Metode Pengurutan Data
(Untuk jumlah data 10.000 dengan menggunakan processor 450MHz)

Waktu (detik)
Metode Data Acak Data Ascending Data Descending

Bubble Sort 11,2 13,2 19,77

Insertion Sort 10,9 10,9 12,25

Selection Sort 13,2 13,2 19,77

 Metode selection sort merupakan perbaikan dari metode bubble
sort dengan mengurangi jumlah perbandingan .
 Selection sort merupakan metode pengurutan yang mencari
nilai data terbesar atau terkecil dan kemudian menempatkannya
pada posisi yang sebenarnya, dimulai dari data diposisi 0
hingga data diposisi N-1.
 Sedangkan metode insertion sort adalah metode pengurutan
yang biasa dipakai oleh pemain kartu dalam mengurutkan
kartunya, yaitu menyisipkan kartu dengan nilai yang lebih kecil
ke posisi sebelum kartu pembandingnya
 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.
 Teknik pengurutan dengan cara pemilihan elemen atau proses kerja
dengan memilih elemen data terkecil untuk kemudian dibandingkan
dan ditukarkan dengan elemen pada awal data, dan seterusnya
sampai dengan seluruh elemen sehingga menghasilkan pola data
yang telah di sort
 Kelebihan dan kekurangan Selection Sort:
􀁻 Kompleksitas selection sort relatif lebih kecil.
􀁻 Mudah menggabungkannya kembali, tetapi sulit membagi
masalah.
􀁻 Membutuhkan method tambahan.
 Kondisi awal:
􀁻 Unsorted list = data
􀁻 Sorted list = kosong
􀁹Ambil yang terbaik (select) dari unsorted list, tambahka di belakang
sorted list.
 Lakukan terus sampai unsorted list habis.
 Qick sort banyak digunakan utk proses sorting,karena:
􀁻 merupakan proses sorting yang umum digunakan
􀁻 mudah untuk diimplementasikan
􀁻 Prosesnya sangat cepat
 Aturan Quick Sort:
􀁻 Select : Pertama kita pilih elemen yang ditengah sebagai pivot,
misalkan X.
􀁻 Partition : kemudian semua elemen tersebut disusun dengan
menempatkanX pada posisi j sedemikian rupa sehingga elemen
disebelah kiri1 lebih < X dan elemen sebelah kanan > X.
􀁻 Rekursif : Kemudian proses diulang untuk bagian kiri dan kanan
elemenX dengan cara yg sama dengan langkah 1 sampai kondisi
terurut
 Adalah binary tree dengan menggunakan kunci, dimana mempunyai
aturan-aturan sebagai berikut :
 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.
 heap dlm kondisi terurut apabila left child < parent dan right child >
parent
 penambahan kunci diletakkan pada posisi terakhir dari level dan
disebelah kanan child yg terakhir, kemudian diurutkan dengan cara
upheap
 Bila menghapus heap dgn mengambil kunci pada parent di level 1
kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali
metode downheap
 Metode Upheap:
1. Bandingkan kunci terakhir dengan parentnya apabila
parent < kunci maka lakukan pertukaran.
2. Ulangi langkah g g 1 dengan membandingkan dengan
parent selanjutnya sampai posisi parent di level 1 selesai
dibandingkan

 Metode Downheap:
1. bandingkan parent dengan leftchild dan rightchild
apabila parent < leftchild atau rightchild maka lakukan
pertukaran.
2. ulangi langkah 1 dengan membandingkan dengan
leftchild dan rightchild pada posisi level dibawahnya
sampai posisi di level terakhir selesai dibandingkan.