Jumat, 31 Oktober 2008

Metode Pengurutan Data Dan program Array

Metode Pengurutan

Bubble Sort

Pengurutan gelembung adalah algoritma pengurutan yang paling tua dan sederhana untuk diimplementasikan. Algoritma ini juga cukup mudah untuk dimengerti.


Perhatikan bahwa jumlah pertukaran dan perbandingan data tidaklah tetap, perbedaan tergantung pada keadaan awal
data setelah diacak. Tabel berikut memperlihatkan tabulasi hasil visualisasi menggunakan metode bubble
sort. Pengacakan Jumlah Total
Pertukaran Data Perbandingan
Data 1 155279 2 127 272 3 137 245 4 142 297 5 151 294 6 138 285 7 178 300 8 165 272 9 156 285 10 175 300 Rata-rata 152 Jumlah rata-rata pertukaran untuk 10 kali pengacakan adalah 152 kali, sedangkan rata-rata jumlah perbandingan adalah
sebanyak 283 kali. Tetapi bila data pada awalnya terurut, maka untuk 25 jumlah data, jumlah pertukaran data sebanyak
0 kali dengan jumlah perbandingan sebanyak 24 kali.


Shell sort
Shell sort adalah algoritma dengan kompleksitas algoritma O(n2) dan yang paling efisien dibanding algoritma-algoritma lain dengan kompleksitas algoritma yang sama. Algoritma shell sort lima kali lebih cepat dibandingkan algoritma pengurutan gelembung dan dua kali lebih cepat dibandingkan algoritma pengurutan dengan penyisipan. Dan tentu saja shell sort juga merupakan algoritma yg paling yang paling kompleks dan sulit dipahami.
Algoritma shell sort melakukan pass atau traversal berkali-kali, dan setiap kali pass mengurutkan sejumlah nilai yang sama dengan ukuran set menggunakan insertion sort. Ukuran dari set yang harus diurutkan semakin membesar setiap kali melakukan pass pada tabel, sampai set tersebut mencakup seluruh elemen tabel. Ketika ukuran dari set semakin membesar, sejumlah nilai yang harus diurutkan semakin mengecil. Ini menyebabkan insertion sort yang dijalankan mengalami kasus terbaik dengan kompleksitas algoritma mendekati O(n). Ukuran dari set yang digunakan untuk setiap kali iterasi (iteration) mempunyai efek besar terhadap efisiensi pengurutan.
Tetapi, walaupun tidak se-efisien algoritma merge sort, heap sort, atau quick sort , algoritma shell sort adalah algoritma yang relatif sederhana. Hal ini menjadikan algoritma shell sort adalah pilihan yang baik dan efisien untuk mengurutkan nilai dalam suatu tabel berukuran sedang (mengandung 500-5000 elemen).


quick sort
Algoritma quick sort sangat sederhana dalam teori, tetapi sangat sulit untuk diterjemahkan ke dalam sebuah code karena pengurutan dilakukan dalam sebuah list dan diproses secara rekursif. Algoritma ini terdisi dari empat langkah (yang mana menyerupai merge sort) yaitu :
  • Memilih sebuah elemen untuk dijadikan poros atau pivot point (biasanya elemen paling kiri dari tabel).
  • Membagi tabel menjadi dua bagian, satu dengan elemen yang lebih besar dari poros, dan satu lagi untuk elemen yang lebih kecil dari poros.
  • Mengulang algoritma untuk kedua buah tabel secara rekursif.
Tingkat keefektifan dari algoritma ini dangat bergantung pada elemen yang dipilih menjadi poros. Kasus terburuk terjadi ketika tabel sudah terurut dan elemen terkecil di sebelah kiri menjadi poros. Kasus ini mempunyai kompleksitas algoritma O(n2). Maka dari itu sangat disarankan untuk memilih poros bukan dari elemen paling kiri dari tabel, tetapi dipilih secara random. Selama poros dipilih secara random, algoritma quick sort mempunyai kompleksitas algoritma sebesar O(n log n).


program array

Contoh Program :
Program Contoh_Array_Input;
Uses Crt;
Var
Bilangan : array[1..50] of Integer;
Begin
ClrScr;
Bilangan[1]:=3;
Bilangan[2]:=29;
Bilangan[3]:=30;
Bilangan[4]:=31;
Bilangan[5]:=23;
Writeln('nilai varibel bilangan ke 3 =',Bilangan[3]);
Readln;
End.

Array juga dapat dideklarasikan bersama dengan tipe yang beragam seperti contoh dibawah ini :
Program Contoh_Deklarasi_Array_Beragam;
Uses Crt;
Var
NPM : array[1..20] of string[10];
Nama : array[1..20] of string[25];
Nilai : array[1..20] of real;
Umur : array[1..20] of byte;
banyak,i : integer;
Begin
ClrScr;
Write('Isi berapa data array yang diperlukan :');Readln(banyak);
For i := 1 to banyak Do
Begin
Write('NPM =');Readln(NPM[i]);
Write('Nama =');readln(Nama[i]);
Write('Nilai=');readln(Nilai[i]);
Write('Umur =');readln(Umur[i]);
End;
{cetak varibel array}
Writeln('NPM NAMA NILAI UMUR ');
For i:= 1 to banyak Do
Begin
Writeln(Npm[i]:10,Nama[i]:25,Nilai[i]:3:2,' ',Umur[i]:3);
End;
Readln;
End.

Untuk deklarasi array dapat digunakan beberapa cara seperti berikut ini :
Type
Angka = String[20];
Var
Nama : Array [1..50] of Angka;
Begin
.
.
End.

Deklarasi tipe indeks subrange integer Indeks pada array dapat tipe skalar atau subrange, tetapi tidak bisa real.
Contoh:
Var
Nilai : Array[1..10] of Integer;
pada contoh ini array nilai mempunyai 10 buah elemen yaitu dari 1 sampai 10. Array tersebut dapat dideklarasikan dengan type seperti berikut ini :

Type
Skala = 1..10;
Var
Nilai : Array [skala] of Integer;
atau :
Type
Skala = 1..10;
Y = Array[skala] of Integer;
Var
Nilai : Y;
atau :
Type
Y = Array[1..10] of Integer;
Var
Nilai : Y;
atau :
Const
Atas =1;
Bawah = 5;
type
Y = Array[Atas..Bawah] of Integer;
Var
Nilai : Y;

I. Deklarasi Type Indeks Skalar
Indeks dari larik dapat berupa tipe skalar.
Contoh. :
Program Deklarasi_Indeks_Array_Skalar;
Uses Crt;
Var
Jum : Array[(jan,feb,mar,apr,mei)] of Integer;
Begin
Jum[jan]:=25;
Jum[feb]:=45;
Jum[mar]:=21;
Jum[apr]:=23;
Jum[mei]:=50;
Writeln('Jumlah nilai bulan maret =',Jum[mar]);
Readln;
End.
dapat juga ditulis :
type
Bln = (jan,feb,mar,apr,mei);
Var
Jum : Array[bln] of Integer;
atau :
type
Bln =(jan,feb,mar,apr,mei);
Var
Jum : Array[jan..mei] of Integer;

II. Deklarasi Konstanta Array
Array tidak hanya dapat berupa suatu varibel yang dideklarasikan di bagian deklarasi variabel, tetapi dapat juga berupa konstanta (const).
Contoh Program :
Program Contoh_Deklarasi_Array_Konstan;
Uses Crt;
Const
Tetap : Array[1..4] of Integer=(7,10,21,20);
Var
i : Integer;
Begin
For i:= 1 to 4 Do
Writeln('Nilai Konstan array ke ',i:2,' =',Tetap[i]);
Readln;
End.
konstanta array dapat juga berupa ketetapan dalam bentuk karakter seperti berikut.
Contoh Program :
Program Contoh_Konstan_Array_Char_;
Uses Crt;
Const
Huruf : Array[0..5] of Char=('A','B','C','D','E','F');
Var
i : Integer;
Begin
For i:= 0 to 5 Do
Writeln('Nilai konstan array ke',i:2,' = ',Huruf[i]);
Readln;
End.
Konstanta array dapat juga berupa string seperti berikut ini.
Contoh Program :
Program Constanta_Array_String;
Uses Crt;
Type
A = Array [1..5] of String;
Const
Nama : A = ('basic','pascal','cobol','paradox','dbase');
Var
i : Integer;
Begin
For i:= 1 to 5 Do
Writeln('Nilai Array ke-',i:2,'= ',Nama[i]);
readln;
end.

Dalam pascal string merupakan array dari elemen- elemen karakter seperti berikut :
Contoh Program :
Program String_Adalah_Array_Tipe_Char;
Uses Crt;
Var
Nama : string;
i : Integer;
Begin
Nama:='Turbo Pascal';
For i:= 1 to Length(nama) Do
Writeln('Elemen ',i,' dari ',Nama,'= ',Nama[i]);
Readln;
End.

contoh program bilangan prima dengan menggunakan bantuan array.
Contoh program :
Program Mencari_Bilangan_Prima_Dengan_Array;
Uses Crt;
Var
Prima : Array[1..100] of Integer;
i,j : Integer;
bil : Integer;
Begin
ClrScr;
For i := 2 to 100 Do
Begin
Prima[i]:=i;
For j:= 2 to i-1 Do
Begin
bil := (i mod j); {* i dibagi j dicek apakah 0*}
If bil = 0 then Prima[i]:=0; {*jika habis dibagi,berarti bkn prima*}
End;
If Prima[i]<> 0 Then Write(Prima[i],' '); {*cetak array yg prima*}
End;
Readln;
End.

Contoh pengurutan data dengan metode buble sort, yaitu dengan cara penukaran, dapat dilihat pada contoh dibawah ini :
Contoh Program :
Program Penggunaan_Array_Untuk_Sortir_Buble_Sort;
Uses Crt;
Var
nil1 : Array[1..100] of Integer;
n,i,j,dum : Integer;
Begin
ClrScr;
Write('mau isi berapa data acak (integer) ='); readln(n);
For i := 1 to n Do
Begin
Write('Data Ke ',i,':');Readln(nil1[i]);
End;
{* penyapuan proses}
for i:= 1 to n-1 do
begin
for j:= i to n do
begin
if nil1[j]
begin
dum:=nil1[j];
nil1[j]:=nil1[i];
nil1[i]:=dum;
end;
end;
end;
writeln;
writeln('Hasil Sortir');
for i := 1 to n do
write(nil1[i]:3);
readln;
end.


III. Array Dua Dimensi
Di dalam pascal Array dapat berdimensi lebih dari satu yang disebut dengan array dimensi banyak (Multidimensional array), disini akan dibahas array 2 dimensi saja. Array 2 dimensi dapat mewakili suatu bentuk tabel atau matrik, yaitu indeks pertama menunjukkan baris dan indeks ke dua menunjukkan kolom dari tabel atau matrik.
1 2
1 2 3
Untuk mengetahui cara mendeklarasikan dari penggunaan aray dua dimensi dapat dilihat pada listing program dibawah ini .

Contoh Program:
Program Deklarasi_Array_Dua_Dimensi;
Uses Crt;
Var Tabel : Array[1..3,1..2] of Integer;
i,j : Integer;
Begin
ClrScr;
Tabel[1,1]:=1;
Tabel[1,2]:=2;
Tabel[2,1]:=3;
Tabel[2,2]:=4;
Tabel[3,1]:=5;
Tabel[3,2]:=6;
For I := 1 to 3 Do Begin For J:= 1 to 2 Do Begin Writeln('Elemen ',i,',',j,'= ',tabel[i,j]);
End;
End;
Readln;
End.


IV. Alternatif Deklarasi Array Dua Dimensi.
Ada beberapa cara dalam mendeklarasikan array dua dimensi, beberapa cara tersebut dapat dilihat dibawah ini :
Contoh :
Var
Tabel : Array[1..3] of Array[1..2] of Byte;
atau :
Type
Matrik = Array[1..3,1..2] of Byte;
Var
Tabel : Matrik;
atau :
Type
Baris = 1..3;
Kolom = 1..2;
Matrik = Array[Baris,Kolom] of Byte;
Var
Tabel : Matrik;
atau :
Type
Baris = 1..3;
Kolom=1..2;
Matrik= Array[Baris] of Array[Kolom] of Byte;
Var
Tabel : Matrik;
Dibawah ini akan diberikan listing program penggunaan array dua dimensi dalam aplikasi penjumlahan matrik :
Contoh Prorgam:
Program Penjumlahan_Matrik;
Uses Crt;
Var
Matrik1,Matrik2, Hasil : Array[1..3,1..2] of Integer;
i,j : Integer;
Begin
ClrScr;
{ input matrik ke satu }
Writeln(' Elemen matrik satu');
For i := 1 to 3 Do
Begin
For j := 1 to 2 Do
Begin
Write('Elemen baris -',i,' Kolom -',j,'= ');
Readln(matrik1[i,j]);
End;
End;
{input matrik ke dua}
Writeln('input elemen matrik dua');
For i:= 1 to 3 Do
Begin
For j:= 1 to 2 Do
Begin
Write('Elemen baris -',i,' kolom -',j,'= ');
Readln(matrik2[i,j]);
End;
End;
{proses penjumlahan tiap elemen}
For i := 1 to 3 Do
Begin
For j:= 1 to 2 Do
Begin
Hasil[i,j]:=Matrik1[i,j]+Matrik2[i,j];
End;
End;
{proses cetak hasil}
For i:= 1 to 3 Do
Begin
For j:= 1 to 2 Do
Begin
Write(Hasil[i,j]:6);
End;
Writeln;
End;
Readln;
End.


V. Array Sebagai Parameter
Array dapat digunakan sebagai parameter yang dikirimkan baik secara nilai (by value) atau secara acuan (by reference) ke procedure atau ke function. Procedure yang menggunakan parameter berupa array harus dideklarasikan di dalam judul procedure yang menyebutkan parameternya bertipe array.

Contoh Program :
Program Contoh_Pengiriman_Parameter_Array_Di_Procedure;
Uses Crt;
Const
Garis ='---------------------------------------------------';
Type
Untai = Array[1..10] of String[15];
Bulat = Array[1..10] of Integer;
Huruf = Array[1..10] of Char;
Var
i,Banyak : Integer;
Procedure Proses(Nama:Untai;Nilai:Bulat);
Var
Ket : String;
Abjad : Char;
Begin
Writeln(Garis);
Writeln('Nama Nilai Abjad Keterangan');
Writeln(Garis);
For i := 1 to Banyak Do
Begin
If Nilai[i] > 90 Then
Begin
Abjad:='A';
Ket :='Istimewa';
End;
If (Nilai[i]<90)>70) Then
Begin
Abjad:='B';
Ket :='Memuaskan';
End;
If (Nilai[i]<70)>60) Then
Begin
Abjad:='C';
Ket :='Cukup';
End;
If (Nilai[i]<60)>45) Then
Begin
Abjad:='D';
Ket :='Kurang';
End;
If Nilai[i]< 45 Then
Begin
Abjad:='E';
Ket :='Sangat kurang';
End;
Writeln(Nama[i]:15,' ',Nilai[i]:4,' ',Abjad,' ',Ket:15);
End;
Writeln(Garis);
End;
Procedure Masuk_Data;
Var
Nama : Untai;
Nilai : Bulat;
Begin
Write('Banyak data =');Readln(Banyak);
For i:= 1 to Banyak Do
Begin
ClrScr;
Writeln('Data ke - ',i);
Write('Nama =');readln(Nama[i]);
Write('Nilai =');readln(Nilai[i]);
End;
Proses(Nama,Nilai);
End;
{modul Utama}
Begin
Masuk_Data;
Readln;
End.