Hai guys kali ini saya akan membagikan tentang Sorting dalam Pemrograman di Algoritma. Pemrograman memanglah sulit dan rumit. Tapi jika dipelajari dengan telaten maka akan menjadi mudah bagi yang sudah menjalankannya. Berikut penjelasan tentang Sorting Dalam Algoritma Dan Struktur Data.
Pengertian
Sorting
Sorting atau pengurutan data adalah
proses untuk menyusun kumpulan data yang seragam menjadi susunan tertentu.
Kumpulan data diurutkan secara Ascending (Urut Menaik), yaitu dari data yang
nilainya secara Descending (Urut Menurun), yaitu dari data yang nilainya paling
besar sampai data yang nilainya paling kecil.
Metode – metode Sorting :
a) Bubble
Sort
Pengurutan model ini mengambil ide dari gelembung air, yaitu
mengapungkan elemen yang bernilai kecil dari bawah ke atas. Proses pengapungan
dilakukan dengan pertukaran elemen-elemen tabel.
Apabila kita menginginkan array terurut menaik, maka elemen
array yang berharga paling kecil “diapungkan” artinya diangkat ke “atas” (atau
ke ujung kiri array) melalui proses pretukaran. Proses pengapungkan ini
dilakukan sebanyak n-1 langkah (satu langkah disebut satu kali pass) dengan n
adalah ukuran array.
program arh_bsort_menaik;
uses crt;
var i,n,j : integer;
a: array [1..100] of integer;
procedure buble;
var z: integer;
begin
for i:= 1 to n-1 do
begin
for j:= n downto i+1 do
begin
if a[j] < a[j-1] then
begin
z:= a[j];
a[j]:= a[j-1];
a[j-1]:=z;
end;
end;
end;
end;
begin
write('masukkan banyak larik (maks
100) : '); readln(n);
for i:= 1 to n do
begin
write('A[',i,'] : '); readln(a[i]);
end;
buble;
write('data setelah diurutkan
: ');
for j:=1 to n do
write (a[j],' ');
end.
Algoritma bubble sort dapat
diringkas sebagaiberikut, jika N adalah panjang elemen struktur data, dengan
elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:
1.
Lakukan traversal untuk membandingkan dua elemen berdekatan.
Traversal ini dilakukan dari belakang.
2.
Jika elemen pada TN-1 > TN , maka lakukan pertukaran
(swap). Jika tidak, lanjutkan ke proses traversal berikutnya sampai bertemu
dengan bagian struktur data yang telah diurutkan.
3.
Ulangi langkah di atas untuk struktur data yang tersisa.
b) Insertion sort
Salah
satu algoritma sorting yang paling sederhana adalah insertion sort.
Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan
berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam
pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu
yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan
pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan
dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana
kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada
pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua
dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua,
kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut
akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan
berurutan pada meja kedua.
Algoritma
insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen
yang tersisa pada bagian array yang belum diurutkan.
Algoritma
void insertionSort(Object array[], int
startIdx, int endIdx) { for (int i = startIdx; i < endIdx; i++) {
int k = i;
for (int j = i +
1; j < endIdx; j++) {
if (((Comparable)
array[k]).compareTo(array[j])>0) { k = j;
}
}
swap(array[i],array[k]);
}
}
Sebuah
Contoh
Data
|
1st
Pass
|
2nd
Pass
|
3rd
Pass
|
4th
Pass
|
||||
Mango
|
Mango
|
Apple
|
Apple
|
Apple
|
||||
Apple
|
Apple
|
Mango
|
Mango
|
Banana
|
||||
Peach
|
Peach
|
Peach
|
Orange
|
Mango
|
||||
Orange
|
Orange
|
Orange
|
Peach
|
Orange
|
||||
Banana
|
Banana
|
Banana
|
Banana
|
Peach
|
||||
Gambar
1.1.2: Contoh insertion sort
Contoh
lainnya:
uses crt;
var
jmldata,i,j:integer;
data,x:array [1..100] of integer;
procedure asc_insert;
var temp:integer;
begin
For
i := 2 to jmldata do
Begin
Temp
:=data[i];
j
:= i-1;
while
(data[j] > temp) and (j>0) do
begin
data[j+1]
:= data[j];
dec(j);
end;
data[j+1]:=temp;
end;
writeln('data yang telah di urut');
for i:=1 to jmldata do
begin
write(data[i],' ');
end;
readln;
end;
begin
clrscr;
write('masukkan berapa angka yang
akan di urut: '); readln(jmldata);
for i:=1 to jmldata do
begin
write('masukkan angka ke-',i,':'); readln(data[i]);
end;
asc_insert;
readln;
end.
c) Quick
sort
Membandingkan suatu elemen (disebut pivot) dengan elemen
yang lain dan menyusunnya sedemikian rupa sehingga elemen- elemen lain yang
lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan
elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah
kanannya. Sehingga dengan demikian telah terbntuk dua sublist, yang terletak di
sebelah kiri dan kanan dari pivot. Lalu pada sublist kiri dan sublist kanan
kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti
sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi.Sehingga
didalamnya telah terjadi proses Rekursif.
Sebagai bonus dapat bonus
program download lewat mediafre.com, program ini dengan beberapa pengurutan
diantaranya:
1]Pengurutan secara BubbleSort;
2]Pengurutan secara SelectionSor;
3]Pengurutan secara InsertionSort’);
1]Pengurutan secara BubbleSort;
2]Pengurutan secara SelectionSor;
3]Pengurutan secara InsertionSort’);
Quicksort ditemukan
oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini jugaberdasar
pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini
hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
Memilah rangkaian data menjadi dua
sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang
dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar
atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot.
Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
2.
Conqsuer
Mengurutkan
elemen pada sub-rangkaian secara rekursif
Contoh
dari proses Soring dengan menggunakan metode Quick Sort
Dalam
Procedure Pascal :
Procedure Quick(Var Temp : Data;
Awal, Akhir : Integer);
Var I,J :
Integer;
Procedure
ATUR;
Begin
I:=Awal +1;
J:= Akhir;
While Temp[I] < Temp[Awal] Do Inc(I);
While Temp[J] > Temp[Awal] Do
Dec(J);
While I < J Do
Begin
SWAP(Temp[I], Temp[J]);
While Temp[I] < Temp[Awal] Do Inc(I);
While Temp[J] > Temp[Awal] Do Dec(J);
End;
SWAP(Temp[Awal], Temp[J]);
End;
Begin
If Awal < Akhir Then
Begin
ATUR;
Quick(Temp, Awal, J-1);
Quick(Temp,J+1,Akhir);
End;
End;
d) Shel
short
Metode ini di kembangkan oleh Donald L (kayak kue). shell
pada tahun 1959. Dalam metode ini jarak antara dua elemen yang di bandingkan
dan ditukarkan tertentu. secara singkat metode ini dijelaskan sebabagi berikut:
Pada langkah pertama, kita mengambil
elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari
elemen pertama tersebut. kemudian elemen kedua kita bandingkan dengan element
lain dengan jarak yang sama seperti diatas. Demikian seterusnya sampai seluruh
elemen di bandingkan. pada langkah kedua proses diulang dengan langkah yang
lebih kecil, pada langkah ketiga jaraktersebut diperkecil lagi seluruh proses
dihentikan jika jarak sudah sama dengan satu (=1)!
contoh
procedure Shellshort pada pascal:
var I,J, jarak:integer;
begin
jarak:=jmlData Div 2;
while Jarak>0 do
begin
for i:=1 to jmlData- jarak Do
begin
j:=i+jarak;
if Temp[i]> temp [j] then
Swap(temp[i], Temp [lok]);
end;
jarak:=jarak div 2;
end;
end;
Untuk program utamanya bisa kan buat sendiri?? dan untuk
pemanggilan programnya bisa juga kan buat sendiri?? dan untuk SWAP (temp[i],
Temp [lok]) itu adalah sebuah prosedur lagi, dimana dalam prosedur tersebut
di lakukan pertukaran. sebenarnya bisa saja sobat langsung membuat procedure
swap ini dalam procedure shellsort. so, berikut adalah procedurenya:
procedure Swap(var a,b :char);
begin
temp:=a;
a:=b;
b:=temp;
end;
end;
Demikian Sorting Dalam Algoritma Dan Struktur Data. Semoga bermanfaat!
No comments:
Post a Comment