Algoritma sorting
D
I
S
U
S
U
n
OLEH
Nama : ISWAHYUNI
Mata Kuliah : Struktur Data
NPM : 1111706
STMIK BUDIDARMA MEDAN
TA 2011-2012
Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat dua jenis pengurutan :
- Ascending (Naik).
Contoh : 2,3,10,15,22
- Descending (Turun).
Contoh : 22,15,10,3,2
Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.
1. Bubble Sort
2. Selection Sort
3. Merge Sort
4. Heap Sort
5. Shaker Sort
Metode Pengurutan Data
Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort
Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)
• Merge Sort
Pengurutan berkurang menurun (diminishing increment sort method)
1. BUBBLE SORT
Metode ini merupakan metode yang paling sederhana dan paling tidak efisien, karena memerlukan waktu yang relatif lebih lama dibandingkan dengan metode - metode yang lainnya. Konsep dasar dari Bubble sort ialah membandingkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang > elemen berikutnya (untuk ascending), maka dilakukan proses penukaran. Proses sorting dapat dimulai dari data awal atau data akhir.
Idenya adalah :
¨ Lakukan pengulangan ( pass ) pada array, tukar elemen yang bersebelahan jika diperlukan ( perbandingan nilainya tidak sesuai ); jika tidak ada pertukaran elemen maka array sudah terurut.
¨ Dalam pass pertama, temukan elemen dengan nilai tertinggi ( maksimal ) dalam array dan tukarkan dengan elemen di sebelah kanannya dan seterusnya sampai dengan mencapai posisinya di ujung array sebelah kanan.
¨ Kemudian dalam pass kedua, nilai tertinggi kedua dalam array akan ditempatkan dalam posisinya ( di sebelah kiri elemen dengan nilai tertinggi ( maksimal ).
¨ Teruskan langkah ketiga sampai semua elemen array terurut.
Berikut ini merupakan Procedure BubbleSort pada Pascal :
Procedure Bubble( Var Temp : Data; JmlData : Integer);
Var I,J : Integer;
Begin
For I:=1 To JmlData Do
For J:=JmlData DownTo I Do
If Temp[J] < Temp[J-1] Then {Untuk Descending >}
SWAP à Temp = a[J-1];
a[J-1] = a[J];
a[J] = Temp;
End;
|
Iterasi
Ke
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
Awal
|
22
|
10
|
15
|
3
|
2
|
1
|
10
|
22
|
15
|
3
|
2
|
10
|
15
|
22
|
3
|
2
| |
10
|
15
|
3
|
22
|
2
| |
10
|
15
|
3
|
2
|
22
| |
2
|
10
|
15
|
3
|
2
|
22
|
10
|
3
|
15
|
2
|
22
| |
10
|
3
|
2
|
15
|
22
| |
10
|
3
|
2
|
15
|
22
| |
3
|
3
|
10
|
2
|
15
|
22
|
3
|
2
|
10
|
15
|
22
| |
3
|
2
|
10
|
15
|
22
| |
3
|
2
|
10
|
15
|
22
| |
4
|
2
|
3
|
10
|
15
|
22
|
2
|
3
|
10
|
15
|
22
| |
2
|
3
|
10
|
15
|
22
| |
2
|
3
|
10
|
15
|
22
| |
5
|
2
|
3
|
10
|
15
|
22
|
2
|
3
|
10
|
15
|
22
| |
2
|
3
|
10
|
15
|
22
| |
2
|
3
|
10
|
15
|
22
| |
Akhir
|
2
|
3
|
10
|
15
|
22
|
Di sini terlihat ketidakefisienan dari bubble sort yaitu harus menyelesaikan JumMax –1 dari data. Sedangkan jika kita melihat dari tabel diatas pada iterasi ke empat saja data sudah terurut dan seharusnya pada saat itu proses sudah berhenti, tapi dengan bubble sort proses harus dilakukan sampai looping selesai.
Pada seluruh prosedur yang menggunakan metode sorting pasti memerlukan prosedur tambahan tukar data (Swap) untuk menukarkan dua buah elemen dalam data. Berikut ini merupakan prosedur untuk menukarkan dua buah data.
2. SELECTION SORT
Mirip dengan bubble sort, namun algoritma ini lebih sedikit usaha untuk menempatkan setiap elemen ke posisinya.
Idenya :
¨ Pertama temukan elemen array terkecil ( minimum ) dan pertukarkan dengan elemen array di posisi ( indeks ) pertama
¨ Kemudian temukan elemen array terkecil kedua dan pertukarkan dengan elemen array di posisi ( indeks ) kedua
¨ Ulangi langkah-langkah diatas sampai semua array terurut
Berikut ini merupakan Procedure Selection Sort pada Pascal :
Procedure selectionSort(var a : array[1..size] of integer );
var integer i,j, min, tmp; begin for( i:=1 to size-1) do begin
for (j = i + 1 to size ) do begin
min = j;
if (a[i] > a[min]) then
SWAP à tmp = a[i];
a[i] = a[min];
a[min] = a[i];
end;
end;
end; { end of procedure }
|
Contoh sorting dengan Selection Sort
Iterasi Ke
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
Awal
|
22
|
10
|
8
|
3
|
2
|
I=1, Lok=5
|
2
|
10
|
8
|
3
|
22
|
I=2, Lok=4
|
2
|
3
|
8
|
10
|
22
|
I=3, Lok=4
|
2
|
3
|
8
|
10
|
22
|
I=4, Lok=5
|
2
|
3
|
8
|
10
|
22
|
Akhir
|
2
|
3
|
8
|
10
|
22
|
3. MERGE SORT
Algoritma Merge Sort ditemukan oleh John von Neumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut, Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh: hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudah terurut.
Algoritma Merge Sort
Algoritma Merge Sort sederhananya, dapat ditulis berikut:
a. Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
b. Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
c. Gabung 2 sublist kembali menjadi satu list terurut.
· Merge Sort dengan metode rekursif
Terdapat 3 prosedur dalam metode ini, yaitu prosedur merge sort,merge, dan insert.
prosedur mergesort
Langkah-langkahnya:
1. Membagi 1 array menjadi 2 dengan cara: cari tengahnya mid= (a+b) div 2 sehingga terdapat 2 bagian, (a,mid) dan (mid+1,b) lakukan terus pembagian sampai pada leaves (daun) yang tidak bisa dibagi lagi.
2. Lakukan merge pada daun yang tidak bisa dibagi lagi
3. Kedua langkah diatas dilakukan apabia a<b (indeks kiri lebih kecil dari indeks kanan)
Berikut ini merupakan Procedure Merge Sort pada Pascal :
algoritmanya:
procedure mergesort (a,b: integer)
begin
if a<b then
begin
mid:= (a+b) div 2
mergesort (a,mid)
mergesort (mid+1,b)
merge (a,b)
end if
end
|
Procedure Merge
Langkah - langkahnya:
1. Cari mid-nya
2. Tentukan indeks iàa=i
3. Tentukan k àk = mid+1
4. Bandingkan elemen yang ke i dengan elemen yang ke-k jika nilai elemen yang ke-i <= nilai elemen yang ke-k, maka naikkan jumlah i
jika tidak,maka
· insert elemen yang ke-k elemen yang ke-i
· naikkan jumlah i
· naikkan jumlah k
· naikkan mid
5. lakukan langkah 4 sampai i>mid atau k>b
Berikut ini merupakan Procedure merge :
algoritmanya:
prosedure merge (a,b:integer)
begin
mid=(a+b) div 2
i=a
k=mid+1
repeat
if a[i] <= a[k] then i =i+1
else
begin
insert (k,i)
i= i+1
k=k+1
mid=mid+1
endif
until i >mid or k>b
end
|
Prosedur Insert
Langkah - langkahnya:
1. Tentukan nilai yang akan diinsert (k), lalu masukkan nilai dari elemen ke-k ke variabel temp.
2. Tentukan bahwa j=k à posisi dari j sampai i+1 menggeser kekanan
3. Masukkan temp ke a[i]
Berikut ini merupakan Procedure insert :
procedure insert(k,i)
begin
temp=a[k]
for j=k downto i+1
a[j]=a[j-1]
endfor
a[i]=temp
end
|
4. Heap Sort
Heap Sort adalah sort yang memanfaatkan prinsip Pohon Heap. Pohon Heap adalah pohon biner complete dimana nilai yang terkandung dalam simpul bapak atau Father (F) lebih besar atau lebih kecil dari nilai kedua buah simpul anaknya atau simpul Son (5), sedangkan nilai simpul anak cabang kiri bisa lebih besar, lebih kecil, atau sama dengan nilai simpul anak cabang kanan.
I. Contoh Pohon Heap
II. Contoh Bukan Pohon Heap
III. Sistem Penomoran Pada Simpul
IV. Proses Pada Heap Sort
• Data yang akan disort berada dalam array satu dimensi. Sudah diketahui bahwa array satu dimensi dapat diilustrasikan atau dinyatakan dalam pohon biner. Proses Heap Sort terdiri dari 2 tahap.
– Susunan data dalam array diubah sedemikian rupa sehingga bila dinyatakan dalam pohon biner, maka pohonnya menjadi Pohon Heap.
V. Proses Pada Heap Sort
1. Menyusun array menjadi pohon heap (secara lojik)
Ilustrasi penerapan algoritma untuk data array di atas, terlihat seperti di bawah.
Isi tabel menjadi:
Isi tabel menjadi:
Isi tabel menjadi:
Datanya menjadi :
Hasil akhir pohon heap
2. Mengurutkan array pohon heap
Ilustrasi proses pengurutan sebagai berikut:
5. SHAKER SORT
Algoritma Shaker sort merupakan improvement dari algoritma pengurutan Bubble sort. Cara kerja dari algoritma ini hampir sama dengan cara kerja dari algoritma Bubble Sort. Perbedaannya adalah Shaker sort melakukan pengurutan array dari dua arah.
Berikut ini merupakan Procedure shaker sort :
procedure ShakeSort(var X : ArrayType; N : integer);
var
L,
R,
K,
J : integer;
begin
L := 2;
R := N;
K := N;
repeat
for J := R downto L do
if (X[J] < X[J - 1]) then
begin
Swap(X[J], X[J - 1]);
K := J
end;
L := K + 1;
for J := L to R do
if (X[J] < X[J - 1]) then
begin
Swap(X[J], X[J - 1]);
K := J
end;
R := K - 1;
until L >= R
end;
procedure Swap(var X, Y : integer);
var
Temp : integer;
begin
Temp := X;
X := Y;
Y := Temp
end;
|
By : Cutt Iswahyuni
Tidak ada komentar:
Posting Komentar