Minggu, 01 November 2015

Algoritma Pseucode untuk Bubble Sort & Selection Sort

Pseudocode adalah bentuk penulisan algoritma yang menggunakan struktur bahasa pemrograman sederhana. Walaupun pseudocode memakai struktur bahasa pemrograman, pseudocode tidak mengikuti aturan penulisan bahasa pemrograman manapun. Karena pseudocode dituliskan hanya untuk mempermudah seseorang memahami sebuah algoritma. Dengan begitu, pseudocode hanyalah menyerupai kode program saja, dan tidak bisa dimengerti langsung oleh komputer. Pseudocode baru bisa diolah oleh komputer jika telah mengikuti aturan penulisan sebuah bahasa pemrograman. (bahasa C, Java, Pascal, dan lain-lain.)
   
    1.      Algoritma Bubble Sort
Di antara beberapa algoritma pengurutan yang ada, algoritma bubble sort merupakan teknik yang paling sederhana. Proses pencarian solusi dilakukan secara brute force, langsung ke intinya, yaitu membandingkan elemen-elemen dalam tabel. Elemen yang lebih kecil ditukar posisinya dengan elemen yang lebih besar bila posisi elemen yang lebih kecil ada di bawah elemen yang lebih besar. Jika tabel belum terurut, proses diulang kembali sampai elemen paling kecil berada di posisi teratas dan elemen lainnya sudah terurut.

      a.      Contoh Sequence Bubble Short
Diketahui array L dengan N=5 (elemen belum terurut). Array akan diurutkan secara ascending.
  Ø  Pseucode;
procedure BubbleSort (input/output L : TabelInt, input n : integer)
{ Mengurutkan tabel L[1..N] sehingga terurut menaik dengan metode pengurutan bubble sort.
Masukan : Tabel L yang sudah terdefenisi nilai-nilainya.
Keluaran: Tabel L yang terurut menaik sedemikian sehingga
L[1] ≤ L[2] ≤ … ≤ L[N]. }
  Ø  Deklarasi;
i : integer { pencacah untuk jumlah langkah }
k : integer { pencacah,untuk pengapungan pada setiap langkah}
temp : integer { peubah bantu untuk pertukaran }
  Ø  Algoritma:
for i ← 1 to n - 1 do
for k ← n downto i + 1 do
 if L[k] < L[k-1] then {pertukarkan L[k] dengan L[k-1]}
temp ← L[k]
L[k] ← L[k-1]
L[k-1] ← temp
Endif
Endfor
Endfor
  Ø  Sorting:
Urutkan array berikut:             6          8          5          3          1
0   1   2   3   4
ü  Pass 1:
I=0 ; J= N-1 =4                       6          8          5          1          3
J = 3                                        6          8          1          5          3
J = 2                                        6          1          8          5          3
J = 1                                        1          6          8          5          3

Hasil akhir langkah 1: 1          6          8          5          3

0   1   2   3   4
ü  Pass 2:
I= 1; J= N-1=4                        1          6          8          3          5
J = 3                                        1          6          3          8          5
J=2                                          1          3          6          8          5

Hasil akhir langkah 2:             1          3          6          8          5

0   1   2   3   4
ü  Pass 3:
I= 1; J= N-1=4                        1          3          6          5          8
J=3                                          1          3          5          6          8

Hasil akhir langkah 2:             1          3          5          6          8 

      2.      Algoritma Selection Sort
Selection Sort adalah sebuah algoritma pengurutan, dimana data terkecil / terbesar akan ditempatkan di awal atau di akhir data. Berbeda dengan Bubble Sort yang langsung menukarkan data jika ditemukan, maka dalam selection sort setelah data yang tidak terurut ditemukan, tidak akan langsung ditukarkan melainkan akan ditandai terlebih dahulu sebagai data terkecil / terbesar dalam satu iterasi.
Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :
  • Algoritma pengurutan maksimum (maximum selection sort), yaitu memilih elemen maksimum sebagai basis pengurutan.
  • Algoritma pengurutan minimum (minimum selection sort), yaitu memilih elemen minimum sebagai basis pengurutan.

  
  Ø  Contoh Squence Algoritma Maximum Selection Sort
Untuk mendapatkan array yang terurut menaik (ascending), algoritma maximum selection sort dapat ditulis sebagai berikut :
 Jumlah Pass = N-1 (jumlah pass)
Untuk setiap pass ke – I = 0,1,….., jumlah pass lakukan :
ü  cari elemen maksimum (maks) mulai dari elemen ke – I sampai elemen ke – (N-1)
ü  pertukarkan maks dengan elemen ke – I
ü  kurangi N dengan satu
Rincian setiap pass adalah sebagai berikut :
Langkah 1:      Cari elemen maksimum di dalam L[0..(N-1)]
Pertukarkan elemen maksimum dengan elemen L[N-1]
Langkah 2:      Cari elemen maksimum di dalam L[0..N-2]
Pertukarkan elemen maksimum dengan elemen  L[N-2]
Langkah 3:      Cari elemen maksimum di dalam L[0..N-3]
Pertukarkan elemen maksimum dengan elemen   L[N-3]
Langkah N-1:  Tentukan elemen maksimum di dalam L[0..1]
Pertukarkan elemen maksimum dengan elemen L[0]
(elemen yang tersisa adalah L[0], tidak perlu diurut karena hanya satu-satunya).
Jadi , pada setiap pass pengurutan terdapat proses mencari harga maksimum dan  proses pertukaran dua buah elemen array.
  Ø  Pseucode
      //prosedur algoritma Maximum Selection Sort secara Ascending (atau Descending)
      //I.S:array sudah berisi nilai integer yang belum terurut
      //F.S:nilai-nilai dalam array terurut secara Ascending (atau Descending)

            procedure v_SelAsc(input/output A:array[0..4]of integer, input N:integer)

  Ø  Deklarasi:
            maks, k, j, temp: integer

  Ø  Algoritma:
            for(k=(N-1);k>=0;kßk-1)  // for(k=0;k<=(N-2);kßk+1) jika dalam Descending
                  maksß0;
            // cari elemen maksimum
                  for(j=0;j<=k;jßj+1)
                        if (A[j] > A[maks])
                              maksßj;
                        endif
                  endfor
                  v_Tukar(A[k],A[maks])
            //panggil procedure v_Tukar
                  endfor
            end procedure

  Ø  Pseudocode Algoritma Tukar Tempat :

            //prosedur algoritma Tukar Tempat
            //I.S:nilai-nilai yang dikirimkan sudah terdefinisi sebelumnya
            //F.S:nilai yang dikirimkan tertukar nilainya

            procedure v_Tukar(input/output P:integer, input/output M:integer)

  Ø  Deklarasi:
            temp: integer

  Ø  Algoritma:
            temp ß P
                  P ß M
                  M ß temp
            endprocedur

  Ø  Sorting
Urutkan array berikut secara ascending, dengan algoritma maximun selection sort:
                        12                    10                    17                    7                      2
Pass 1:
ü  Cari elemen maksimun di dalam array L[0..4]. Maks=L[2]=17
ü  Tukar maks dengan L[4], maka diperoleh

12                    10                    2                      7                      17
Pass 2:  berdasarkan susunan array pada Pass 1
ü  Cari elemen maksimun di dalam array L[0..3]. Maks=L[0]=12
ü  Tukar Maks dengan L[3], maka diperoleh
7                      10                    2                      12                    17
Pass 3: berdasarkan susunan array pada Pass 2
ü  Cari elemen maksimum di dalam array [0..2]. Maks=L[1]=10
ü  Tukar Maks dengan L[2], maka diperoleh
7                      2                      10                    12                    17

Pass 4: berdasarkan susunan array pada Pass 3
ü  Cari elemen maksimum di dalam array [0..1]. Maks=L[0]=6
ü  Tukar Maks dengan L[1], maka diperoleh
2                      7                      10                    12                    17

Jadi, saat ini array L sudah terurut sacara maximum ascending
Awal   :           12                    10                    17                    7                      2          
Pass 1  :           12                    10                     2                     7                      17
Pass 2  :           7                      10                    2                      12                    17
Pass 3  :           7                      2                      10                    12                    17
Pass 4  :           2                      7                      10                    12                    17

#Untuk mengurutkan array secara descending pada algoritma maximum selection caranya hampir sama seperti mengurutkan secara ascending, hanya saja urutannya dari yang terbesar ke yang terkecil.
Seperti;
Awal   :           10                    7                      12                    2                      17
Pass 1  :           17                    7                      12                    2                      10
Pass 2  :           17                    12                    7                      2                      10
Pass 3  :           17                    12                    10                    2                      7
Pass 4  :           17                    12                    10                    7                      2

  Ø  Contoh Sequence Algoritma Maximum Selection Sort
Untuk mendapatkan array yang terurut menaik (ascending), algoritma minimum selection sort dapat ditulis sebagai berikut :
  ü  Jumlah Pass = N-1 (jumlah pass)
  ü  cari elemen minimum (min) mulai dari elemen ke – I sampai elemen ke – (N-1)
  ü  pertukarkan min dengan elemen ke – I
  ü  Untuk setiap pass ke – I = 0,1,….., N-1,  lakukan :
Rincian setiap pass adalah sebagai berikut : 
Langkah 1       :           Cari elemen minimum di dalam L[0..(N-1)]
Pertukarkan elemen terkecil dengan elemen L[0]
Langkah 2       :           Cari elemen minimum di dalam L[1..(N-1)]
Pertukarkan elemen terkecil dengan elemen L[1]
Langkah 3       :           Cari elemen minimum di dalam L[2..(N-1)]
Pertukarkan elemen terkecil dengan elemen L[2]
Langkah N-1   :           Tentukan elemen minimum di dalam L[(N-2)..(N-1)]
Pertukarkan elemen terkecil dengan elemen  L[N-2]
(elemen yang tersisa adalah L[N-1], tidak perlu diurut karena hanya satu-satunya).
  Ø  Pseucode
 //I.S:array sudah berisi nilai integer yang belum terurut
//F.S:nilai-nilai dalam array terurut secara Ascending (atau Descending)
procedure v_minAsc(input/output A:array[0..4]of integer,
input N:integer)


  Ø  Deklarasi
k, min, j, temp:integer
  Ø  Algoritma:
                        for(k=0;k<=(N-2);kßk+1)       //for(k=(N-1);k>=1;kßk-1) untuk descending
                        //cari elemen terkecil
min ß k
for(j=(k+1);j<=(N-1);jßj+1)    //for(j=0;j<=k;jßj+1)untuk descending
if (A[j] < A[min])
min ß j
endif
endfor
v_Tukar(A[k],A[min])
endfor
  Ø  Sorting
Urutkan array berikut secara ascending, dengan algoritma minimum selection sort:
                        12                    10                    17                    7                      2
            Pass 1
ü  Cari elemen terkecil di dalam array L[0..4]. Min=L[4]=2
ü  Tukar Min dengan L[0], maka diperoleh
2                      10                    17                    7                      12
            Pass 2  berdasarkan susunan array pada Pass 1
ü  Cari elemen terkecil di dalam array L[1..4]. Min=L[3]=7
ü  Tukar Min dengan L[1], maka diperoleh
2                      7                      17                    10                    12
Pass 3  berdasarkan susunan array pada Pass 2
ü  Cari elemen terkecil di dalam array L[2..4]. Min=L[3]=10
ü  Tukar Min dengan L[2], maka diperoleh
2                      7                      10                    17                    12
Pass 4 berdasarkan susunan array pada Pass 3
ü  Cari elemen terkecil di dalam array L[3..4]. Min=L[3]=12
ü  Tukar Min dengan L[3], maka diperoleh
2                      7                      10                    12                    17
Jadi, saat ini array L sudah terurut sacara minimum ascending
Awal   :           12                    10                    17                    7                      2
Pass 1  :           2                      10                    17                    7                      1
Pass 2  :           2                      7                      17                    10                    12
Pass 3  :           2                      7                      10                    17                    12
Pass 4  :           2                      7                      10                    12                    17
#Untuk mengurutkan array secara descending pada algoritma minimum selection caranya hampir sama seperti mengurutkan secara ascending, hanya saja urutannya dari yang terbesar ke yang terkecil.
Seperti
Awal   :           10                    7                      12                    2                      17
Pass 1  :           10                    7                      12                    17                    2
Pass 2  :           10                    17                    12                    7                      2
Pass 3  :           12                    17                    10                    7                      2

Pass 4  :           17                    12                    10                    7                      2