TEKNIK SORTING
SORTING dapat 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).
- Descending
(Turun).
Contoh :
Data
: Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);
Data
Acak
: 22 10 15 3 8 2
Terurut Ascending
: 2 3 8 10 15 22
Terurut
Descending : 22 15 10 8 3 2
Untuk melakukan
proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.
Beberapa metode
yang sudah umum digunakan diantaranya adalah :
1. Pengurutan
berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)
- Insertion sort
Teknik sorting ini dibuat dengan cara menyisipkan atau memasukkan
satu-persatu, bila kita akan mengurutkan data, kemudian ingin menyisipkan suatu
data maka data tersebut akan otomatis masuk dimana dia berada. Pengurutan
dilakukan dengan cara membandingkan data ke – i dengan data berikutnya, (dimana
i dimulai dari data di index ke 1 sampai dengan data terakhir). Jika ditemukan
data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan
posisi yang seharusnya, dan saat ada elemen yang disispkan, maka elemen-elemen
lainnya akan bergeser kebelakang.
Contoh procedure
insertion sort ascending :
Procedure
asc_insert;
Var
i, j, temp :
byte;
begin
for i := 2 to max do
begin
temp := data [i] ;
j :=i-1;
while (data [j] >
temp ) and (j>0) do
begin
data [j+1] := data [j];
dec (j) ;
end;
data [j+1] := temp ;
end;
end;
- Tree sort
Metode sorting dengan cara membangun pohon biner dengan menampilkan 3
hasil output: PreOrder, InOrder, dan PostOrder. Konsep dasar dari tree sort
adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dan sebagainya.
Dalam tree sort ada istilah akar atau root dan daun atau leaf.
ketentuan
dari gambar diatas adalah :
1
menjadi akar ,
2
menjadi subtree kiri,
3
menjadi subtree kanan,
4
& 5 menjadi daun dari subtree kiri ,
6
menjadi daun dari subtree kanan.
Setiap
objek dalam pohon biner berisi dua pointer, biasanya disebut kiri dan kanan.
Selain pointer ini tentu saja node dapat berisi tipe data lainnya. Misalnya,
pohon biner integer bisa terdiri dari objek dari jenis berikut:
struct Node {
int item; / / Data dalam node ini.
Node *kiri; / / Pointer ke subtree kiri.
Node * kanan; / / Pointer ke subtree kanan.
}
2. Pengurutan berdasarkan perbandingan
(compirasion-based sorting)
- Bubble sort
Teknik ini dilakukan dengan pola membawa nilai terbesar menjadi nilai
index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2,
lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil
lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah
data. Membandingkan elemen yang sekarang dengan elemen yang berikutnya, jika
elemen sekarang>elemen berikutnya, maka tukar.
Contoh procedure
tukar data:
Procedure
asc_buble (var data :array; jmldata:integer);
Var
i,j : integer;
begin
for i := 2 to jmldata do
for j :=jmldata downto i do
if data [j] < data [j-1] then
tukardata (data[j], data [j-1] ) ;
end;
- Exchange sort
Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar
menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai
1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang
lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan
hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran.
Jadi waktu untuk melakukan proses sorting lebih cepat. Exchange sort itu sangat
mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama
dengan buble sort.
Contoh procedure
exchange sort :
Procedure
asc_buble (var data :array; jmldata:integer);
Var
i,j : integer;
begin
for i := 2 to jmldata do
for j :=jmldata downto i do
if data [j] < data [j-1] then
tukardata (data[j], data [j-1] ) ;
end;
perbedaannya
terdapat dalam hal bagaimana membandingkan antar elemen-elemennya:
3. Pengurutan berdasarkan prioritas
(priority queue sorting method)
- Selection sort
Teknik sorting ini dibuat dengan cara melakukan pengecekan satu-persatu,
bila kita akan mengurutkan secara ascending maka kita lakukan pengecekan nilai
tempat yang pertama (index pertama pada array) kita bandingkan semua nilai yang
ada kita cari nilai minimalnya, lalu simpan index/ letak nilai minimum itu
ditemukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai
minimum yang telah simpan tadi. Proses ini dilakukan terus-menerus sampai pada
pengecekan index terakhir minimal dengan index terakhir, beda dengan streith
selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih
sedikit, hanya jumlah data-1 pertukaran. Jadi waktu untuk melakukan proses
sorting lebih cepat. Membandingkan elemen yang sekarang dengan elemen yang
berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen yang lebih
kecil, maka dicatat posisinya. Namun jika ditemukan elemen terkecil, maka
dicatat posisinya dan kemudian di TUKAR dengan elemen sekarang.
Contoh procedure
selection sort secara ascending :
Procedure
asc_selection;
Var
Min,pos : byte;
Begin
For i:= 1 to max-1 do
Begin
Pos :=i ;
For j := i+1 to max do
If data [j] < data [pos] then pos
:=j;
If i <> pos then
tukardata (data[i] , data[pos] );
End;
End;
- Heap sort (menggunakan tree)
Teknik
sorting ini dibuat dengan versi yang jauh lebih efisien selection sort. Ia juga
bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan
bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa
daftar tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur
data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah
dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil)
terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah
ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap,
menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n)
untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort
untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas
kasus terburuk.
HeapSort 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. Algoritma
pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang
larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu
Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree.
Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.
Algoritma pengurutan heap dimulai dari membangun
sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus
data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang
telah terurut. Setelah memindahkan data dengan nilai terbesar, proses
berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap
tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum
diisi data lain.
Proses
ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang
terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk
menyimpan heap dan satu lagi untuk menyimpan data yang sudah
terurut. Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu
larik saja. Yaitu dengan cara menukar isi akar dengan elemen terakhir
dalam heap tree. Jika memori tidak menjadi masalah maka dapat tetap
menggunakan dua larik yaitu larik masukan dan larik hasil.
Heap
Sort memasukkan data masukan ke dalam struktur data heap. Nilai terbesar
(dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu
sampai habis, nilai tersebut diambil dalam urutan yang terurut.
Algoritma
untuk heap sort :
function
heapSort(a, count) is
input:
sebuah larik tidak terurut a dengan panjang length
(pertama
letakkan a dalam max-heap) heapify(a, count)
end
:= count -1
while
end > 0 do
remove
( )
reheapify
( )
end := end – 1
4. Pengurutan berdasarkan pembagian
dan penguasaan (devide and conquer method)
- Quick sort
Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada
teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi
selalu lebih kecil dari data disebelah kanan. Namun data pada kedua patisi belum
terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua
partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi
lagi. Merupakan proses penyusunan elemen yang membandingkan suatu elemen
(pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen
–elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan
elemen yang lebih besar dari pivot terletak disebelah kanan pivot.Dengan
demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri
pivot.Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan
kita kerjakan proses yang sama seperti yang sebelumnya.Demikian seterusnya
sampai tidak terdapat sublist lagi.
Contoh procedure
quick sort secara ascending :
Procedure asc_quick
(l , r :integer) ;
Var
i, j : integer;
begin
if l < r then
begin
i := l ; j := r+1;
repeat
repeat inc (i) until data [i] >=
data [l] ;
repeat dec (j) until data [j] <=
data [l] ;
if i<j then tukardata (data [i], data [j]) ;
until i>j ;
tukardata (data [l], data [j] );
asc_quick (l, j-1);
asc_quick (j+1, r);
end;
end;
- Merge sort
Teknik
sorting ini dibuat dengan cara mengambil keuntungan dari kemudahan penggabungan
daftar sudah disortir ke daftar diurutkan baru. Dimulai dengan membandingkan
setiap dua elemen (yaitu: 1 dengan 2, kemudian 3 dengan 4) dan swapping mereka
jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan
daftar yang dihasilkan dari dua ke daftar empat, kemudian menggabungkan daftar
tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam
daftar diurutkan akhir.
Algoritma pengurutan data mergesort dilakukan dengan menggunakan cara
divideandconquer yaitu dengan memecah kemudian menyelesaikan setiap bagian
kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana
bagian pertama merupakan setengah (jika data genap) atau setengah minus satu
(jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali
untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu digabungkan kembali dengan
membandingkan pada blok yang sama apakah data pertama lebih besar daripada data
ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama,
kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai
ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya.
Sehingga metode mergesort merupakan metode yang membutuhkan fungsi rekursi
untuk penyelesaiannya.
Dengan hal ini deskripsi dari algoritma dirumuskan
dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja
dari Mergesort.
-
Divide : Memilah elemen – elemen dari
rangkaian data menjadi dua bagian.
-
Conquer : Conquer setiap bagian dengan memanggil
prosedur mergesortsecararekursif
-
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.
Contoh penerapan atas sebuah larik/array sebagai
data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:
-
Pertama kali larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
- Kedua
larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2,
5}
-
Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut
{1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1
dalam elemen larik ke dua telah dipindahkan ke larik baru)
-
Langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik
baru yang dibuat sebelumnya
-
{1, 2} ↔{3, 4, 9} dan {5}
-
{1, 2, 3} ↔ {4, 9} dan {5}
-
{1, 2, 3, 4}↔{9} dan {5}
-
{1, 2, 3, 4, 5}↔{9} dan {null}
-
{1, 2, 3, 4, 5, 9}↔{null}dan {null}
Contoh
program sedehana merge sort :
Public
class mergeSort{
Public
static void main(String args [ ] ){
int
i;
int
array [ ] = {7,5,1,3,6,4,9,8};
System.out.println("\n\n
Kelompok 3\n\n");
System.out.println("
Pengurutan dengan MergeSort\n\n");
System.out.println("Data
Sebelum Diurutkan:\n");
for(i = 0; i < array.length; i++)
System.out.print(
array[i]+" ");
System.out.println(
);
Merge
Sort_srt(array,0, array.length - 1);
System.out.print("Data
Setelah Diurutkan:\n");
for(i = 0; i < array.length; i++)
System.out.print(array[i]+"
");
System.out.println();
}
Public
static void mergeSort_srt(int array[ ],int lo, int n){
int
low = lo;
int
high = n;
if
(low > = high)
{return; }
int
middle = (low + high) / 2;
mergeSort_srt(array,
low, middle);
mergeSort_srt(array,
middle + 1, high);
int
end_low = middle;
int
start_high = middle + 1;
while
((lo <= end_low) && (start_high <= high))
{
if
(array[low] < array[start_high]) {
low++;
}
else
{
int
Temp = array[start_high];
for (int k = start_high- 1; k > =low; k--)
{array[k+1] = array[k]; }
array[low]
= Temp;
low++;
end_low++;
start_high++;
}
}
}
5. Pengurutan berkurang menurun
(diminishing increment sort method)
- Shell sort (pengembangan insertion)
Merupakan proses pengurutan data yang sebelumnya acak menjadi data yang
terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan.
Teknik sorting ini dibuat dengan cara meningkatkan atas bubble sort dan
insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari
satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai
mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom baru
array menggunakan insertion sort.
Metode ini dikembangkan oleh Donald L. Shell pada
tahun 1959. Dalam metode ini jarak antara dua elemen yang dibandingkan dan
ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut. Pada
langkah pertama, kita ambil elemen pertama dan kita bandingkan dengan elemen
pada jarak tertentu dari elemen pertama tersebut. Kemudian elemen kedua kita
bandingkan dengan elemen lain dengan jarak yang sama seperti diatas. Demikian
seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses
diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut
diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu.
Berikut ini
merupakan Procedure Shell Sort pada Pascal :
Procedure
Shell(Var Temp : Data; JmlData : Integer);
Var I,J, Jarak
: Integer;
Begin
Jarak := JmlData Div 2;
While Jarak > 0 Do
Begin
For I:=1 To JmlData-Jarak Do
Begin
J := I + Jarak;
If Temp[I] > Temp[J] Then
SWAP(Temp[I], Temp[Lok]);
End;
Jarak := Jarak Div 2;
End;
End;
[ Dipost oleh
EVI IRFAN BUDIANA - A710140033 -
PENDIDIKAN TEKNIK INFORMATIKA UMS ]
http://puguhjayadi.blogspot.com/2013/05/tree-sort-c.html
Tidak ada komentar:
Posting Komentar