Pengurutan (Shorting)
1. Pendahuluan
Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan dan susunan tertentu. Masalah pengurutan dapat ditulis sebagai berikut:
Diberikan larik L dengan n elemen yang sudah terdefinisi elemen-elemennya. Urutan larik tersebut sehingga tersusun secara menaik (ascending):
L[1] ≤ L[2] ≤ L[3] ≤....≤ L[n]
Atau secara menurun (descending):
L[1] ≥ L[2] ≥ L[3] ≥ ....≥ L[n]
Data yang diurut dapat berupa data bertipe dasar atau tipe terstruktur (record). Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai field kunci.
Algoritma yang sering ditemukan dalam literatur-literatur komputer antara lain: Bubble Sort, Selection Sort (Maximum Sort dan Minimum Sort), Insertion Sort, Heap Sort, Shell Sort, Quick Sort, Merge Shorte, Radix Sort, tree sort. Dalam modul ini tidak akan membahas semua algoritma pengurutan tersebut, tetapi hanya tiga buah algoritma pengurutan yang sederhana saja, yaitu:
1) Metode Pengurutan Apung (Bubble Sort),
2) Metode Pengurutan Seleksi (Selection Sort),
3) Metode Pengurutan Sisip (Shell Sort)
2. Tujuan Instruksional Umum
Mahasiswa dapat mengerti dan memahami algoritma pengurutan (sorting)
3. Tujuan Instruksional Khusus
- Memahami dan menguasai algoritma pengurutan dasar dengan menggunakan metode pengurutan Apung (Bubble Sort) dan konsep penerapannya dalam memecahkan masalah pemrograman
- Memahami dan menguasai algoritma pengurutan dasar dengan menggunakan Metode Pengurutan Seleksi (Selection Sort) dan konsep penerapannya dalam memecahkan masalah pemrograman
- Memahami dan menguasai algoritma pengurutan dasar dengan menggunakan Metode Pengurutan Sisip (Shell Sort) dan konsep penerapannya dalam memecahkan masalah pemrograman
4. Kegiatan Praktikum
.4.1. Kegiatan Praktikum 1
§ Uraian dan contoh
4.1.1 Algoritma Pengurutan Apung (Bubble Sort)
Prinsip pengapungan digunakan pada pengurutan apung. Apabila kita menginginkan larik terurut menaik, maka elemen larik yang berharga paling kecil ” diapungkan”, artinya diangkat ke ”atas” (atau ke ujung kiri larik) melalui proses pertukaran. Pengapungan ini dilakukan sebanyak n-1 langkah (satu langkah tersebut juga satu kali pass) dengan n adalah ukuran larik. Pada akhir setiap langkah ke-i, larik [1..n] akan terdiri atas dua bagian yaitu bagian yang sudah terurut, yaitu L[1..i], dan bagian yang belum terurut, L[i+1..n]. Setelah langkah terakhir, diperoleh larik L[1..n] yang terurut menaik. Lihat gambar.1:
| 1 | i i+1 n |
| Sudah terurut | Belum terurut |
Gambar.1 Bagian larik yang terurut pada metode pengurutan apung
Prosedur pengurutan apung (Bubble Sort) agar larik L terurut menaik adalah sebagai berikut:
| Procedure bubblesort(var L:larikint; n:integer);
Var i : integer ; k : integer ; temp : integer ;
begin for i := 1 to n-1 do for k := n downto i+1 do if L[ k ] < L [ k-1 ] then temp := L[ k ]; L[ k ]:= L[ k-1]; L[ k-1]:= temp; End; |
Prosedur pengurutan apung (Bubble Sort) dengan memanfaatkan prosedur Tukar, sebagai berikut :
| Procedure bubblesort_naik(var L : larikint ; n : integer);
Var i : integer ; k : integer ; procedure tukar (var a : integer ; b : integer); var temp : integer ; begin temp := a ; a := b ; b := temp ; end ;
begin for i := 1 to n-1 do for k := n downto i+1 do if L[ k ] < L [ k-1 ] then Tukar (L [k], L[k-1]); End; |
Prosedur pengurutan apung (Bubble Sort) agar larik L terurut menurun adalah sebagai berikut:
| Procedure bubblesort_turun(var L : larikint ; n : integer);
Var i : integer ; k : integer ; procedure tukar (var a : integer ; b : integer); var temp : integer ; begin temp := a ; a := b ; b := temp ; end ;
begin for i := 1 to n-1 do for k := n downto 1 do if L[ k ] < L [ k-1 ] then Tukar (L [k], L[k-1]); End; |
Contoh 4.1: program pengurutan bublesort dengan larik terurut menaik!
| program urut; uses wincrt; var L: array [1..100] of integer; i,k,n,temp : integer;
procedure input; begin writeln ('Data sebelum diurutkan'); write('masukkan data= '); readln(n); for i:=1 to N do begin write('L[' ,i, ']= ');readln (L[i]) ; end; end;
procedure bublesort; begin for i:=1 to N-1 do begin for k :=N downto i+1 do begin if L[k] < L[k-1] then begin temp :=L[k]; L[k] := L[k-1]; L[k-1] :=temp; end; end; end; end;
begin input; writeln; bublesort; writeln ('Data setelah diurutkan '); for i:=1 to N do begin writeln ('L[' ,i, '] = ',L[i]); end; writeln; end. |
§ Latihan 1
1. Buatlah program pengurutan bublesort dengan pemilihan larik terurut menaik (ascending) dan menurun (descending)!
.4.2. Kegiatan Praktikum 2
§ Uraian dan contoh
Algoritma Pengurutan Seleksi (Selection Sort)
Pengurutan Seleksi (Selection Sort) adalah memilih elemen maksimum/minimum dari larik, lalu menempatkan elemen maksimum/minimum itu pada awal atau akhir larik (elemen terujung) (Lihat gambar 2). Selanjutkan elemen terujung tersebut “diisolasi” dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa, yaitu memilih elemen maksimum/minimum berikutnya dan mempertukarkannya dengan elemen terujung larik sisa. Proses memilih nilai maksimum/minimum dilakukan pada setiap pass. Jika larik berukuran n, maka jumlah pass adalah n-1.
Sebelum :
Sesudah :
| 1 | N |
| Belum terurut |
|
|
| terurut |
Ada dua varian algoritma pengurutan seleksi ditinjau dari pemilihan elemen maksimum/minimum, yaitu :
1) Algoritma pengurutan seleksi-maksimum, yaitu memilih elemen maksimum sebagai basis pengurutan.
Prosedur pengurutan seleksi – maksimum untuk pengurutan menaik, sebagai berikut:
| Procedure selectionsortmax_naik(var L : larikint ; n : integer ); Var i : integer ; j : integer ; imaks: integer ; maks : integer ; temp : integer ; begin for i := n downto 2 do imaks := 1; maks := L[1]; for j := 2 to i do if L[ j ] > maks then imaks := j ; maks := L[ j ] ; begin temp := L[ i ] ; L[ i ] := maks ; L[imaks] := temp ; End; End; |
Prosedur pengurutan seleksi – maksimum untuk pengurutan menaik tanpa peubah maks, sebagai berikut:
| Procedure selectionsortmax_naik(var L : larikint ; n : integer ); Var i : integer ; j : integer ; imaks: integer ; temp : integer ; begin for i := n down to 2 do imaks := 1; for j := 2 to i do if L[ j ] > L[imaks] then imaks := j ; begin temp := L[ i ] ; L[ i ] := L[imaks] ; L[imaks] := temp ; End; End; |
Prosedur pengurutan seleksi – maksimum dengan memanfaatkan prosedur Tukar, sebagai berikut :
| Procedure selectionsortmax_naik(var L : larikint ; n : integer ); Var i : integer ; j : integer ; imaks: integer ; procedure tukar (var a : integer ; b : integer); var temp : integer ; begin temp := a ; a := b ; b := temp ; end ; begin for i := n down to 2 do imaks := 1; for j := 2 to i do if L[ j ] > L[imaks] then imaks := j ; tukar (L[imaks], L[i]); End; |
Prosedur pengurutan seleksi – maksimum agar larik L terurut menurun adalah sebagai berikut:
| Procedure selectionsortmax_turun(var L : larikint ; n : integer ); Var i : integer ; j : integer ; imaks: integer ; procedure tukar (var a : integer ; b : integer); var temp : integer ; begin temp := a ; a := b ; b := temp ; end ; begin for i := 1 to n-1 do imaks := i; for j := i+1 to n do if L[ j ] > L[imaks] then imaks := j ; tukar (L[imaks], L[i]); End; |
|
Contoh 4.2 program pengurutan seleksi maksimum dengan terurut menaik;
| program urut; uses wincrt; var L: array [1..100] of integer; i,j,imaks,n,temp : integer;
procedure input; begin writeln ('Data sebelum diurutkan'); write('masukkan banyaknya data= '); readln(n); for i:=1 to N do begin write('L[' ,i, ']= ');readln (L[i]) ; end; end;
Procedure selectionsortmax_naik;
begin for i := n downto 2 do begin imaks := 1; for j := 2 to i do begin if L[ j ] > L[imaks] then imaks := j ; begin temp := L[ i ] ; L[ i ] := L[imaks] ; L[imaks] := temp ; end; end; end; end;
begin input; writeln; selectionsortmax_naik; writeln ('Data setelah diurutkan '); for i:=1 to N do begin writeln ('L[' ,i, '] = ',L[i]); end; writeln; end. |
2) Algoritma pengurutan seleksi-minimum, yaitu memilih elemen minimum sebagai basis pengurutan.
Prosedur pengurutan seleksi – minimum dengan agar larik Lterurut menaik, sebagai berikut :
| Procedure selectionsortmin_naik(var L : larikint ; n : integer ); Var i : integer ; j : integer ; imin integer ; procedure tukar (var a : integer ; b : integer); var temp : integer ; begin temp := a ; a := b ; b := temp ; end ; begin for i := 1 to n-1 do imin := i; for j := i + 1 to n do if L[ j ] < L[imin] then imin := j ; tukar (L[imin], L[i]); End; |
Prosedur pengurutan seleksi – minimum agar larik L terurut menurun adalah sebagai berikut:
| Procedure selectionsortmin_turun(var L : larikint ; n : integer ); Var i : integer ; j : integer ; imin: integer ; procedure tukar (var a : integer ; b : integer); var temp : integer ; begin temp := a ; a := b ; b := temp ; end ; begin for i := n downto 2 do imin := 1; for j := 2 to i do if L[ j ] < L[imin] then imin := j ; tukar (L[imaks], L[i]); End; |
|
Contoh 4.3 : program pengurutan seleksi-minimum dengan terurut menurun!
| program urut; uses wincrt; var L: array [1..100] of integer; i,j,imin,n,temp : integer;
procedure input; begin writeln ('Data sebelum diurutkan'); write('masukkan banyaknya data= '); readln(n); for i:=1 to N do begin write('L[' ,i, ']= ');readln (L[i]) ; end; end;
Procedure selectionsortmin_turun;
begin for i := n downto 2 do begin imin := 1; for j := 2 to i do begin if L[ j ] < L[imin] then imin := j ;
begin temp := L[ i ] ; L[ i ] := L[imin] ; L[imin] := temp ; end; end; end; end;
begin input; writeln; selectionsortmin_turun; writeln ('Data setelah diurutkan '); for i:=1 to N do begin writeln ('L[' ,i, '] = ',L[i]); end; writeln; end. |
§ Latihan 2
1. buatlah program pengurutan seleksi-minimum dengan terurut menaik!
.4.3. Kegiatan Praktikum 3
§ Uraian dan contoh
Algoritma Pengurutan Sisipan (Insertion Sort)
Pengurutan sisip (insertion Sort) adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dilakukan dengan menyisir larik. Selama penyisiran dilakukan pergeseran elemen larik. Metode pengurutan sisip cocok untuk persoalan menyisipkan elemen baru kepada sekumpulan elemen yang sudah terurut.
Prosedur Pengurutan Sisip Untuk Pengurutan Menaik :
| Procedure insertionsort_naik (var L: larikint; n:integer); Var i : integer ; j : integer ; y : integer ; ketemu : boolean ;
begin for i := 2 to n do y := L[ i ] ; j := i – 1 ; ketemu := false ; while (j >= 1) and (not ketemu) do if y < L [ j ] L [ j+1] := L [ j ] ; j := j-1; else ketemu := true ; L [ j+1] := y; End; |
Prosedur Pengurutan Sisip Untuk Pengurutan Menurun :
| Procedure insertionsort_turun (var L: larikint; n:integer);
Var i : integer ; j : integer ; y : integer ; ketemu : boolean ;
begin for i := 2 to n do y := L[ i ] ; j := i – 1 ; ketemu := false ; while (j >= 1) and (not ketemu) do if y > L [ j ] L [ j+1] := L [ j ] ; j := j-1; else ketemu := true ; L [ j+1] := y; End; |
§ Latihan 3
1. Buatlah program pengurutan insertionsort dengan pemilihan larik terurut menaik (ascending)
2. Buatlah program pengurutan insertionsort dengan pemilihan larik terurut menurun (descending)
5. Kunci Jawaban latihan
1.1
| program bubbleshort; uses wincrt;
var L : array [1..100] of integer ; i,K,N,temp:integer; pilih:char;
begin begin writeln ('Data sebelum diurutkan'); write('masukkan data= '); readln(n); for i:=1 to N do begin write('L[' ,i, ']= ');readln (L[i]) ; end; end;
write('hasil ditampilkan secara ascending atau discending(a/d)?');readln(pilih); if (pilih='a') OR (pilih='A') then begin for i:=1 to N-1 do begin for k :=N downto i+1 do begin if L[k] < L[k-1] then begin temp :=L[k]; L[k] := L[k-1]; L[k-1] :=temp; end; end; end; end;
if (pilih= 'd') or (pilih='D') then begin for i:=1 to N-1 do begin for k :=N downto i+1 do begin if L[k] > L[k-1] then begin temp :=L[k]; L[k] := L[k-1]; L[k-1] :=temp; end; end; end; end;
writeln ('Data setelah diurutkan '); for i:=1 to N do begin writeln ('L[' ,i, '] = ',L[i]); end; writeln; end.
|
2.1
| program urut; uses wincrt; var L: array [1..100] of integer; i,j,imin,n,temp : integer;
procedure input; begin writeln ('Data sebelum diurutkan'); write('masukkan banyak data= '); readln(n); for i:=1 to N do begin write('L[' ,i, ']= ');readln (L[i]) ; end; end;
Procedure selectionsortmin_naik; begin for i := 1 to n-1 do begin imin := i; begin for j := i+1 to n do if L[ j ] < L[imin] then imin := j ; begin temp := L[ i ] ; L[ i ] := L[imin] ; L[imin] := temp ; end; end; end;
begin input; writeln; selectionsortmin_naik; writeln ('Data setelah diurutkan '); for i:=1 to N do begin writeln ('L[' ,i, '] = ',L[i]); end; writeln; end.
|
3.1
| program urut; uses wincrt; var L: array [1..100] of integer; i,j,y,n : integer;
procedure input; begin writeln ('Data sebelum diurutkan'); write('masukkan banyaknya data= '); readln(n); for i:=1 to N do begin write('L[' ,i, ']= ');readln (L[i]) ; end; end;
Procedure insertionsort_naik;
Var i : integer ; j : integer ; y : integer ; ketemu : boolean ;
begin for i := 2 to n do begin y := L[ i ] ; j := i - 1 ; ketemu := false ; while (j >= 1) and (not ketemu) do begin if y < L [ j ] then begin L [ j+1] := L [ j ]; j := j-1; end else ketemu := true ; L [ j+1] := y; End; end; end; begin input; writeln; insertionsort_naik; writeln ('Data setelah diurutkan '); for i:=1 to N do begin writeln ('L[' ,i, '] = ',L[i]); end; writeln; end.
|
3.2
| program urut; uses wincrt; var L: array [1..100] of integer; i,j,y,n : integer;
procedure input; begin writeln ('Data sebelum diurutkan'); write('masukkan banyaknya data= '); readln(n); for i:=1 to N do begin write('L[' ,i, ']= ');readln (L[i]) ; end; end;
Procedure insertionsort_turun;
Var i : integer ; j : integer ; y : integer ; ketemu : boolean ;
begin for i := 2 to n do begin y := L[ i ] ; j := i - 1 ; ketemu := false ; while (j >= 1) and (not ketemu) do begin if y > L [ j ] then begin L [ j+1] := L [ j ]; j := j-1; end else ketemu := true ; L [ j+1] := y; End; end; end; begin input; writeln; insertionsort_turun; writeln ('Data setelah diurutkan '); for i:=1 to N do begin writeln ('L[' ,i, '] = ',L[i]); end; writeln; end.
|
