Metode sorting

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 A_i adalah elemen terkecil. }

Deklarasi

idxmin, k, temp : integer

Algoritma:

idxmin←i

for k←i+1 to jdo

if A_k <>idxmin then

idxmin←k

endif

endfor

{ pertukarkan A_i dengan A_idxmin }

temp←A_i

A_i←A_idxmin

A_idxmin←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(n²).

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.