Join With Me On Twitter

Join With Me On Twitter : @supersahrul

Kamis, 15 Oktober 2009

Pengurutan (array) dalam Turbo Pascal

I. Judul Praktikum : Pengurutan (array)
II. Tujuan Praktikum :
1. Untuk mengetahui macam-macam metode dalam pengurutan.
2. Dapat mengetahui kelebihan dan kelemahan metode pengurutan.
3. Untuk mengetahui metode mana yang lebih baik dan mudah untuk digunakan
III. Dasar Teori
Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu dan proses yang sering harus dilakukan dalam pengolahan data dan proses mengatur sekumpulan objek menurut aturan atau susunan tertentu (WIR76). Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.Pengurutan objek tersebut dapat dilakukan secara ascending (urut naik) dan descending (urut turun). Bila n buah objek (atau data) dismpan dalam larik L, maka pengurutan menaik berarti menyusun elemen larik sedemikian sehingga :
L[1] ≤ L[2] ≤ L[3 ≤ … ≤ L[N]
Sedangkan pengurutan menurun berarti menyusun lemen larik sedemikian sehingga :
L[1] ≥ L[2] ≥ L[3 ≥ … ≥ L[N]
Data yang diurut dapat berupa data bertipe dasar atau bertipe terstruktur (record). Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai field kunci.
Berikut ini diberikan beberapa contoh data terurut:
(i) 23, 27, 45, 67, 100, 130, 501
(data bertipe integer menaik)
(ii) 50, 27, 31.009, 20.3, 19.0, -5.2, -10.9
(data bertipe riil terurut menurun)
(iii) ‘d’, ‘e’, ‘g’, ‘i’, ‘x’
(data bertipe karakter terurut menaik)
(iv) ‘Amir’, ‘Badu’, ‘Budi’, ‘Dudi’, ‘Eno’, ‘Rudi’, ‘Zamzani’
(data bertipe string terurut menaik)
(v) <13596001, ‘Eko’, ‘A’>, <13596006, ‘Rizka’, ‘B’>,
<13596007, ‘Hamdi’, ‘D’>, <13596010, ‘Rizal, ‘C’>,
<13596012, ‘Ratna’, ‘A’>
(data mahasiswa bertipe terstruktur terurut menaik berdasarkan field NIM)

Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
DEKLARASI ARRAY UNTUK SORTING
Deklarasikan:
int data[100];
int n; //untuk jumlah data
Fungsi untuk Tukar 2 Buah Data:
void tukar(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
Metode-metode Pengurutan Data
Adanya kebutuhan terhadap proses pengurutan memunculkan berbagai macam metode pengurutan. Banyak metode pengurutan yang telah ditemukan. Hal ini menunjukkan bahwa persoalan pengurutan adalah persoalan yang kaya dengan solusi algoritmik. Metode pengurutan yang ditemukan didalam literatur-literatur komputer antara lain :
1. Bubble Sort
2. Selection Sort (Maximum Sort dan Minimum Sort)
3. Insertion Sort
4. Heap Sort
5. Shell Sort
6. Quick Sort
7. Merge Sort
8. Radix Sort
9. Tree Sort
Pada materi ini tidak akan membahas semua metode pengurutan tersebut, tetapi hanya empat buah metode pengurutan yang sederhana saja, yaitu:
1. Metode Pengurutan Apung (Bubble Sort)
2. Metode Pengurutan Seleksi (Selection Sort)
3. Metode Pengurutan Sisipan (Insertion Sort)
4. Metode Pengurutan Shell (Shell Sort)
Untuk setiap metode pengurutan akan ditulis algoritmanya. Dua metode pertama (bubble dan selection sort) melakukan prinsip pertukaran elemen dalam proses pengurutan sehingga keduanya dinamakan pengurutan dengan pertukaran (exchange sort), sedangkan dua metode terakhir melakukan prinsip geser dan sisip elemen dalam prose pengurutan (shift and insert sort). Semua metode pengurutan selalu melakukan operasi perbandingan elemen larik untuk menemukan posisi urutan yang tepat.
• Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort, exchange sort
• Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
• Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and
keep sorted method)
• Insertion sort, tree sort
• Pengurutan berdasarkan pembagian dan penguasaan (devide and
conquer method)
• Quick sort, merge sort
• Pengurutan berkurang menurun (diminishing increment sort method)
• Shell sort
Metode pengurutan juga dapat diklasifikasikan sebagai metode pengurutan internal dan metode pengurutan eksternal.
1. Metode pengurutan internal, yaitu metode pengurutan untuk data yang disimpan di dala memori komputer. Umumnya struktur internal yang dipakai untuk pengurutaninternal adalah larik, sehingga pengurutan internal disebut juga pengurutan larik.
2. Metode pengurutan eksternal, yaitu metode pengurutan untuk data yang disimpan di dalam disk storage, disebut juaga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.

A. Metode Pengurutan Apung (Bubble Sort)
Metode pengurutan apung (bubble sort) diinspirasi oleh gelembung sabun yang berada di atas permukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan.
Metode sorting termudah. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar. Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan kekiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Prosedur Bubble Sort
Versi 1
void bubble_sort(){
for(int i=1;i for(int j=n-1;j>=i;j--){
if(data[j] tukar(&data[j],&data[j-1]); //ascending
}
}
}
Versi 2
void bubblesort2(){
for(i=1;i<6;i++){
for(int j=0;j<6-i;j++){
if(data[j]>data[j+1])
tukar(&data[j],&data[j+1]); //descending
}
}
}
Dengan prosedur diatas, data terurut naik (ascending), untuk urut turun
(descending) silhkan ubah bagian:
if (data[j]Menjadi:
if (data[j]> data[j-1]) tukar(&data[j],&data[j-1]);
Komentar Mengenai Pengurutan Apung
Pengurutan apung merupakam metode pengurutan yang tidak mangkus (efficient). Hal ini disebabkan oleh banyaknya operasi pertukaran yang dilakukan pada setiap langkah pengapungan. Untuk ukuran larik yang besar, pengurutan dengan metode ini membutuhkan waktu yang lama. Karena alasan itu, maka metode pengurutan apung jarang digunakan dalam praktek pemrograman. Namun, kelebihan metode ini adalah pada kesederhanaannya sederhana dan mudah dipahami.

B. Metode Pengurutan Seleksi (Selection Sort)
Metode pengurutan ini disebut pengurutan seleksi karena gagasan dasarnya adalah memilih elemen maksimum/ minimum dari larik, lalu menempatkan elemen maksimum/ minimum pada awal atau akhir larik dan merupakan kombinasi antara sorting dan searching.
Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
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. Misalkan larik L dengan N=6 sebagai berikut:

Maka langkah-langkah pengurutannya adalah:

Contoh algoritma :
Procedure SelectionSort(input/output L : Larikint, input N : integer)
{mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan maksimum}
{k.awal : elemen larik L sudah terdefinisi harganya}
{k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤... ≤ L[N]}

Deklarasi
I : integer
J : integer {pencacah untuk mencari nilai maksimum}
Imaks : integer {indeks yang berisi nilai maksimum sementara}

Procedure tukar(input/output A : integer, input/output : B : integer)
{mempertukarkan nilai A dan B}
Deskripsi
For I ← N downto 2 do {jumlah pengulangan sebanyak N-1}
{cari elemen maksimum pada elemen L[1..I]}
Imaks ← I {elemen pertama diasumsikan sebagai elemen maksimum sementara}
For J ← 2 to I do
If L[J] > L[Imaks] then
Imaks ← J
Endif
Endfor {pertukarkan L[Imaks] dengan L[I]}
Tukar(L[Imaks], L[I])
Endfor

2.Algoritma pengurutan seleksi-minimum, yaitu memilih elemen minimum sebagai basis pengurutan. Misalkan larik L dengan N=6 sebagai berikut:

maka langkah-langkah pengurutannya adalah:

Contoh algoritma :
Procedure SelectionSort(input/output L : larikint, input N : integer)
{mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan pilih minimum}
{k.awal : elemen larik L sudah terdefinisi harganya}
{k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤... ≤ L[N]} Deklarasi I : integer
J : integer {pencacah untuk mencari nilai maksimum}
Imin : integer {indeks yang berisi nilai maksimum sementara}

Procedure Tukar(input/output A : integer, input/output : B : integer)
{mempertukarkan nilai A dan B}
Deskripsi
For I ← 1 to N-1 do {cari indeks dari elemen minimum di dalam larik L[I..N]}
Imin ← I
For J ← I+1 to N do
If L[J] > L[Imin] then
Imin ← J
Endif
Endfor {pertukarkan L[Imin] dengan L[I]}
Tukar(L[Imin], L[I])
Endfor

Prosedur Selection Sort
void selection_sort(){
for(int i=0;i pos = i;
for(int j=i+1;j if(data[j] < data[pos]) pos = j; //ascending
}
if(pos != i) tukar(pos,i);
}
}
Komentar Mengenai Metode Pengurutan Seleksi
Dibanding dengan metode pengurutan apung, metode pengurutan seleksi memiliki kinerjayang lebih baik. Alasannya, operasi pertukaran elemen hanya dilakukan sekali saja pada setiap pass, dengan demikian lamanya pengurutannya berkurang dibandingkan dengan metode pengurutan gelembung.

C. Metode Pengurutan Sisipan (Insetion Sort)
Pengurutan sisipan adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencairan posisi yang tepat dilakukan dengan cara menyisir elemen larik. Selama penyisiran dilakukan pergeseran elemen larik. Metode pengurutan sisip cocok untuk persoalan menyisipkan elemen baru ke dalam sekumpulan elemen yang sudah yang terurut.
Pada metode ini elemen terbagi menjadi 2 bagian yaitu kelompok sumber yang merupakan susunan asli dari kelompok tersebut (belum terurut) yaitu dari A1…..AN dan kelompok yang kedua adalah kelompok tujuan yaitu susunan elemen yang telah terurut dengan urutan dari A1….Ai -1. Langkah penyisipan dimulai dari i = 2 dengan pertambahan 1. Elemen ke i diambil dari kelompok sumber dan akan dipindahkan ke kelompok tujuan dengan cara menyisipkannya pada tempatnya yang sesuai.
Algoritma metode sisip langsung :
- langkah 0 : Baca vector yang akan diurutkan (dalam program utama)
- langkah 1 : Kerjakan langkah 2 sampai 5 untuk i = 2 sampai dengan N
- langkah 2 : Tentukan : T = A[i] (elemen yang akan disisipkan), A[0] = T (data sentinel) dan j = i -1.
- langkah 3 : (lakukan pergeseran). Kerjakan langkah 4 selama T < A[j]
- langkah 4 : Tentukan : A[j + 1] = A[j] dan j = j -1.
- langkah 5 : Tentukan : A[j + 1] = T
- langkah 6 : Selesai
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
Prosedur Insertion Sort
void insertion_sort(){
int temp;
for(int i=1;i temp = data[i];
j = i -1;
while(data[j]>temp && j>=0){
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
Komentar mengenai metode pengurutan sisipan
Kelemahan metode pengurutan sisipan terletak pada banyaknya operasi pergeseran yang dilakukan dalam mencari posisi yang tepat untuk elemen larik. Pada setiap pass i, opeasi pergeseran yang diperlukan maksimum i -1 kali. Untuk larik yang berukuran besar, jumlah operasi pergeseran meningkat secara kuadratik, sehingga pengurutan sisip kurang bagus untuk volume data yang besar.
D. Metode Pengurutan Shell (Shell Sort)
Metode ini merupakan perbaikan terhadap metode pengurutan sisipan. Kelemahan metode pengurutan sisipan sudah disebutkan pada bagian sebelumnya. Jika data pada posisi ke-1000 ternyata posisi yang tepat adalah sebagai elemen kedua, maka dibutuhkan kira-kira 998 kali pergeseran elemen.
Untuk mengurangi pergeseran terlalu jauh, kita mengurutkan larik setiap k elemen dengan metode pengurutan sisip, misalkan kita urutkan setiap 5 elemen (k kita namakan juga step atau increment). Selanjutnya, digunakan nilai step yang lebih kecil, misalnya k = 3, lalu diurut setiap 3 elemen. Begitu seterusnya sampai nilai k = 1. Karena nilai step selalu berkurang maka metode pengurutan Shell kadang – kadang dinamakan juga metode pengurutan kenaikan berkurang (diminishing increment sort)
Komentar mengenai metode pengurutan shell
Metode pengurutan shell merupakan perbaikan terhadap metode pengurutan sisipan. Namun tidak seorangpun yang pernah dapat menganalisis metode pengurutan shell secara tepat, karena pemilihan ukuran step (seperti 5, 3, 1, atau pendefinisian ukuran tep dengan pernyataan step = step div 3+ 1) didasarkan pada pertimbangan sugesti.
Tidak ada aturan yang diketahui untuk menemukan ukuran step yang optimum. Jika step yang dipilih berdekatan, semakin banyak jumlah pass yan g dihasilkan, tapi setiap pass mungkin lebih cepat. Jika ukuran step menurun dengan cepat, jumlah pass akan berkurang tetapi setiap pass menjadi lebih panjang (lama).

IV. Algoritma

Type
Larik= array [1..100] of integer ;
Deklarasi
n : integer
x : integer
i : integer
L : Larik
ketemu:boolean {pertanda untuk menentukan apakah x ditemukan}
Procedure bagi_dua(input L: Larikint, input n: integer, input x : integer,output idx : integer, var ketemu:boolean)
Deklarasi
i, j : integer { indeks kiri dan indeks kanan larik}
k : integer { indeks elemen tengah }
Idx:integer
i← 1 {ujung kiri larik}
j ← n (ujung kanan larik}
Ketemu ← false {asumsikan x belum ditemukan}
While (not Ketemu) and (I <= J) do
k ← (i + j) div 2 (bagi dua larik L pada posisi k}
If L[k] = x then
{lakukan pencarian pada larik bagian kanan, set indeks ujung kiri larik yang baru}
Ketemu ← true
Idx ← k
Else
If (L[k] > x) then
J ← k - 1
Else
{lakukan pencarian pada larik bagian kiri, set indeks ujung kanan larik yang baru}
I ← k + 1
Endif
Endif
Endwhile
{ketemu = true or i > j}
If (ketemu) then { x ditemukan}
Idx← k
Else { x tidak ditemukan dalam larik }
Idx← -1
End if














V. Program

Program Searching ;
Uses wincrt;
Type
Larik= array [1..100] of integer ;
Var
N : integer;
X : integer;
i : integer;
L : Larik;
ketemu:boolean;
Procedure bagi_dua(N : integer;var ketemu:boolean);
Var
I, J : integer;
K : integer;
Idx:integer;
Begin
I := 1;
J := N;
Ketemu := false;
While (not Ketemu) and (I <= J) do
Begin
K := (I + J) div 2 ;
If L[K] = X then
Begin
Ketemu := true;
Idx := K;
End
Else
Begin
If (L[K] > X) then
J := K - 1
Else
I := K + 1 ;
End;
End;
End;
Begin
write ('Masukan Jumlah Data = '); readln (N);
for i:=1 to N do
begin
write ('Masukan Data = '); readln (L[i]);
end;
write('Masukan Data yang Dicari = '); readln (X);
bagi_dua(N,ketemu);
if ketemu then
write ('Data yang Anda Cari Ada')
else
write('Maaf, Data yang Anda Cari Tidak Ada. Coba Ulangi Lagi') ;
end.










Tidak ada komentar:

Poskan Komentar