Algoritma dan Pemrograman
Sorting (Pengurutan) IS1313
Oleh: Eddy Prasetyo N
Pengantar
Sorting merupakan sebuah proses untuk mengatur item dalam suatu urutan tertentu ( menaik atau menurun ). Misalnya untuk mengurutkan NIM, mengurutkan IPK, mengurutkan nama dsb. Operasi dasar sorting : Membandingkan nilai
Untuk membandingkan nilai hanya digunakan operator : =, <, > atau kombinasi diantara operator tersebut untuk membandingkan nilai-nilai yang akan diurutkan.
Memindahkan nilai-nilai dalam daftar ke posisi yang sesuai
Contoh-contoh algoritma sorting Bubble Sort Insertion Sort Selection Sort Counting Sort Maximum Sort Shaker Sort Quick Sort Radix Sort Shell Sort Heap Sort Merge Sort Empat algoritma pertama akan dibahas dalam pertemuan kita.
Counting Sort
Pengurutan dengan pencacahan adalah pengurutan yang paling sederhana. Jika diketahui bahwa data ( nilai elemen array ) yang akan diurut mempunyai batas tertentu dan merupakan bilangan bulat, misalnya MIN...MAX maka cara paling sederhana untuk mengurut adalah : 1. Sediakan array TabCount[MIN...MAX] yang diinisialisasikan dengan nol dan pada akhir proses TabCount[i] berisi banyaknya data pada tabel asal yang berharga i. 2. Tabel dibentuk kembali dengan menuliskan kembali nilai-nilai yang ada
Algoritma cont…. procedure CountSort(var TabInt:array[1..N] of integer); var i,j,k,Min, Max : integer; TabCount : array[Min..Max] of integer; begin for ( i:=Min to Max ) do begin TabCount[i]:=0; end;
Algoritma cont…. for ( i:=1 to n ) do begin TabCount[TabInt[i]]:=TabCount[TabInt[i]]+1; end; k:=0; for(i:=Min to Max) do if TabCount[i] <> 0 then for(j:=1 to TabCount[i]) do begin k:=k+1; TabInt[k]:=i; end;
Tracing Algoritma Original : TabInt[1..7] berisi data : 2 3 5 6 5 1 2 Nilai MIN = 1 dan nilai MAX = 6 Maka akan diinisialisasikan array TabCount[1..6] = { 0, 0, 0, 0, 0, 0 } Isi TabCount pada : Pass 1 : { 0, 1, 0, 0, 0, 0 } Pass 2 : { 0, 1, 1, 0, 0, 0 } Pass 3 : { 0, 1, 1, 0, 1, 0 } Pass 4 : { 0, 1, 1, 0, 1, 1 } Pass 5 : { 0, 1, 1, 0, 2, 1 } Pass 6 : { 1, 1, 1, 0, 2, 1 } Pass 7 : { 1, 2, 1, 0, 2, 1 } Sehingga pada saat dituliskan kembali ke TabInt[1..7] = { 1, 2, 2, 3, 5, 5, 6 }
Bubble Sort
Idenya adalah : Lakukan pengulangan ( pass ) pada array, tukar elemen yang bersebelahan jika diperlukan ( perbandingan nilainya tidak sesuai ); jika tidak ada pertukaran elemen maka array sudah terurut. Dalam pass pertama, temukan elemen dengan nilai tertinggi ( maksimal ) dalam array dan tukarkan dengan elemen di sebelah kanannya dan seterusnya sampai dengan mencapai posisinya di ujung array sebelah kanan. Kemudian dalam pass kedua, nilai tertinggi kedua dalam array akan ditempatkan dalam posisinya ( di sebelah kiri elemen dengan nilai tertinggi ( maksimal ). Teruskan langkah ketiga sampai semua elemen array terurut.
Algoritma procedure bubbleSort(var a : array[1..size] of integer ); var int i,j, tmp; begin for ( i: = size downto 2) do begin for (j := 2 to i) do begin if (a[j-1] > a[j]) then begin tmp = a[j-1]; a[j-1] = a[j]; a[j] = tmp; end; end; end; end; {end of procedure}
Tracing Algoritma cont… Array asal : P=6:
34 34 8 8 8 8 akhir pass 6 : 8 p = 5: 8 8 8 8 akhir pass 5 : 8
8 8 34 34 34 34 34 34 34 34 34 34
64 64 64 64 51 51 51 51 51 51 32 32
51 51 51 51 64 32 32 32 32 32 51 21
32 32 32 32 32 64 21 21 21 21 21 51
21 21 21 21 21 21 64 64 64 64 64 64
j=2 j=3 j=4 j=5 j=6 j=2 j=3 j=4 j=5
Tracing Algoritma cont… P = 4:
8 8 8 akhir pass 4 : 8 P=3: 8 8 akhir pass 3 : 8 P = 2: 8 akhir pass 2 : 8
34 34 32 32 32 32 21 21 21
32 32 34 21 21 21 32 32 32
21 21 21 34 34 34 34 34 34
51 51 51 51 51 51 51 51 51
64 64 64 64 64 64 64 64 64
j=2 j=3 j=4 j=2 j=3 j=2 j=2
Selection Sort Mirip dengan bubble sort, namun algoritma ini lebih sedikit usaha untuk menempatkan setiap elemen ke posisinya Idenya : Pertama temukan elemen array terkecil ( minimum ) dan pertukarkan dengan elemen array di posisi ( indeks ) pertama Kemudian temukan elemen array terkecil kedua dan pertukarkan dengan elemen array di posisi ( indeks ) kedua Ulangi langkah-langkah diatas sampai semua array terurut
Algoritma Procedure selectionSort(var a : array[1..size] of integer ); var integer i,j, min, tmp; begin for( i:=1 to size-1) do begin min = i; for (j = i + 1 to size ) do begin if (a[j] < a[min]) then min = j; tmp = a[min]; a[min] = a[i]; a[i] = tmp; end; end; end; { end of procedure }
Tracing Algoritma Original : after p = 1 : after p = 2 : after p = 3 : after p = 4 : after p = 5 :
34 8 8 8 8 8
8 34 21 21 21 21
64 64 64 32 32 32
51 51 51 51 34 34
32 32 32 64 64 51
21 21 34 34 51 64
Insertion Idenya : Perhatikan elemen-elemen array pada setiap saat, penyisipan dilakukan pada tempat yang tepat untuk setiap elemen array dengan menggunakan sequential search ( untuk menjaga elemen-elemen array tetap terurut ). Elemen array yang akan disisipkan ke posisi yang tepat akan memindahkan elemen array yang lebih besar satu posisi ke kanan dan kemudian akan menempati posisi yang ditinggalkan ( pencarian posisi yang tepat akan dilakukan selama masih ada elemen array yang di sebelah kirinya yang mempunyai nilai lebih besar ).
Algoritma procedure insertionSort(var a : array[1..size] of integer ); var int i,j,tmp; bagin for(i:=2 to size)do begin tmp:=a[i]; j=i; while ((j>1) and ( tmp < a[j-1])) do begin a[j]:=a[j-1]; j:=j-1; end; a[j]:=tmp end; end;
Tracing Algoritma Original : after p = 1 :
34 8
8 34
64 64
51 51
after p = 2 :
8
34
64
51
after p = 3 :
8
34
51
64
after p = 4 :
8
32
34
51
after p = 5 :
8
21
32
34
32 21 32 21 positions moved: 1 32 21 positions moved: 0 32 21 positions moved: 1 64 21 positions moved: 3 51 64 positions moved: 4
