ALGORITMA SORTING
Catatan Logika
Algoritma, 29 April 2017
Pertemuan Ke-4,5,6,7
ALGORITMA
SORTING
Sorting adalah
proses menyusun elemen-elemen dengan tata urut tertentu, dan proses tersebut
terimplementasi dalam berbagai macam aplikasi. Aplikasi tersebut mampu menampilkan account yang aktif. Hampir
seluruh pengguna dalam sistem akan memilih tampilan daftar perurutan yang scara
ascending demi kenyamanan dalam perurutan yang secara ascending demi kenyamanan
dalam penelusuran data.
 |
| -=ALGORITMA SORTING=- |
Beberapa macam
algoritma telah dibuat karena proses tersebut sangat mendasar dan sering
digunakan. Ada beberapa metode sorting yang sering digunakan antara lain:
-
Buble sort
-
Insertion sort
-
Selection sort
-
Merge sort
-
Quick sort
-
Shell sort
-
Radix sort
-
Heap sort
a. Insertion
Sort
Insertion sort merupakan algoritma sorting yang paling sederhana. Ide
dari algoritma ini dapat dianalogikan seperti pengurutan kartu. Algoritma
insertion sort pada dasarnya memilah data yang akan di urutkan menjadi dua
bagian, yang belum di urutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum di urutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan.
Contoh:
Data
|
1st pass
|
2nd pass
|
3nd 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
|
Algoritma:
Void insertion sort (objek array [], int start idx,int end idx ]{
For (int i=start idx, i<end idx; i++) {
Int k =i;
For (m+i=i+1;) < end idx ; i++) {
If ( ( (comparable) array [k]. Compareto (array[1]) >0) {
}
}
Swap (array [i], array[k];
}.
b. Selection
Sort
Hampir
sama dengan metode insertion sort. Algoritma ini sangat rapat dan mudah untuk
diimplementasikan. Cara kerja metode ini didasarkan pada pencarian elemen
terkecil kemudian dilakukan penukaran dengan elemen 1. Sebagai contoh pada
pengurutan satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan
secara ascending. Pada awalnya, kartu tersebut akan disusun secara linear pada
sebuah meja dari kiri ke kanan dan dari atas ke bawah. Pilih nilai kartu yang
paling rendah, kemudian tukarkan posisi kartu yang terletak pada pojok kiri
atas meja, lalu cari kartu dengan nilai paling rendah di antara sisa kartu yang
ter sedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi
kedua sebelum posisi terakhir dibandingkan dan digeser dengan kartu yang bernilai rendah.
Contoh:
Data
|
1st pass
|
2nd pass
|
3nd pass
|
4th pass
|
Maricar
|
Hannah
|
Hannah
|
Hannah
|
Hannah
|
Vanessa
|
Vanessa
|
Margaux
|
Margaux
|
Margaux
|
Margaux
|
Margaux
|
Vanessa
|
Maricar
|
Maricar
|
Hannah
|
Maricar
|
Maricar
|
Vanessa
|
Rowena
|
Rowena
|
Rowena
|
Rowena
|
Rowena
|
Vanessa
|
Algoritma:
Void
selection sort (object array[], int star idx, int end idx){
Int min;
For (int
i=start idx; i< end idx; i++){
Min=I;
For (int
I=i+1, I<end idx; J++){
If ( (
(comparable)array[min])compare To (array[j])>0){
Min=j;
}
Swap(array[min],array[i];
}
c. Merge
Sort
Sebelum
mengetahui algoritma merge sort, kita ketahui dulu garis besar dari konsep Devide End Canguer karena merge sort
mengadaptasi pola tersebut. Beberapa algoritma mengimplementasi konsep rekursi untuk
menyelesaikan permasalahan utama kemudian di pecah menjadi sub masalah,
kemudian solusi dari sub masalah akan membimbing menuju solusi permasalahan
utama.
Pada setiap
tingkatan rekursi pola tersebut terdiri atas 3 langkah:
1.
Devide è
memilih masalah menjadi sub masalah
2.
Canguer è
selesaikan sub masalah tersebut menjadi rekursif
3.
Kombinasi è
mengkombinasikan solusi dari sub masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama.
Contoh:
-
Rangkaian data
7
|
2
|
5
|
6
|
-
Membagi rangkaian menjadi 2(dua) bagian
5
|
6
|
right
|
arr
|
7
|
2
|
Left
|
arr
|
-
Membagi left arr menjadi dua bagian
7
|
2
|
-
Mengkombinasikan
2
|
7
|
-
Membagi right arr menjadi dua bagian
-
Mengkombinasikan
5
|
6
|
-
Mengkombinasikan left arr dan right arr
2
|
7
|
5
|
6
|
Algoritma:
Void merge sort
(object array [],int start idx, int end idx){
If(arrray length i=i){
//membagi rangkaian data, right
arr dan left arr
Merge sort (left arr,
start idx, end idx);
Merge sort (right arr,
start idx, end idx);
Combine (left arr, right
arr);
}
}
d. Quick
Sort
Algoritma
ini ditemukan oleh (A.R Horme). Seperti pada merge sort algoritma ini juga berdasar
pada pola devide and canguer tetapi algoritma ini hanya mengikuti langkah-langkah
berikut:
1.
Devide
Memilih rangkaian data menjadi dua sub rangkaian A[P.Q.I]
dan A[Q+I.r] di mana setiap elemen A[P.Q.I] adalah kurang dari atau sama dengan
[Q] dan setiap elemen pada A[Q+.r] adalah sama dengan atau lebih besar elemen
pada A[Q] disebut sebagai elemen pivot perhitungan pada elemen Q merupakan
salah satu bagian dari prosedur pemisahan.
2.
Conguer
Mengurutkan elemen pada sub bagian secara rekursif
Pada algoritma Quick sort, langkah kombinasi tidak dilakukan karena
telah terjadi pengurutan elemen-elemen pada sub array.
Contoh:
Rangkaian data
3
|
1
|
4
|
1
|
5
|
9
|
2
|
6
|
5
|
3
|
5
|
8
|
Pilih sebuah elemen yang menjadi
elemen pivot
3
|
1
|
4
|
1
|
5
|
9
|
2
|
6
|
5
|
3
|
5
|
8
|
Inisialisasi elemen kiri sebagai
elemen kedua dari elemen kanan sebagai elemen akhir
3
|
1
kiri
|
4
|
1
|
5
|
9
|
2
|
6
|
5
|
3
|
5
|
8
kanan
|
Geser elemen kiri ke kanan sampai
ditemukan nilai yang lebih besar dari elemen pivot tersebut geser elemen kanan
ke kiri sampai di temukan nilai dari elemen yang tidak lebih besar dari elemen
tersebut.
3
|
1
|
4
kiri
|
1
|
5
|
9
|
2
|
6
|
5
|
3
kanan
|
5
|
8
|
Tukarkan antara elemen kiri dan kanan
3
|
1
|
3
kiri
|
1
|
5
|
9
|
2
|
6
|
5
|
4
kanan
|
5
|
8
|
Geserkan lagi elemen kiri dan kanan
Tukarkan antar elemen kembali
3
|
1
|
3
|
1
|
2
kiri
|
9
|
5
kanan
|
6
|
5
|
4
|
5
|
8
|
Geser lagi elemen kiri dan kanan
3
|
1
|
3
|
1
|
2
|
9
|
5
|
6
|
5
|
4
|
5
|
8
|
Terlihat bahwa titik kiri dan
kanan telah digeser sehingga mendapatkan
nilai elemen kanan
2
|
1
|
3
|
1
|
3
|
9
|
5
|
6
|
5
|
4
|
5
|
8
|
Algoritma:
Void Quick sort (object array [], int
left idx, int end idx){
Int pivot idx;
/*kondisi terminasi*/
If(right idx>left idx){
Pivot idx=partition (array, left idx,
right idx);
Quick sort(‘array left idx, pivot
idx’);
Quick sort (array, pivot idx+1, right
idx);
}
{
e. Bubble
Sort
Merupakan
salah satu jenis sorting termudah karena konsep dari algoritmanya diibaratkan
seperti gelembung air untuk elemen struktur data yang seharusnya pada posisi
awal. Buble sort mengurutkan data dengan cara mebandingkan elemen sekarang
dengan elemen berikutnya. Dengan cara berulang melakukan proses looping
(perulangan) terhadap elemen-elemen struktur data yang belum di urutkan di mana
nilai dari masing-masing elemen akan dibandingkan selama proses looping.
Contoh:
Data
TAHAP 1
22
|
10
|
15
|
3
|
8
|
2
|
22
|
10
|
15
|
3
|
2
|
8
|
22
|
10
|
15
|
2
|
3
|
8
|
22
|
10
|
2
|
15
|
3
|
8
|
22
|
2
|
10
|
15
|
3
|
8
|
2
|
22
|
10
|
15
|
3
|
8
|
TAHAP 2
2
|
22
|
10
|
15
|
3
|
8
|
2
|
22
|
10
|
3
|
15
|
8
|
2
|
22
|
3
|
10
|
15
|
8
|
2
|
3
|
22
|
10
|
15
|
8
|
TAHAP 3
2
|
3
|
22
|
10
|
15
|
8
|
2
|
3
|
22
|
10
|
8
|
15
|
2
|
3
|
22
|
8
|
10
|
15
|
2
|
3
|
8
|
22
|
10
|
15
|
TAHAP 4
2
|
3
|
8
|
22
|
10
|
15
|
2
|
3
|
8
|
10
|
22
|
15
|
TAHAP 5
2
|
3
|
8
|
10
|
15
|
22
|
