Modul Algoritma Sorting

BAB V

S O R T I N G 

A.   Pendahuluan

Deskripsi Singkat

Bab ini akan membahas definisi pengurutan, pengurutan gelembung, pengurutan maksimum/minimum, pengurutan seleksi.

Relevansi

Pengurutan akan memudahkan kita dalam mencari data dalam sebuah program. Pengurutan sangat erat kaitannya dengan pencarian.

Tujuan Instruksional Khusus

Mahasiswa mampu membuat program dengan menggunakan perintah sorting.

B.   Penyajian

1)      Definisi Pengurutan (Sorting)

Selain pencarian, pengurutan data merupakan salah satu permasalahan umum yang juga sering dijumpai dalam pemrograman. Sebagai bukti nyata, tinjaulah metode pencarian bagi dua di atas yang menuntut kita untuk melakukan pengurutan terlebih dahulu sebelum kita melakukan pencarian.

Dalam pemrograman, terdapat beberapa metode untuk melakukan pengurutan data. Namun terdapat 8 (delapan) metode yang umumnya banyak digunakan, yaitu :

1.      Bubble Sort

2.      Maximum/Minimum Sort

3.      Selection Sort

4.      Insertion Sort

5.      Heap Sort

6.      Quick Sort

7.      Merge Sort

8.      Shell Sort

Pada pembahasan ini, hanya 3 (tiga) metode yang akan dibahas yaitu metode pengurutan gelembung (bubble sort), pengurutan maksimum/minimum (maximum/minium sort) dan pengurutan seleksi (selestion sort).

2)      Pengurutan Gelembung (Bubble sort)

Menurut sumber yang ada, metode ini diinspirasi oleh adanya gelembung sabun yang mengapung di atas permukaan air. Hal ini tentunya disebabkan karena berat jenis gelembung sabun lebih kecil dari berat jenis air. Konsep dari fenomena tersebut kemudian diterapkan sebagai metode pengurutan data di dalam array. Dalam metode ini data dengan nilai terkecil akan diapungkan ke posisi teratas, dan sebaliknya data dengan nilai terbesar akan berada pada posisi terbawah. Sebagai contoh, asumsikan bahwa kita memiliki array A yang berisi lima buah elemen data, seperti yang tampak di bawah ini.

25	22	18	20	15
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.1 Array A sebelum diurutkan dengan metode gelembung

Di sini kita akan mengurutkan array tersebut secara menaik, yaitu dengan mengapungkan nilai terkecil ke posisi teratas (paling kiri). Proses ini tentu akan dilakukan dengan menggunakan pertukaran antar elemen array. Tahapan-tahapan yang harus dilakukan adalah sebagai berikut.

Tahap 1

Mulai dari A[5] sampai A[2], lakukan perbandingan nilai antara A[k] dan A[k-1] dimana variabel k mewakili indeks array yang sedang aktif. Apabila nilai A[k] lebih kecil, maka tukarkan nilai A[k] dengan A[k-1]. Sampai di sini, array tersebut akan menjadi seperti berikut.

15	25	22	18	20
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.2 Hasil Pengurutan  Array A  tahap 1

Tahap 2

Mulai dari A[5] sampai A[3], lakukan proses seperti pada tahap 1 sehingga array akan menjadi seperti berikut.

15	18	25	22	20
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.3 Hasil Pengurutan  Array A  tahap 2

Tahap 3

Mulai dari A[5] sampai A[4], lakukan proses seperti pada tahap 1 dan 2  sehingga array akan menjadi seperti berikut.

15	18	20	25	22
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.4 Hasil Pengurutan  Array A  tahap 3

Tahap 4

Tahap ini merupakan tahap terakhir dimana kita akan melakukan perbandingan terhadap nilai dari elemen terakhir (A5]) dengan elemen terakhir-1 (A[4]). Apabila nilai A[5] lebih kecil maka tukarkan nilainya dengan A[4] sehingga array A di atas akan terurut secara menaik seperti yang tampak di baeah ini.

15	18	20	22	25
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.5 Hasil Pengurutan  Array A  tahap 4

Pada proses yang terjadi di atas tampak jelas bahwa untuk melakukan pengurutan data dengan lima buah elemen, kita harus melakukan empat tahapan. Sekarang, apabila proses di atas kita translasikan ke dalam bahasa pascal, maka hasilnya adalah sebagai berikut.

Var

n,                                              {banyaknya elemen array}

j, k                                            {variabel bantu untuk indeks pengulangan}

temp : integer;                      {variabel bantu untuk melakukan pertukarannilai}

begin

for j:= 1 to N-1 do begin

for k:= N downto j+1 do begin

if A[k] < A[k-1] then begin

temp := A[k];

A[k] := A[k-1];

A[k-1] := temp;

End;

End;

End;

End;

Untuk lebih memperjelas, coba perhatikan implementasinya di dalam program berikut.

Program UrutGelembung;

Uses crt;

Const

n = 5;

A : array [1 . . n] of integer = (25, 22, 18, 20, 15);

Var

j, k, temp : integer;

begin

clrscr;

{menampilkan data sebelum proses pengurutan}

Writeln(’Data sebelum diurutkan’);

For j := 1 to n do begin

Writeln(’A[’, j,’] = ’, A[j];

End;

Melakukan proses pengurutan data}

For j:= 1 to n-1 do begin

For k:= n downto j+1 do begin

If A[k] < A[k-1] then begin

Temp :=A[k];

A[k] := A[k-1];

Ak-1] := temp;

End;

End;

End;

{Menampilkan data setelah proses pengurutan}

Writeln;

Writeln (’Data setelah diurutkan’);

For j:= 1 to n do begin

Writeln(’A[’, j, ’] = ’, A[j]);

End;

Readln;

End.

Hasil yang akan diberikan oleh program di atas adalah sebagaii beriku.

Data sebelum diurutkan

25

22

18

20

15

Data setelah diurutkan

15

18

20

22

25

3)      Pengurutan Maksimum/Minimum

Dengan metode ini, elemen array dengan nilai maksimum/minimum akan disimpan ke bagian ujung array (elemen pertama maupun terakshir). Selanjutnya nilai tersebut akan diisolasi atau diikat dan tidak diikutkan lagi dalam proses selanjutnya. Di sini, kita hanya akan menggunakan metode maksimum saja dan tidak akan membahas mengenai metode minimum. Hal ini disebabkan karena konsep yang terdapat pada metode minimum sama persis dengan metode maksimum. Untuk mempermudah pembahasan, coba perhatikan kembali array A yang terdapat pada bahasan sebelumnya.

25	22	18	20	15
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.6 Array A sebelum diurutkan dengan metode Maksimum/Minimum

Pada bagian ini kita akan melakukan pengurutan data di dalam array tersebut dengan menggunakan metode maksimum, di mana kita akan melempar nilai maksimum ke bagian paling kanan array. Adapun tahapan-tahapan yang perlu dilalui untuk melakukan hal tersebut adalah sebagai berikut.

Tahap 1

Mulai dari A[1] sampai A[5], cari nilai maksimum dan tukarkan nilainya dengan elemen terakhir (A[5]) sehingga array akan akan berubah menjadi seperti di bawah ini.

15	22	18	20	25
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.7 Hasil Pengurutan  Array A  tahap 1

Sampai di sini, elemen terakhir (A[5]) tidak akan diikutkan lagi ke dalam proses atau tahap selanjutnya.

Tahap 2

Mulai dari A[1] sampai A[4], cari nilai maksimum dan tukarkan nilainya dengan elemen terakhir saat ini (A[4]) sehingga array akan akan berubah menjadi seperti di bawah ini.

15	20	18	2	25
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.8 Hasil Pengurutan  Array A  tahap 2

Sampai di sini, elemen ke-4 (A[4]) juga tidak akan diikutkan lagi ke dalam proses atau tahap selanjutnya.

Tahap 3

Mulai dari A[1] sampai A[3], cari nilai maksimum dan tukarkan nilainya dengan elemen terakhir saat ini (A[3]) sehingga array akan tampak seperti di bawah ini.

15	18	20	22	25
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.9 Hasil Pengurutan  Array A  tahap 3

Sampai di sini, elemen ke-3 (A[3]) juga tidak akan diikutkan lagi ke dalam proses selanjutnya.

Tahap 4

Tahap terakhir, cari nilai maksimum antara A[1] sampai A[2] dan tukarkan nilainya dengan elemen A[2]. Untuk kasus ini nilai maksimum terdapat pada A[2] sehingga di sini benarnya terjadi proses yang seharusnya tidak perlu dilakukan, yaitu menukarkan nilai A[2] dengan A[2]. Berikut ini bentuk translasi metode di atas ke dalam bahasa Pascal.

Var

n,                                                     {banyaknya elemen array keseluruhan}

x,                                                      {banyaknya elemen array yang belum terurut}

j, k,                                                   {untuk indeks pengulangan}

maks,                                             {untuk menyimpan nilai maksimal}

imaks,                                            {untuk menyimpan indeks dari elemen yang menyimpan nilai maksimal}

temp : integer;                              {variabel bantu untuk proses pertukaran}

begin

x:= n;                                              {mula-mula semua belum terurut}

for j:= 1 to n-1 do begin

maks := A[1];

imaks := 1;

for k:= 2 to x do begin

if(A[k] > maks) then begin

maks := A[k];

imaks := k;

end;

end;

{tukarkan maks dengan A[x]}

Temp := A[x];

A[x] := A[imaks];

A[imaks] := temp;

{ikat elemen terakshir dengan menurunkan nilai x}

x := x – 1;

end;

end;

4)      Pengurutan Seleksi

Pengurutan dengan metode seleksi ini bekerja dengan cara memilih salah satu elemen serta menganggapnya sebagai nilai terkecil. Kemudian nilai tersebut aan dibandingkan dengan elemen-elemen pada posisi berikutnya. Apabila nilai yang dipilih pertama kali lebih besar dari nilai elemen pembanding maka tukarkan kedua buah nilai tersebut. Untuk memperjels pembahasan ini, marilah kita perhatikan kembali array A seperti pembahasan sebelumnya. Berikut gambarannya.

25	22	18	20	15
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.10 Array A sebelum diurutkan dengan metode Seleksi

Tahap 1

Mula-mula, A[1] akan dianggap sebagai nilai terkecil, yaitu dengan cara memasukkan nilai 1 ke dalam variabel, misalnya dengan nama min. Mulai dari j = min + 1 sampai n (jumlah elemen array), lakukan perbandingan antara A[j] dengan nilai A[min]. Apabila nilai dari A[min] > A[j], isikan min = j. Setelah pengulangan selesai, tukarkan nilai A[min] dan A[1]. Untuk kasus ini, nilai min adalah 5 karena nilai terkecil tersimpan pada indeks ke-5. hal tersebut akan menyebabkan array A tampak menjadi seperti berikut.

15	22	18	20	15
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.11 Hasil Pengurutan  Array A  tahap 1

Tahap 2 

Mula-mula, A[2] akan dianggap sebagai nilai terkecil, yaitu dengan cara memasukkan nilai 2 ke dalam variabel, misalnya dengan nama min. Kemudian sama seperti di atas, lakukan pengulangan mulai dari j = min + 1 sampai n dan bandingkan setiap nilainya.  Setelah didapatkan nilai min, maka tukarkan A[min] dengan A[2]. Untuk kasus ini, nilai minimum ditemukan pada indeks ke-3 sehingga min = 3. Tukarkan A[min] dengan A[2] sehingga array A akan tampak seperti berikut.

15	18	22	20	25
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.12 Hasil Pengurutan  Array A  tahap 2

Tahap 3

Mula-mula, A[3] akan dianggap sebagai nilai terkecil, yaitu dengan cara memasukkan nilai 3 ke dalam variabel min. Kemudian sama seperti di atas, lakukan pengulangan mulai dari j = min + 1 sampai n dan bandingkan setiap nilainya.  Setelah didapatkan nilai min, maka tukarkan A[min] dengan A[3]. Untuk kasus ini, nilai minimum ditemukan pada indeks ke-4 sehingga min = 4. Tukarkan A[min] dengan A[4] sehingga array A akan tampak seperti berikut.

15	18	20	22	25
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.13 Hasil Pengurutan  Array A  tahap 3

Tahap 4

Mula-mula, A[4] akan dianggap sebagai nilai terkecil, yaitu dengan cara memasukkan nilai 4 ke dalam variabel min. Kemudian sama seperti di atas, lakukan pengulangan mulai dari j = min + 1 sampai n dan bandingkan setiap nilainya.  Setelah didapatkan nilai min, maka tukarkan A[min] dengan A[4]. Untuk kasus ini, nilai minimum ditemukan pada indeks ke-4 sehingga min = 4. Tukarkan A[min] dengan A[4] sehingga array A akan tampak seperti berikut.

15	18	20	22	25
A[1]	A[2]	A[3]	A[4]	A[5]

Gambar 5.14 Hasil Pengurutan  Array A  tahap 4

C. Penutup

1)      Pertanyaan

Buat program untuk mengurutkan data mahasiswa dengan metode seleksi.

2)    Umpan Balik dan Tindak Lanjut

Untuk menguasai materi ini, sebaiknya anda membuat ringkasan materi tentang sorting (pengurutan) dan membuat sendiri beberapa program dengan sorting.

Jawab pertanyaan di atas dengan langsung membuat program di komputer. Jalankan program tersebut sampai benar. Hapus kembali listing program yang sudah benar dan buat kembali program tersebut, dan jalankan. Kalau tingkat kesalahan pada pembuatan program sudah kecil, anda dapat melanjutkan materi berikutnya. Kalau program belum jalan, perbaiki terus sampai benar.

3)      Kunci Jawaban

Procedure selectionsort;

Var

      i, j, temp, imax : integer;

begin

      for i:= 1 to n-1 do

      begin

           imax := i;

           for j := i+1 to n do

                  if TabInt[j] < TabInt[max] then

                      imax := j;

           temp := TabInt[imax];

           TabInt[imax] := TabInt[i];

           TabInt[i] := temp;

      End;

End.

Daftar Pustaka

Jurusan Informatika. 2006. Bahan Ajar Pemrograman 2. Hibah Pengajaran PHK A1 Universitas Negeri Gorontalo

Kadir, Abdul. 2002. Pemrograman Pascal Buku 1. Yogyakarta: Andi Offset.

Munir, Rinaldi. 2005. Algoritma dan Pemrograman dalam bahasa Pascal dan C Edisi 3. Bandung: Informatika.

Rahardjo, Budi. 2005. Teknik Pemrograman Pascal. Bandung:Informatika