Selasa, 10 Mei 2011

SORTING


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 :
1
n
Belum terurut

        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.

Diposting oleh di

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)