DATA SORTING
Altien Jonathan Rindengan, S.Si, M.Kom
Pendahuluan
Sorting (pengurutan) : proses mengatur sekumpulan objek menurut urutan atau susunan tertentu Diberikan array L dengan n elemen yg sudah terdefinisi elemen-elemennya. Urutan array tersusun secara menaik (ascending) : L[1] ≤ L[2] ≤ … ≤ L[n] Urutan array tersusun secara menurun (descending) : L[1] ≥ L[2] ≥ … ≥ L[n]
Pendahuluan …
23, 27, 45, 67, 100,133 (data bertipe integer terurut naik) 50.37, 31, 20.3, 19.5, 0.4, -3.2, -10.9 (data bertipe real terurut turun) „Amir‟, „Badu‟,‟Budi‟, „Eno‟,‟Rudi‟, „Zamri‟ (data bertipe string terurut naik) „d‟,‟e‟,‟g‟,‟i‟,‟x‟ (data bertipe karakter terurut naik)
Jenis-jenis Algoritma Pengurutan
Bubble Sort Selection Sort (Maximum Sort & Minimum Sort) Insertion Sort Heap Sort Shell Sort Quick Sort Merge Sort Radix Sort Tree Sort
Jenis-jenis Algoritma Pengurutan …
Bubble Sort & Selection Sort : melakukan prinsip pertukaran elemen dalam proses pengurutan (exchange sort) Radix Sort & Tree Sort : melakukan prinsip geser dan sisip elemen dalam proses pengurutan (shift & insert sort) Heap Sort & Tree Sort, memerlukan konsep tree
Algoritma Bubble Sort
Bubble sort (pengurutan apung) : diinspirasi oleh gelembung sabun yang berada di atas permukaan air Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung di atas permukaan air Secara umum, benda berat akan terbenam dan benda ringan akan terapung
Algoritma Bubble Sort …
Prinsip pengapungan : Jika kita menginginkan array teruurut naik, maka elemen array yang bernilai paling kecil “diapungkan” artinya diangkat ke “atas” (ujung kiri array) melalui proses pertukaran Proses pengapungan dilakukan sebanyak n-1 langkah ( 1langkah = 1pass), n adalah ukuran array Pada akhir setiap langkah ke-i, array L[1..n] akan terdiri dari 2 bagian : Terurut : L[1..i] Belum terurut : L[i+1..n]
Langkah terakhir diperoleh array L[1..n] yang terurut naik
Algoritma Bubble Sort …
Algoritmanya (terurut naik): Untuk setiap pass i=1,2,…,n-1,lakukan : Mulai dari elemen k=n,n-1,…,i+1, lakukan: 1. 2.
Bandingkan L[k] dengan L[k-1] Pertukarkan L[k] dengan L[k-1] jika L[k]
Algoritma Bubble Sort …
Rincian setiap pass sebagai berikut : Pass 1 : Mulai dari elemen ke-k = n,n-1,…,2, bandingkan L[k] dengan L[k-1]. Jika L[k]
Algoritma Bubble Sort …
Pass 3 : Mulai dari elemen ke-k = n,n-1,…,4, bandingkan L[k] dengan L[k-1]. Jika L[k]
Algoritma Bubble Sort …
Contoh array dengan 6 elemen : 25 27 10 1
2
3
8
76 21
4
5
6
Pass 1: k
elemen yg dibandingkan
pertukarkan?
hasil sementara
k=6 k=5 k=4 k=3 k=2
L[6]
ya tidak ya ya ya
25, 27, 10, 8, 21, 76 25, 27, 10, 8, 21, 76 25, 27, 8, 10, 21, 76 25, 8, 27, 10, 21, 76 8, 25, 27, 10, 21, 76
8 1
25 27 10 21 76 2
3
4
5
6
Algoritma Bubble Sort …
Pass 2: k
elemen yg dibandingkan
pertukarkan?
hasil sementara
k=6 k=5 k=4 k=3
L[6]
tidak tidak ya ya
8, 25, 27, 10, 21, 76 8, 25, 27, 10, 21, 76 8, 25, 10, 27, 21, 76 8, 10, 25, 27, 21, 76
8 1
10 25 27 21 76 2
3
4
5
6
Algoritma Bubble Sort …
Pass 3: k
elemen yg dibandingkan
pertukarkan?
hasil sementara
k=6 k=5 k=4
L[6]
tidak ya ya
8, 10, 25, 27, 21, 76 8, 10, 25, 21, 27, 76 8, 10, 21, 25, 27, 76
8 1
10 21 25 27 76 2
3
4
5
6
Algoritma Bubble Sort …
Pass 4: k
elemen yg dibandingkan
pertukarkan?
hasil sementara
k=6 k=5
L[6]
tidak tidak
8, 10, 21, 25, 27, 76 8, 10, 21, 25, 27, 76
8 1
10 21 25 27 76 2
3
4
5
6
Algoritma Bubble Sort …
Pass 5: k
elemen yg dibandingkan
pertukarkan?
hasil sementara
k=6
L[6]
tidak
8, 10, 21, 25, 27, 76
8 1
10 21 25 27 76 2
3
4
5
6
Sudah terurut: 8 1
10 21 25 27 76 2
3
4
5
6
program urut_bubble; uses crt; const nmaks=1000; var L:array[1..nmaks] of integer; n,i,k,temp:integer; begin clrscr; write('Jumlah data : ');readln(n);writeln; write('Data belum terurut:'); for i:=1 to n do begin gotoxy(4*i,5);read(L[i]); end; 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;
writeln; writeln('Data setelah pengurutan :'); for i:=1 to n do begin gotoxy(4*i,9);writeln(L[i]); end; writeln; readln; end.
Algoritma Selection Sort
Gagasannya memilih elemen maksimum/minimum dari array, lalu menempatkannya apda awal atau akhir array Selanjutnya elemen tersebut “diisolasi” dan tidak disertakan pada proses selanjutnya. Proses ini diulang untuk elemen array yang tersisa Ada 2 varian selection sort : Maximum selection sort : memilih elemen maksimum sebagai basis pengurutan Minimum selection sort : memilih elemen minimum sebagai basis pengurutan
Maximum selection sort
Untuk array terurut menaik : Jumlah pass = n-1 Untuk setiap pass i =1,2,…jumlah pass, lakukan :
1.
2. 3.
Cari elemen terbesar (maks), mulai dari elemen-1 sampai n Pertukarkan elemen maks dengan elemen ke-n Kurangi n satu (karena elemen ke-n sudah terurut)
Maximum selection sort …
Pass 1 :
Pass 2 :
Cari elemen maks di dalam L[1..n] Pertukarkan elemen maks dengan elemen L[n] Ukuran array yang belum terurut = n-1
Cari elemen maks di dalam L[1..n-1] Pertukarkan elemen maks dengan elemen L[n-1] Ukuran array yang belum terurut = n-2
Pass n-1 :
Cari elemen maks di dalam L[1..2] Pertukarkan elemen maks dengan elemen L[2] Ukuran array yang belum terurut = 1
Maximum selection sort …
Contoh array dengan 6 elemen : 29 27 10 1
2
8
3
76 21
4
5
6
Pass 1: Cari
elemen maks di array L[1..6], diperoleh maks=L[5]=76 Pertukarkan maks dengan L[6], diperoleh 29 27 10 1
2
3
8 4
21 76 5
6
Maximum selection sort …
Pass 2: Cari
elemen maks di array L[1..5], diperoleh maks=L[1]=29 Pertukarkan maks dengan L[5], diperoleh 21 27 10 1
2
3
8 4
29 76 5
6
Pass 3: Cari
elemen maks di array L[1..4], diperoleh maks=L[2]=27 Pertukarkan maks dengan L[4], diperoleh 21
8
1
2
10 27 29 76 3
4
5
6
Maximum selection sort …
Pass 4: Cari
elemen maks di array L[1..3], diperoleh maks=L[1]=21 Pertukarkan maks dengan L[3], diperoleh
10
8
1
2
21 27 29 76 3
4
5
6
Pass 5: Cari
elemen maks di array L[1..2], diperoleh maks=L[1]=10 Pertukarkan maks dengan L[2], diperoleh 8 1
10 21 27 29 76 2
3
4
5
6
Maximum selection sort …
Tinggal satu elemen L[1]=8, maka pengurutan selesai dengan L yang terurut adalah
8 1
10 21 27 29 76 2
3
4
5
6
program urut_selection_max; uses crt; const nmaks=1000; var L:array[1..nmaks] of integer; n,i,j,imaks,temp:integer; begin clrscr; write('Jumlah data : ');readln(n);writeln; write('Data belum terurut:'); for i:=1 to n do begin gotoxy(4*i,5);read(L[i]); end; for i:=n downto 2 do begin imaks:=1; for j:=2 to i do begin if L[j] > L[imaks] then imaks:=j; end; temp:=L[imaks]; L[imaks]:=L[i]; L[i]:=temp; end;
writeln; writeln('Data setelah pengurutan :'); for i:=1 to n do begin gotoxy(4*i,9);writeln(L[i]); end; writeln; readln; end.
