Sorting (Pengurutan): Pengantar dan Operasi Dasar

Slide1Sorting (Pengurutan)

Slide2Pengantar 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

Slide3Contoh-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.

Slide4Counting 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

Slide5Algoritma                          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;

Slide6Algoritma                          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;

Slide7Tracing AlgoritmaOriginal :  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 }

Slide8Bubble 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.

Slide9Algoritmaprocedure 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}

Slide10Tracing Algoritma             cont…Array asal :   34  8  64  51  32  21 P = 6 :   34  8  64  51  32  21 j = 2     8  34  64  51  32 21  j = 3  8  34   64   51  32 21 j = 4  8   34  51   64  32   21 j = 5  8          34  51  32  64 21   j = 6 akhir pass 6 :  8   34  51  32   21 64 p = 5: 8   34  51  32   21 64   j = 2 8   34  51  32  21 64  j = 3 8  34   51  32  21 64  j = 4 8  34  32   51  21 64  j = 5 akhir pass 5 :   8  34  32  21  51 64

Slide11Tracing Algoritma             cont…P = 4: 8  34  32  21  51 64  j = 2 8   34  32  21  51 64  j = 3 8  32   34  21  51 64  j = 4 akhir pass 4 :   8  32  21  34  51 64 P = 3 : 8  32  21  34  51 64  j = 2 8   32  21  34  51 64  j = 3 akhir pass 3 :   8   21  32  34  51 64 P = 2: 8   21  32  34  51 64  j = 2 akhir pass 2 : 8  21  32  34  51 64  j = 2

Slide12Selection 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

Slide13AlgoritmaProcedure 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 }

Slide14Tracing AlgoritmaOriginal :   34  8  64  51  32  21 after p = 1 :   8  34  64  51  32  21 after p = 2 :  8   21  64  51  32  34 after p = 3 :  8  21   32  51  64  34 after p = 4 :  8  21  32   34  64  51 after p = 5 :  8  21  32  34   51  64

Slide15InsertionIdenya :  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 ).

Slide16Algoritmaprocedure 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;

Slide17Tracing AlgoritmaOriginal :  34  8  64  51  32  21 after p = 1 :  8  34  64  51  32  21 positions moved: 1 after p = 2 :  8  34  64  51  32  21 positions moved: 0 after p = 3 :  8  34  51  64  32  21 positions moved: 1 after p = 4 :  8  32  34  51  64  21 positions moved: 3 after p = 5 :  8  21  32  34  51  64 positions moved: 4