BAB 5 SORTING(PENGURUTAN)

1. Pengertian SortingPengurutan data atau sorting merupakan hal yang sangat

penting dalam kehidupan nyata untuk melakukan pengolahan data. Pengurutan bisa dilakukan dengan urutan menaik (ascending) atau dengan urutan menurun (descending). Misalnya, diketahui data sebagai berikut :

6 1 8 4 9 2 0 7 5 3Jika diurutkan secara ascending, maka hasilnya adalah :

Jika diurutkan secara descending, maka hasilnya adalah :9 8 7 6 5 4 3 2 1 0

Jika yang diurutkan adalah sebuah rekaman (record) yang terdiri dari beberapa jenis data maka pengurutan biasanya dilakukan berdasarkan salah sat jenis data yang disimpan, misalnya jika sebuah rekaman (record) data mata kuliah mahasiswa, dapat diurutkan berdasarkan nomor pokok mahasiswa.Pengurutan terbagi menjadi dua kelompok : Pengurutan Internal

Adalah pengurutan terhadap sekumpulan data yang disimpan didalam memori utama komputer. Umumnya struktur data yang dipakai adalah larik, sehingga pengurutan internal disebut juga pengurutan larik.

Pengurutan EksternalAdalah pengurutan data yang disimpan di alam memori sekunder, biasanya data bervolume besar sehingga tidak mampu dimuat semuanya didalam memori komputer, disebut juga pengurutan arsif (file), karena struktur eksternal yang dipakai adalah arsip.

Beberapa metode yang umum digunakan diantaranya adalah :1. Bubble sort2. Gravitation Sort3. Selection Sort4. Insertion Sort5. Swap-Insertion Sort

2. Bubble SortBubble sort adalah salah satu pengurutan exchanging yang

bersifat langsung dan termasuk jenis pengurutan yang paling sederhana. Nama bubble sort sendiri berasal dari sifat nilai elemen terbesar yang selalu naik ( ke akhir dari list) seperti gelembung udara bubble.

Ide pengurutan bubble sort adalah sebagai berikut :

32

0 1 2 3 4 5 6 7 8 9

Dimulai dari elemen terakhir (paling kanan) kemudian dibandingkan dengan elemen depannya (sebelah kirinya).

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.

pseudocode bubble sort untuk pengurutan ascending:Data array of int (1..10);int n : //jumlah anggota array data ;int temp, i, tukar ;do

tukar 0;for I 0 to i n-1 do

If (data[i] > data [i+1] thenTemp data [i];Data [i] data [i+1];Data [i+1] temp;Tukar 1;

Endif;Endfor;

While (tukar > 0);

Pada setiap pengulangan (loop) selalu dilakukan pengecekan terhadap tiap elemen, mulai elemen pertama dan kedua, elemen kedua dan ketiga, dan seterusnya sampai elemen sebelum terakhir. Bila masih terjadi pertukaran (tukar=1) dilakukan pengecekan lagi sampai tidak terjadi pertukaran (tukar=0) yang berarti semua elemen dalam list tersebut sudah terurut secara ascending (tukar>0).Contoh : Misalkan elemen-elemen yang akan diurutkan disimpan dalam array, yaitu A=[6, 2, 9, 3, 7, 4]. Urutkan secara ascendingLangkah 1

6 2 9 3 7 4 : 4 < 7

Tukar

6 2 9 3 4 7 : 4 > 3

Tetap

6 2 9 3 4 7 : 3 < 9

Tukar

6 2 3 9 4 7 : 3 > 2

Tetap

6 2 3 9 4 7 :2 < 6

Tukar

Hasil 2 6 3 9 4 7

Langkah 2

2 6 3 9 4 7 : 7 > 4

Tetap

2 6 3 9 4 7 : 4 < 9

Tukar

2 6 3 4 9 7 : 4 Tetap

33

> 32 6 3 4 9 7 : 3

< 6Tukar

Hasil 2 3 6 4 9 7

Langkah 3

2 3 6 4 9 7 : 7 < 9

Tukar

2 3 6 4 7 9 : 7 > 4

Tetap

2 3 6 4 7 9 : 4 < 6

Tukar

Hasil 2 3 4 6 7 9

Langkah 4

2 3 4 6 7 9 : 9 > 7

Tetap

2 3 4 6 7 9 : 7 > 6

Tetap

Hasil 2 3 4 6 7 9

Langkah 5

2 3 4 6 7 9 : 9 > 7

Tetap

Hasil 2 3 4 6 7 9

3. Gravitation Sort (Pengurutan Gravitasi)Mirip dengan bubble sort tetapi dimulai dari elemen pertama

( paling kiri ) dan dibandingkan dengan elemen dibelakangnya (sebelah kanannya). Sehingga pada akhir langkah pertama diperoleh elemen terakhir sudah dalam posisi terurut, demikian seterusnya.

procedure UrutGravitasi(input/output L: Larik; input N : integer)DeklarasiI : integer {pencacah untuk jumlah langkah}K : integer {pencacah untuk pemberatan pada setiap langkah}U : integer {indeks ujung kiri bagian larik yang telah terurut}Temp : integer {peubah bantu untuk pertukaran}AlgoritmaU ← Nfor I ← 1 to N-1 do

for K ← 1 to U-1 doif L[K] > L[K+1] then {pertukarkan L[K] dengan L[K+1]}

Temp ← L[K]L[K] ← L[K-1]L[K-1] ← Temp

endifendfor{ larik L[U..N] terurut, larik L[1..U-1] belum terurut }U ← U - 1

endfor

34

Contoh : urutkan secara naik elemen-elemen array A = [6, 2, 9, 3, 4, 7]Langkah 1

6 2 9 3 4 7 : 6 > 2 Tukar

2 6 9 3 4 7 : 6 < 9 Tetap2 6 9 3 4 7 : 9 > 3 Tukar2 6 3 9 4 7 : 9 > 4 Tukar2 6 3 4 9 7 : 9 > 7 Tukar

Hasil 2 6 3 4 7 9

Langkah 2

2 6 3 4 7 9 : 2 < 6 Tetap

2 6 3 4 7 9 : 6 > 3 Tukar2 3 6 4 7 9 : 6 > 4 Tukar2 3 4 6 7 9 : 6 < 7 Tetap

Hasil 2 3 4 6 7 9 :

Langkah 3

2 3 4 6 7 9 : 2 < 3 Tetap

2 3 4 6 7 9 : 3 < 4 Tetap2 3 4 6 7 9 : 4 < 6 Tetap

Hasil 2 3 4 6 7 9

Langkah 4

2 3 4 6 7 9 : 2 < 3 Tetap

2 3 4 6 7 9 : 3 < 4 TetapHasil 2 3 4 6 7 9

Langkah 5

2 3 4 6 7 9 : 2 < 3 Tetap

Hasil 2 3 4 6 7 9

4. Selection Sort (Pengurutan Seleksi)Pemilihan elemen – elemen ekstrim, paling besar (maksimum)

atau paling kecil (minimum), kemudian ditempatkan pada posisi yang sesuai. Langkah tersebut diulangi untuk elemen-elemen sisanya, sampai semua elemen terurut. Terdapat 4 variasi dalam pengurutan seleksi, yaitu :a. Pengurutan naik : pemilihan maksimun, ditempatkan dibagian

akhir.b. Pengurutan naik : pemilihan minimum, ditempatkan dibagian awal.c. Pengurutan turun : pemilihan maksimum, ditempatkan dibagian

awal.d. Pengrutan turun : pemilihan minimum, ditempatkan dibagian

akhir.

Algoritma pengurutan seleksi :For i 1 to n -1 do

Min j i;Min x A[i];

For j i + 1 to n doIf A[j] < min x thenMin j jMin x A[j]

35

A[min j] A[i]A[i] min x

Contoh : urutkan naik elemen-elemen array A = [6, 9, 7, 3, 2, 4] dengan pemilihan maksimum.Langkah

1

6 9 7 3 2 4 Tukar Elemen ke-2 dg elemen

ke-6

Hasil 6 4 7 3 2 9

Langkah

2

6 4 7 3 2 Elemen sisa belum terurut

6 4 7 3 2 Tukar elemen ke-3 dg elemen

ke-5

Hasil 6 4 2 3 7 9

Langkah

3

6 4 2 3 Elemen sisa belum terurut

6 4 2 3 Tukar elemen ke-1 dg elemen

ke-4

Hasil 3 4 2 6 7 9

Langkah

4

3 4 2 Elemen sisa belum terurut

3 4 2 Tukar elemen ke-2 dg elemen

ke-3

Hasil 3 2 4 6 7 9

Langkah

5

3 2 Sisa elemen belum terurut

3 2 Tukar elemen ke-1 dg elemen

ke-2

Hasil 2 3 4 6 7 9

5. Insertion Sort (pengurutan sisip) Mirip dengan cara orang mengurutkan kartu, selembar demi

selembar kartu diambil dan disisipkan ( insert ) ketempat yang seharusnya.

Pengurutan dimulai dari data yang ke-2 sampai dengan data yang terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan di posisi seharusnya.

Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

36

Algoritma pengurutan sisip: ascendingFor i 2 to n do

Temp A[i];J i - 1;While (temp < A[j] and (j>0) do

J j – 1End whileFor k i downt j+1 do

A[k] A[k-1}EndforA[j+1] temp;

endfor

Contoh : urutkan naik elemen-elemen array A = [22, 10, 15, 3, 8, 2 ]22 10 15 3 8 2 10 22 15 3 8 2 10 15 22 3 8 2

3 10 15 22 8 2 3 8 10 15 22 2 2 3 8 10 15

22

Hasil

6. SWAP-Insertion sort (Pengurutan sisip-tukar)Mirip dengan pengurutan sisip, bedanya jika suatu elemen tidak

dalam kondisi terurut maka langsng dilakukan pertukaran. Jadi tidak perlu proses pergeseran.Langkah untuk pengurutan naik :a. Anggap elemen pertama sudah dalam kondisi terurut.b. Mulai dari elemen kedua sampai elemen terakhir lakukan :

Simpan (assign) variable indeksnya ke variable lain. Bandingkan elemen tersebut dengan elemen di depannya :

- Jika lebih kecil maka tukarkan, kemudian bandingkan lagi dengan elemen depannya lagi.

- Jika lebih besar maka berhenti.c. Ulangi untuk elemen ketiga dan seterusnya sampai elemen

terurut.Contoh : ururtkan naik elemen-elemen array A = [6, 2 , 9, 3, 4, 7]

Langkah

1

6 2 9 3 4 7 : 2 < 6 Tukar

Hasil 2 6 9 3 4 7

Langkah

2

2 6 9 3 4 7 : 9 > 6 Tetap

37

Hasil 2 6 9 3 4 7

Langkah

3

2 6 9 3 4 7 :3 < 9 Tukar

2 6 3 9 4 7 : 3 < 6 Tukar

Hasil 2 3 6 9 4 7

Langkah

4

2 3 6 9 4 7 : 4 < 9 Tukar

2 3 6 4 9 7 : 4 < 6 Tukar

Hasil 2 3 4 6 9 7

Langkah

5

2 3 4 6 9 7 : 7 < 9 Tukar

Hasil 2 3 4 6 7 9

7. Penggabungan Dua Buah Larik TerurutMisalkan kita memiliki dua buah larik, L1 dan L2, yang masing-

masing sudah terurut naik. Kita ingin membentuk sebuah larik baru L3, yang merupakan gabungan dari dua buah larik tersebut, sedemikian sehingga L3 juga terurut naik. Misalkan elemen-elemen larik L1 dan L2 masing-masing :

Larik L1 : 1 13 24Larik L2 : 2 15 27 30

Penggabungan L1 dan L2 menghasilkan L3 yang tetap terurut menaik :Larik L3 : 1 2 13 15 24 27 30

Proses penggabungan dikerjakan dengan cara membandingkan satu elemen pada larik L1 dengan satu elemen pada larik L2. Jika elemen pada larik L1 lebih kecil dari elemen pada larik L2, maka salin elemen dari larik L1 ke L3. Elemen berikutnya pada larik L1 maju satu elemen, sedangkan elemen L2 tetap. Hal yang sama juga berlaku bila elemen dari L2 lebih kecil dari elemen L1, maka salin elemen dari L2 ke L3. Larik L2 maju satu elemen, larik L1 tetap. Dengan cara seperti ini, aka nada larik yang elemennya sudah habis duluan, sedangkan larik yang lain msih tersisa. Salin seluruh elemen yang tersisa ke L3.

Hal yang harus diperhatikan adalah ukuran larik L3. Jumlah elemen larik L3 adalah banyaknya elemen larik L1 ditambah dengan banyaknya elemen larik L2.

Contoh penggabungan larik L1 dan larik L2.

38

8. Merge SortAlgoritma pengurutan data mergesort dilakukan dengan

menggunakan cara divide-and-conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.

Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode mergesort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Mergesort.a. Divide

Memilah elemen – elemen dari rangkaian data menjadi dua bagian.b. Conquer

Conquer setiap bagian dengan memanggil prosedur mergesortsecararekursif

c. KombinasiMengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

39

L1 L2 L3

1 13 24 2 15 27 30 1< 2 1

1 1

3

24 2 15 27 30 2 < 13 1 2

1 1

3

24 2 1

5

27 30 13 <

15

1 2 1

3

1 13 2

4

2 1

5

27 30 15 <

24

1 2 3 1

3

1

5

1 13 2

4

2 15 2

7

30 24 <

27

1 2 3 1

3

1

5

2

4

1 13 24 2 15 2

7

30 27 1 2 3 1

3

1

5

2

4

2

7

1 13 24 2 15 27 3

0

30 1 2 3 1

3

1

5

2

4

2

7

3

0

Algoritma Merge SortProcedure Merge(input/output A, B : Larik, Output Awal,Tengah,Akhir :

integer)DeklarasiI, J, K, T : integerDeskripsiI AwalK AwalJ Tengah + 1ALGORITMA

If A[I] < A[J] then {elemen sebelah kiri lebih kecil}B[K] A[I]I I + 1

ElseB[K] A[J] {elemen sebelah kanan lebih besar}J J + 1

EndifK K + 1While ((I <= Tengah) or (J <= Akhir)){memasukkan sisa elemen saat 2 larik tidak sama panjang}

if I > Tengah then {larik kiri lebih dulu habis}for T J to Akhir

B[K+T-J] A[T]Endfor

Else {elemen kanan habis lebih dulu}For T I to Tengah

B[K+T-I] A[T]Endfor

Endif

Procedure Iterasi(input/output A, B : Larik, Input N, Cacah : integer)DeklarasiI, T : integerAlgoritmaI 1While I < (N – 2*Cacah + 1) do

Merge(A, B, I, I+Cacah-1, N)I I + 2*Cacah

EndwhileIf (I+Cacah-1) < N then {penggabungan ke sublarik}

Merge(A, B, I, I+Cacah-1, N)Else

For T I to N doB[T] A[T]

EndforEndif

Algoritma Mergesort{mengurutkan elemen larik sehingga tersusun menaik dengan metodepengurutan merge}{k.awal: elemen-elemen larik yang sudah terdefinisi nilainya}{k.akhir: elemen-elemen larik terurut menaik}Deklarasi

Cacah : integerB : Larik

AlgoritmaCacah 1

40

While Cacah < N doIterasi(A, B, N, Cacah)Cacah Cacah * 2Iterasi(B, A, N, Cacah)Cacah Cacah * 2

Endwhile

Contoh :

41

15 12 45 56 13 10 43 34 56 65

15 12 45 56 13 10 43 34 56 65

12 15 45 56 10 13 34 43 56 65

12 15 45 56 10 13 34 43 56 65

3415 43131210 45 56 56 65

4543 56 56 653415131210