sorting

2.1 Sorting
Sorting adalah proses menyusun elemen-elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif. Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data.

Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma-algoritma yang ada sangatlah berguna.
Setelah menyelesaikan pembahasan pada bagian ini, anda diharapkan mampu :
1. Memahami dan menjelaskan algoritma dari insertion sort, selection sort,
merge sort dan quick sort.
2. Membuat implementasi pribadi menggunakan algoritma yang ada.

2.2 Bubble Sort
Bubble sort adalah salah satu metode pengurutan exchanging yang bersifat langsung dan termasuk jenis pengurutan yang paling sederhana. Nama bubble sort sendiri berasal dari sifat nilai elemen terbesar yang selalu naik ke atas (ke akhir dari list) seperti gelembung udara(bubble). Ide dari bubble sort adalah sebagai berikut :
1. Pengecekan dimulai dari elemen paling awal.
2. Elemen ke-1 dan ke-2 dari list dibandingkan.
3. Jika elemen pertama lebih besar dari elemen kedua, dilakukan pertukaran.
4. Langkah 2 dan 3 dilakukan lagi terhadap elemen kedua dan ketiga, seterusnya sampai elemen terakhir.
5. Bila sudah sampai di elemen terakhir dilakukan pengulangan lagi dari awal sampai tidak ada terjadi lagi pertukaran elemen.
6. Bila tidak ada pertukaran elemen lagi, maka elemen list terurut.
2.2.1 Algoritma
void bubble_sort(){
for(int i=1;i=i;j--){
(data[j]0) {
k = j;
}
}
swap(array[i],array[k]);
}
}

2.3.2 Contoh

2 4 6 7 5 9 3 8
2 4 6 5 7 9 3 8
2 4 5 6 7 9 3 8
2 3 4 5 6 7 9 8
2 3 4 5 6 7 8 9


2.4 Selection Sort
Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah-langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Tehnik pengurutan dengan cara pemilihan elemen atau proses kerja dengan memilih elemen data terkecil untuk kemudian dibandingkan dan ditukarkan dengan elemen data awal, dst sampai deagan seluruh elemen shingga akan menghasilkan pola data yang telah di sort.
Prinsip kerja dari tehnik selection ini adalah :
1. Pengecekan dimulai data ke-1 sampai dengan data ke-n.
2. Tentukan bilangan dengan indek terkecil dari data bilangan tersebut.
3. Tukarkan bilangan dengan index terkecil tersebut dengan bilangan pertama ( i= 1 ) dari data bilangan tersebut.
4. Lakukan langkah 2 dan ke 3 untuk bilangan berikutnya ( i= i+1 ) sampai didapatkan urutan yang optimal.

2.4.1 Algoritma
void selectionSort(Object array[], int startIdx, int endIdx) {
int min;
for (int i = startIdx; i < endIdx; i++) { min = i; for (int j = i + 1; j < endIdx; j++) { if (((Comparable)array[min]).compareTo(array[j])>0) {
min = j;
}
}
swap(array[min], array[i]);
}
}
2.4.2 Contoh

2 4 6 7 5 9 3 8
2 4 6 7 5 9 3 8
2 3 6 7 5 9 4 8
2 3 4 7 5 9 6 8
2 3 4 5 7 9 6 8
2 3 4 5 6 9 7 8
2 3 4 5 6 7 9 8
2 3 4 5 6 7 8 9

2.5 Merge Sort
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari konsep divide and conquer karena merge sort mengadaptasi pola tersebut.

2.5.1 Pola Divide dan Conquer
Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah 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. Divide
Memilah masalah menjadi sub masalah
2. Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif
3. Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama
2.5.2 Memahami Merge Sort
Seperti yang telah dijelaskan sebelumnya, 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 bagianyang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Prinsip kerja merge sort adalah :
1. Kelompokkan deret bilangan ke dalam 2 bagian, 4 bagian, 8 bagian,...dst.
2. Urutkan secara langsung bilangan ke dalam kelompok tersebut.
3. Lakukan langkah diatas untuk kondisi bilangan yang lain sampai didapatkan urutan yang optimal.

2.5.3 Algoritma
void mergeSort(Object array[], int startIdx, int endIdx) {
if (array.length != 1) {
//Membagi rangkaian data, rightArr dan leftArr
mergeSort(leftArr, startIdx, midIdx);
mergeSort(rightArr, midIdx+1, endIdx);
combine(leftArr, rightArr);
}
}



2.5.4 Contoh

2 4 6 7 5 9 3 8
2 4 6 7 5 9 3 8
2 4 6 7 5 9 3 8
2 3 4 5 6 7 8 9

2.6 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.
Sort dengan interasi secara urut dari posisi elemen 1, ke-2 san seterusnya. Tukarkan setiap elemen pd posisi tersebut dengan elemen lain yang nilainya memang seharusnya berada pada posisi tersebut.
Prinsip kerja dari quick sort adalah :
1. Tentukan Lower Bound (Batas Bawah) dan Upper Bound (Batas Atas).
2. Bandingka LB dengan UB.
3. Jika LB>UB. Tukar (cari operasi perbandingan yang optimal/terkecil).
4. Jika LB= leftIdx) {
pivotIdx = partition(array, leftIdx, rightIdx);
quickSort(array, leftIdx, pivotIdx-1);
quickSort(array, pivotIdx+1, rightIdx);
}
}





2.6.2 Contoh

2 4 6 7 5 9 3 8
2 3 6 7 5 9 4 8
2 3 4 7 5 9 6 8
2 3 4 5 7 9 6 8
2 3 4 5 6 9 7 8
2 3 4 5 6 7 9 8
2 3 4 5 6 7 8 9


2.7 Heap Sort
Heap Sort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.

2.7.1 Metode
Heap Sort memiliki dua fungsi utama yaitu , fungsi untuk menginisialisasi heap awal dari list kontigu dengan elemen acak, dan fungsi kedua yaitu fungsi untuk meng-insert heap baru dengan mengambil node awal heap dan mempromosikan elemen lain dibawahnya untuk menggantikan posisinya. Kali ini kami fungsi pertama akan dinamakan dengan BuildHeap() dan InsertHeap() untuk fugnsi kedua.
Untuk fungsi kedua merupakan tahap kedua di mana kita akan mengambil akar pohon heap yang merupakan nilai terbesar/terkecil (tergantung penyusunan) , dan nilai ini akan diletakkan di akhir list. Kita akan meyimpan indeks pengulangan dalam var last_unsorted.

2.7.2 Algoritma
template
void Sortable_list :: heap_sort( )
/* Post: The entries of the Sortable_list have been rearranged so that their keys
are sorted into nondecreasing order.
{
Record current; // temporary storage for moving entries
int last_unsorted; // Entries beyond last_unsorted have been sorted.
build_heap( ); // First phase: Turn the list into a heap.
for (last_unsorted = count − 1; last_unsorted > 0; last_unsorted−−)
{
current = entry[last_unsorted]; // Extract the last entry from the list.
entry[last_unsorted] = entry[0]; // Move top of heap to the end
insert_heap(current, 0, last_unsorted
− 1); // Restore the heap
}
}

2.7.3 Fungsi InsertHeap()
Pada fungsi insert_heap ini akan melakukan penghapusan sebuah simpul pada heaptree, pemilihan sebuah simpul untuk ditempatkan di posisi yang lebih atas, dan menjaga tree tersebut tetap sebuah heaptree.
Langkah-langkanya ialah :
1. Setiap simpul yang dihapus(low) dicari anaknya yang memiliki kunci terbesar/terkecil(large)
2. Anak dengan kunci yang lebih besar dipromosikan ke tempat simpul yang di hapus.

3. Langkah 1 dan 2 akan di lakukan berulang kali sampai simpul yang dihapus tidak punya anak lagi atau simpul yang ingin dipromosikan lebih besar/kecil daripada anak dari simpul yang dihapus yang memiliki kunci terbesar/terkecil.

Prinsip kerja heap sort :
1. Bentuk pohon heap dengan prosedur yang ada.
2. Laksanankan sort, ulangi sampai dengan langkah 10; Q=N, N-1,…..,2.
3. Tentukan nilai record: K[I]←→K[Q].
4. Berikan harga awal I←1; Key← K[I]; J←2.
5. Dapatkan indek dari harga terbesar anak dari record baru.
If J+1K[J] then
J=J+1
6. Buat kembali heap baru., Ulangi sampai langkah 10 apabila JKey.
7. Tukarkan harga record: K[I]←→K[J]
8. Dapatkan anak berikutnya.
I←J; J←Q+1
9. Dapatkan indeks dari anak dengan harga terbesar berikutnya
if J+1K[J] then
J=J+1
Else
if J> N then J=N
10. Copykan record ke dalam tempatnya yang cocok
K[I]←Key I return

Berikut kode program fungsi insert_heap() dalam bahasa c ++ :
template
void Sortable_list :: insert_heap(const Record ¤t, int low, int high)
/* Pre: The entries of the Sortable_list between indices low Ç 1 and high, inclusive,
form a heap. The entry in position low will be discarded.
Post: The entry current has been inserted into the Sortable_list and the entries
rearranged so that the entries between indices low and high, inclusive,
form a heap.
*/
{
int large; // position of child of entry[low] with the larger key
large = 2 * low + 1; // large is now the left child of low.
while (large <= high) { if (large < high && entry[large] < entry[large + 1]) large++; // large is now the child of low with the largest key. if (current >= entry[large]){
break; // current belongs in position low.
}
else { // Promote entry[large] and move down the tree.
entry[low] = entry[large];
low = large;
large = 2 * low + 1;
}
}
entry[low] = current; }

Contoh :

2.7.4 Fungsi BuildHeap()
Pada bagian build heap ini kiat kan menginisialisasi heap awal dari list yang acak. Untuk melakukan hal tersebut pertama-tama ingat bahwa 2 pohon dengan satu simpul secara otomatis, akan memenuhi ketentuan dari sebuah heap, dengan demikian kita tidak perlu khawatir dengan daun dari pohon; yaitu paruh kedua dari list. Jika kita memulai dari tengah list sampai ke awal, kita dapat menggunakan fungsi insert_heap untuk memasukkan setiap masukan ke bagian heap yang terdiri dari semua masukan yang masuk kemudian yang kemudian membentuk heap yang sempurna.
Berikut ini fungsi build_heap yang ditulis dalam bahasa C++.
template
void Sortable_list :: build_heap( )
/* Post: The entries of the Sortable_list have been rearranged so that it becomes
a heap.
*/and insert_heap. */
{
int low; // All entries beyond the position low form a heap.
for (low = count/2 - 1; low >= 0; low--) {
Record current = entry[low];
insert_heap(current, low, count - 1);
}
}