Metode-metode Sorting :
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 pertukaran. Proses pengapungan ini dilakukan sebanyak n-1 langkah(satu langkah disebut satu kali pass) dengan n adalah ukuran array.
I. Definisi
Bubble Sort merupakan cara pengurutan yang sederhana. Konsep dari algoritma ini adalah seperti gelembung air untuk elemen struktur data yang seharusnya berada pada posisi awal. Cara kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping) terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam traversal tersebut nilai dari dua struktur data dibandingkan, jika ternyata urutannya tidak sesuai dengan permintaan (urutan), maka dilakukan proses penukaran (swap).
II. Algoritma Bubble Sort (ascending)
Algoritma bubble sort adalah sebagai berikut, jika N adalah jumlah elemen data, dengan elemen-elemennya adalah T1, T2, …, TN-1,TN, maka:
1. Lakukan traversal dari belakang untuk membandingkan dua elemen yang berdekatan
2. Jika elemen pada TN-1 > TN , maka dilakukan proses pertukaran data (swap). Jika tidak, lanjutkan ke data berikutnya sampai bertemu dengan data yang telah diurutkan.
3. Ulangi langkah tersebut untuk semua data yang tersisa.
Ilustrasi Kasus :
Perhatikan array TabInt di bawah ini yang terdiri dari n = 6 elemen yang belum terurut. Array ini akan diurutkan menaik dengan metode Bubble Sort.
Elemen Array 25 27 10 8 76 21
Indeks 1 2 3 4 5 6
←Arah pembandingan
Pass 1 : | Pass 2 : (Berdasarkan hasil akhir Pass 1) | ||||||||||||
| 25 | 27 | 10 | 8 | 21 | 76 | | 8 | 25 | 27 | 10 | 21 | 76 |
| 1 | 2 | 3 | 4 | 5 | 6 | | 1 | 2 | 3 | 4 | 5 | 6 |
| 25 | 27 | 10 | 8 | 21 | 76 | | 8 | 25 | 27 | 10 | 21 | 76 |
| 25 | 27 | 8 | 10 | 21 | 76 | | 8 | 25 | 10 | 27 | 21 | 76 |
| 25 | 8 | 27 | 10 | 21 | 76 | | 8 | 10 | 25 | 27 | 21 | 76 |
| 8 | 25 | 27 | 10 | 21 | 76 | Hasil Akhir Pass 2 : | ||||||
Hasil Akhir Pass 1 : | | 8 | 10 | 25 | 27 | 21 | 76 | ||||||
| 8 | 25 | 27 | 10 | 21 | 76 | | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | | | | | | | |
Pass 3 : (Berdasarkan hasil akhir Pass 2) | Pass 4 : (Berdasarkan hasil akhir Pass 3) | ||||||||||||
| 8 | 10 | 25 | 27 | 21 | 76 | | 8 | 10 | 21 | 25 | 27 | 76 |
| 1 | 2 | 3 | 4 | 5 | 6 | | 8 | 10 | 21 | 25 | 27 | 76 |
| 8 | 10 | 25 | 21 | 27 | 76 | Hasil Akhir Pass 4 : | ||||||
| 8 | 10 | 21 | 25 | 27 | 76 | | 8 | 10 | 21 | 25 | 27 | 76 |
Hasil Akhir Pass 3 : | | 1 | 2 | 3 | 4 | 5 | 6 | ||||||
| 8 | 10 | 21 | 25 | 27 | 76 | Pass 5 : (Berdasarkan hasil akhir Pass 4) | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | | 8 | 10 | 21 | 25 | 27 | 76 |
| | | | | | | Hasil Akhir Pass 4 : | ||||||
| | | | | | | | 8 | 10 | 21 | 25 | 27 | 76 |
| | | | | | | | 1 | 2 | 3 | 4 | 5 | 6 |
# Hasil akhir Pass 5 menyisakan satu elemen yang tidak perlu diurutkan lagi maka pengurutan selesai.
Keterangan :
| | : Bagian data yang sudah diurutkan/diapungkan |
| | : Bagian data yang dibandingkan dan mungkin ditukarkan posisinya |
Procedure Bubble Sort
Procedure BubbleSort(input n:integer,input/output T:TabInteger)
{Mengurutkan Tabel Integer[1..N] dengan Bubble Sort}
Kamus
pass : integer {pencacah untuk jumlah langkah}
k : integer {pencacah pengapungan untuk setiap langkah}
temp : integer {variabel bantu untuk pertukaran}
Algoritma
for pass ← 1 to (n-1) do
for k ← n downto (pass+1) do
if (T[k] <>
{pertukarkan T[k] dengan T[k-1]}
temp ← T[k]
T[k] ← T[k-1]
T[k-1] ← temp
endif
endfor
endfor
Implementasi Procedure Bubble Sort dalam Algoritma
procedure InputData(input n : integer; output T : TabInteger)
Kamus
i : integer
Deskripsi
for i ← 1 to n do
read(T[i])
endfor
Procedure BubbleSort(input n:integer,input/output T:TabInteger)
{Mengurutkan Tabel Integer[1..N] dengan Bubble Sort}
Kamus
pass : integer {pencacah untuk jumlah langkah}
k : integer {pencacah pengapungan untuk setiap langkah}
temp : integer {variabel bantu untuk pertukaran}
Algoritma
for pass ← 1 to (n-1) do
for k ← n downto (pass+1) do
if (T[k] <>
{pertukarkan T[k] dengan T[k-1]}
temp ← T[k]
T[k] ← T[k-1]
T[k-1] ← temp
endif
endfor
endfor
Algoritma Bubble_Sort
Kamus
const Nmax=100
type TabInteger = array[1..NMax] of integer
TabInt : TabInteger
jml_data : integer
Deskripsi
read (jml_data) {memasukkan banyak data yang mau diinput}
InputData(jml_data,TabInt) {memanggil prosedur InputData}
BubbleSort(jml_data,TabInt) {memanggil Prosedur BubbleSort}
Algoritma Bubble_Sort memanggil dua prosedur yaitu prosedur InputData(dengan parameter jml_data sebagai input untuk parameter input n dan TabInt sebagai output untuk parameter output T) dan prosedur BubbleSort(dengan jml_data sebagai input untuk parameter input n dan TabInt sebagai input sekaligus output untuk parameter input/output T ).
Contoh buble sort dengan bahasa program pascal
Program Sorting_Bubble;
Uses winCrt;
Const
Max = 10;
Type
Arr = Array[1..max] Of Byte;
Var
Data : Arr;
i : Byte;
Procedure Input;
Begin
Clrscr;
Writeln('Masukkan 10 Data ');
Writeln('=================');
For I:=1 To Max Do
Begin
Write('Data Ke :',I,'=');Readln(Data[i]);
End;
Clrscr;
For i:=1 to Max Do
Write(Data[i],' ');
Writeln;
Writeln('=========================');
Writeln('Data Yang telah Diurutkan');
Writeln;
{ Readln;}
End;
Procedure Change (Var a,b :Byte);
Var c:Byte;
Begin
116
C:=a;a:=b;b:=c;
End;
Procedure Asc_Bubble;
Var
P,Q : Byte;
Flag: Boolean;
Begin
Flag:=False;
P:=2;
While (P
Begin
Flag:=True;
For Q:=Max Downto P Do
If Data[Q]
Begin
Change(Data[Q],data[Q-1]);
Flag:=False;
End;
Inc(i);
End;
Write(' Ascending ');
End;
Procedure Desc_Bubble;
Var
P,Q : Byte;
Flag: Boolean;
Begin
Flag:=False;
P:=2;
While (P
Begin
Flag:=True;
For Q:=Max Downto P Do
If Data[Q]>Data[Q-1] Then
Begin
Change(Data[Q],data[Q-1]);
Flag:=False;
End;
Inc(i);
End;
Write('Descending ');
End;
Procedure Output;
Begin
For I:=1 To Max Do
Write(Data[I],' ');
Writeln;
End;
Begin
Input;
Asc_Bubble; Output;
Desc_Bubble; OutPut;
Writeln;
117
Write('Tekan Enter Untuk Lanjut');
Readln;
End.
HASILNYA :
Selection Sort
Selection sort merupakan sebuah algoritma pengurutan yang secara berulang mencari item yang belum terurut dan mencari paling sedikit satu untuk dimasukkan ke dalam lokasi akhir.
Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya.
Contoh ilustrasi :
Misalkan ada sekumpulan data acak berjumlah n elemen yang disimpan di dalam larik L, akan diurut menaik, maka langkah-langkah yang harus dilakukan adalah:
1. Menentukan jumlah iterasi, yaitu pass = n – 2.
2. Untuk setiap pass ke-i = 0,1,2,...,pass, lakukan:
a. Cari elemen terbesar (maks) dari elemen ke-i sampai ke-(n-1).
b. Pertukarkan maks dengan elemen ke-i.
c. Kurangin n satu (n = n – 1).
Rincian tiap-tiap pas adalah sebagai berikut:
• pass 0
− Cari elemen maksimum di dalam L[0...(n-1)].
− Pertukarakan elemen maksimum dengan elemen L[n-1].
• pass 1
− Cari elemen maksimum di dalam L[0...(n-2)].
− Pertukarakan elemen maksimum dengan elemen L[n-2].
• pass 2
− Cari elemen maksimum di dalam L[0...(n-3)].
− Pertukarakan elemen maksimum dengan elemen L[n-3].
• pass 3
− Cari elemen maksimum di dalam L[0...1].
Selection Method - Selection Sort
− Pertukarakan elemen maksimum dengan elemen L[1].
Pseudo-code Selection Sort:
procedure SelectionSort(input/output A : TabelInt, input i,j: integer)
{ Mengurutkan tabel A[i..j] dengan algoritma Selection Sort.
Masukan: Tabel A[i..j] yang sudah terdefinisi elemen-elemennya.
Keluaran: Tabel A[i..j] yang terurut menaik. }
Algoritma:
if i <>then { Ukuran(A) > 1 }
Bagi(A, i, j)
SelectionSort(A, i+1, j)
endif
procedure Bagi(input/output A : TabInt, input i,j: integer)
{ Mencari elemen terkecil di dalam tabel A[i..j], dan menempatkan elemen terkecil sebagai elemen pertama tabel.
Masukan: A[i..j]
Keluaran: A[i..j] dengan Ai adalah elemen terkecil. }
Deklarasi
idxmin, k, temp : integer
Algoritma:
idxmin←i
for k←i+1 to jdo
if Ak <>idxmin then
idxmin←k
endif
endfor
{ pertukarkan Ai dengan Aidxmin }
temp←Ai
Ai←Aidxmin
Aidxmin←temp
Selection Method - Selection Sort
Contoh kasus:
Misalkan tabel A berisi elemen-elemen berikut:
4 12 3 9 1 21 5 2
Langkah-langkah pengurutan dengan Selection Sort:
4 12 3 9 1 21 5 2
1 12 3 9 4 21 5 2
1 2 3 9 4 21 5 12
1 2 3 9 4 21 5 12
1 2 3 4 9 21 5 12
1 2 3 4 5 21 9 12
1 2 3 4 5 9 12 21
1 2 3 4 5 9 12 21
1 2 3 4 5 9 12 21
Kompleksitas waktu algoritma:
⎩⎨⎧>+−==1,)1(1,)(ncnnTnanT
Penyelesaian (seperti pada Insertion Sort):
T(n) = O(n2).
Kelebihan dan kekurangan Selection Sort
1. Kompleksitas selection sort relatif lebih kecil
2. Mudah menggabungkannya kembali, tetapi sulit membagi masalah
3. Membutuhkan method tambahan
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. nggaplah 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 Insertion Sort adalah sebagai berikut:
Procedure insertionSort(input/output T : Larik, input nElm : integer) {KAw : Larik T terisi mulai indeks 1 s/d nElm} {KAk : Isi larik T dari indeks 1 s/d nElm terurut membesar} |
Kamus pass : integer i : integer temp : ElemenLarik |
Deskripsi pass traversal 2..nElm temp ß T[pass] i ß pass – 1 while (T[i]>temp) and (i>1) do T[i+1] ß T[i] i ß i – 1 if (T[i]>temp) then T[i+1] ß T[i] T[i] ß temp else T[i+1] ß pass |
Quick sort
Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar 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. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array
Merge sort
Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif.
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan. Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Komentar ini telah dihapus oleh pengarang.
BalasHapus