SORTING
Pengertian Algoritma Pengurutan
(sorting)
• Dalam ilmu komputer, algoritma pengurutan adalah
• algoritma yang meletakkan elemen-elemen suatu kumpulan
data dalam urutan tertentu. Atau
• proses pengurutan data yg sebelumnya disusun secara acak
sehingga menjadi tersusun secara teratur menurut suatu aturan
tertentu.
• Yang pada kenyataannya ‘urutan
urutan tertentu
tertentu’ yang umum
digunakan adalah secara terurut secara numerikal ataupun
secara leksikografi (urutan secara abjad sesuai kamus).
• Ad 2 jjenis
Ada i sorting
i : A Ascending
di ((naik)
ik) & D
Descending
di
(turun)
Klasifikasi AlgoritmaPengurutan (sorting)
y Exchange Sort
melakukan pembandingan antar data, dan
melakukan pertukaran apabila urutan yang
didapat belum sesuai.
Contohnya : Bubble sort, Cocktail sort, Comb sort, Gnome
sort, Quicksort.
y Selection Sort
mencarii elemen
l yang tepat
t t untuk
t k diletakkan
dil t kk di
posisi yang telah diketahui, dan meletakkannya
di posisi tersebut setelah data tersebut
ditemukan.
Contohnya :Selection sort, Heapsort, Smoothsort, Strand sort
y Insertion Sort
mencari tempat yang tepat untuk suatu elemen data yang telah
diketahui ke dalam subkumpulan data yang telah terurut,
kemudian melakukan penyisipan (insertion) data di tempat yang
tepat tersebut.
tersebut
Contohnya adalah : Insertion sor, Shell sort, Tree sort, Library sort, Patience sorting.
y Merge Sort
data
d t dib
dibagii menjadi
j di subkumpulan-subkumpulan
bk l bk l yang k kemudian
di
subkumpulan tersebut diurutkan secara terpisah, dan kemudian
digabungkan kembali dengan metode merging. algoritma ini
melakukan metode pengurutan merge sort juga untuk
mengurutkan
k subkumpulandata
bk l d tersebut,
b atau dengan
d k
kata lain,
l i
pengurutan dilakukan secara rekursif.
Contohnya adalah : Merge sort.
y Non-Comparison Sort
proses pengurutan data yang dilakukan
algoritma ini tidak terdapat pembandingan
antardata, data diurutkan sesuai dengan
pigeon hole principle.
Contohnya adalah : Radix sort, Bucket sort, Counting sort,
Pigeonhole sort
sort, Tally sort
sort.
METODE SORTING
1. RADIX SORT
Ide Dasar
y Ide dasar dari metode Radix sort ini adalah
mengkategorikan data-data menjadi sub kumpulan
subkumpulan data sesuai dengan nilai radix-nya,
mengkonkatenasinya,
k k t i kemudian
k di
mengkategorikannya kembali berdasar nilai radix
lainnya.
lainnya
Implementasi Radix Sort
• Contoh implementasi
p yyang
g akan dilakukan adalah
implementasi pada bilangan bulat positif
menggunakan salah satu algoritma pengurutan
radix
di sort.
t
• Contohnya adalah pengurutan sebuah kumpulan
data bilangan bulat dengan jumlah digit maksimal 3
Pertama kali, data dibagi-bagi sesuai dengan digit
terkanan :
y Hasil pengkategorian tersebut lalu digabung
kembali dengan metode konkatenasi menjadi :
y Kemudian pengkategorian dilakukan
kembali,namun kali ini berdasar digit kedua atau
digit tengah, dan jangan lupa bahwa urutan pada
tiap subkumpulan data harus sesuai dengan urutan
kemunculan pada kumpulan data
Yang kemudian dikonkatenasi kembali menjadi
Kemudian langkah
g ketiga,
g , atau langkah
g terakhir
pada contoh ini adalah pengkategorian kembali
berdasar digit yang terkiri, atau yang paling
signifikan
i ifik
y Yang kemudian dikonkatenasi lagi menjadi
y Yang merupakan hasil akhir dari metode
pengurutan ini. Di mana data telah terurut dengan
metode radix sort.
Algoritma dan Kompleksitas Waktu
Radix Sort
y Implementasi
p dari algoritma
g tersebut dibuat
menggunakan bahasa Pascal, yang direalisasikan
dengan menggunakan queue sebagai representasi
ti k
tiap kategori
t i radix
di untuk
t k pengkategorian.
k t i
y Array A adalah array input, dan array B adalah
array A yang sudah terurut.
terurut
Procedure RadixSort (A : TArray; var B : TArray; d : byte);
var
KatRadix : array [0..9] of Queue;
i x, ctr
i, t : iinteger;
t
pembagi : longword;
begin
{--- mengkopi A ke B ---}
for i:=1 to n do
B[i] := A[i];
pembagi := 1;
for x:=1 to d do begin
{ inisialisasi
{--- i i i li i KKatRadix
R di ---}}
for i:=0 to 9 do
InitQueue (KatRadix[i]);
{--- dikategorikan ---}
for i:
i:=11 to n do
Enqueue (KatRadix [(B[i] div pembagi) mod 10], B[i]);
B[i] := 0;
{--- dikonkat ---}
ctr := 0;
for i:=0 to 9 do begin
while (NOT IsQueueEmpty (KatRadix[i])) do begin ctr := ctr + 1;
B[ctr]:=DeQueue (KatRadix [i]);
end;
end;
pembagi := pembagi * 10;
end;
end;
METODE SORTING
2. BUBLE SORT
Ide Bubble Sort
o Algoritma dimulai dari elemen paling awal.
o 2 buah elemen pertama dari list dibandingkan.
o Jika elemen pertama lebih besar dari elemen
kedua,dilakukan
kedua dilakukan pertukaran
pertukaran.
o Langkah 2 dan 3 dilakukan lagi terhadap elemen
kedua dan ketiga,
g , seterusnya
y sampai
p ke ujung
j g
elemen
o Bila sudah sampai ke ujung dilakukan lagi ke awal
sampaii tidak
tid k ada
d terjadi
t j di lagi
l i pertukaran
t k elemen.
l
o Bila tidak ada pertukaran elemen lagi, maka list
elemen sudah terurut.
Algoritma Bubble Sort
y Setiap pasangan data: x[j] dengan x[j-1], untuk
semua i=1,...,n-1 harus memenuhi keterurutan,
yaitu x[j] > x[j-1].
y Apabila
b l tidak
d k memenuhih maka
k posisi kedua
k d data
d
harus ditukar.
y Untuk
U t k pemrograman k konvensional
i l maka
k
pemeriksaan-pemeriksaan pasangan tersebut
harus dilakukan satu demi satu, misalnya oleh
bubble-sort dilakukan dari kanan ke kiri serta di
dalam sejumlah iterasi.
y Pada iterasi ke-i, pemeriksaan tsb. dilakukan pula dalam loop-for
sbb.
bb
deskripsi
adatukar true
I 1
While (I<n) and (adatukar) do
J 1
Adatukar false
While j <= < (n-I)
(n I) do
If x[j] > x[j+1] then
Adatukar true
temp x[j]
X[j]
[j] x[j+1]
[j ]
x[j+1] temp
endif
j j+1
endwhile
i i+1
endwhile
y Loop-for
p tersebut
b akan menggeser
gg b
bilangan
g
terkecil ke posisi i.
y Loop-for dilakukan hanya sampai ke i karena pada
iterasi ke-i data dalam x[0], x[1], ..., x[I 1]
merupakan yang paling kecil dan sudah terurut
h il pengeseran yang dil
hasil dilakukan
k k setiapti lloop
sebelumnya.
y Oleh sebab itu iterasi hanya dilakukan untuk harga
i=0, 1, ..., n-2 atau sampai tidak terjadi penukaran
dalam suatu iterasi.
Implementasi Bubble Sort
Pada gambar di bawah, pegecekan dimulai dari data yang
paling akhir, kemudian di bandingkan dengan data di
depannya, jika data di depannya lebih besar maka akan
ditukar.
ditukar
Tidak ada penukaran
karena 3<8
Pengurutan Berhenti Di Sini
•Pada proses kedua, pengecekan dilakukan
sampaii dengan
d data
d t kke-2 karena
k data
d t pertama
t
pasti sudah paling kecil.
Pengurutan Berhenti Di Sini
Tidak ada penukaran
p
karena 10<15
Pengurutan berhenti di sini
Pengurutan berhenti di sini
y Keuntungan
g lain dari algoritma
g ini adalah dapat
p dijalankan
j dengan
g
cukup
k cepat dand efisien
f untuk
k mengurutkan
k list
l yang urutannya sudahd h
hampir benar.
y Selain kasus terbaik tersebut, komleksitas untuk algoritma ini adalah
O(n²).
y Karenanya algoritma ini termasuk sangat tidak efisien untuk dilakukan,
apalagi jika pengurutan dilakukan terhadap elemen yang banyak
jumlahnya.
y Biasanya bubble sort digunakan untuk mengenalkan konsep dari sorting
algoritma pada pendidikan komputer karena idenya yang cukup
sederhana.
METODE SORTING
3. SELECTION SORT
PENDAHULUAN
y Metode selection sort merupakan perbaikan dari metode
bubble sort dengan mengurangi jumlah perbandingan .
y Selection sort merupakan metode pengurutan yang
mencari nilai data terbesar atau terkecil dan kemudian
menempatkannya pada posisi yang sebenarnya, dimulai
dari data diposisi 0 hingga data diposisi N-1.
y Sedangkan metode insertion sort adalah metode
pengurutan yang biasa dipakai oleh pemain kartu dalam
mengurutkan kartunya,
kartunya yaitu menyisipkan kartu dengan
nilai yang lebih kecil ke posisi sebelum kartu
pembandingnya.
y Selection Sort merupakan kombinasi antara sorting dan
searching
searching.
y Untuk setiap proses, akan dicari elemen-elemen yang
belum diurutkan yang memiliki nilai terkecil atau terbesar
akan dipertukarkan ke posisi yang tepat di dalam array.
array
y Misalnya untuk putaran pertama, akan dicari data dengan
nilai terkecil dan data ini akan ditempatkan di indeks
terkecil (data[0]),
(data[0]) pada putaran kedua akan dicari data
kedua terkecil, dan akan ditempatkan di indeks kedua
(data[1]).
y Selama proses,
proses pembandingan dan pengubahan hanya
dilakukan pada indeks pembanding saja, pertukaran data
secara fisik terjadi pada akhir proses.
y Tehnik pengurutan dgn cara pemilihan elemen atau proses
kerja
e ja dg
dgn memilih
e eelemen
e e data te
terkecil
ec ut
utk kemudian
e ud a
dib di k & ditukarkan
dibandingkan di k k dgn d elemen
l pd
dddata awal,
l dst
d
s/d seluruh elemen shg akan menghasilkan pola data yg
telah disort.
y Kelebihan dan kekurangan
g Selection Sort:
{ Kompleksitas selection sort relatif lebih kecil.
{ Mudah menggabungkannya kembali, tetapi sulit membagi masalah.
{ Membutuhkan method tambahan.
y Kondisi awal:
{ Unsorted list = data
{ Sorted list = kosong
y Ambil yang terbaik (select) dari unsorted list, tambahkan
di belakang sorted list.
y Lakukan
L k k terus
t sampaii unsorted
t d li
listt habis.
h bi
Selection sort contoh
40 2 1 43 3 65 0 -1
1 58 3 42 4
40 2 1 43 3 4 0 -1
1 58 3 42 65
40 2 1 43 3 4 0 -1
1 42 3 58 65
40 2 1 3 3 4 0 -1 42 43 58 65
Selection sort: Contoh (lanj.)
40 2 1 3 3 4 0 -1
1 42 43 58 65
-1 2 1 3 3 4 0 40 42 43 58 65
-1 2 1 3 3 0 4 40 42 43 58 65
-1 2 1 0 3 3 4 40 42 43 58 65
Selection sort: Contoh (lanj.)
-1 2 1 0 3 3 4 40 42 43 58 65
-1 0 1 2 3 3 4 40 42 43 58 65
-1 0 1 2 3 3 4 40 42 43 58 65
-1 0 1 2 3 3 4 40 42 43 58 65
-1 0 1 2 3 3 4 40 42 43 58 65
METODE SORTING
4. INSERTION SORT
Insertion Sort
y Prinsip dasar Insertion adalah secara berulang-
ulang
l menyisipkan
i i k / memasukan k setiap
ti elemen.
l k
ke
dlm posisinya / tempatnya yg benar.
y Mirip dengan cara orang mengurutkan kartu,
selembar demi selembar kartu diambil dan
disisipkan (insert) ke tempat yang seharusnya.
y Pengurutan dimulai dari data ke-2
ke 2 sampai dengan
data terakhir, jika ditemukan data yang lebih
kecil, maka akan ditempatkan (diinsert) diposisi
yang seharusnya.
h P
Pada
d penyisipan
i i elemen,
l maka
k
elemen-elemen lain akan bergeser ke belakang
Insertion Sort
y Kondisi awal:
{ Unsorted list = data
{ Sorted list = kosong
y Ambil sembarang elemen dari unsorted list, sisipkan
(insert) pada posisi yang benar dalam sorted list.
y Lakukan
L k k terus
t sampaii unsorted
t d list
li t h
habis.
bi
y Bayangkan anda mengurutkan kartu.
Insertion sort: Contoh
40 2 1 43 3 65 0 -1 58 3 42 4
2 40 1 43 3 65 0 -1 58 3 42 4
1 2 40 43 3 65 0 -1 58 3 42 4
Insertion sort: Contoh (lanj.)
1 2 40 43 3 65 0 -1 58 3 42 4
1 2 3 40 43 65 0 -1 58 3 42 4
1 2 3 40 43 65 0 -1 58 3 42 4
Insertion sort: Contoh (lanj.)
1 2 3 40 43 65 0 -1 58 3 42 4
0 1 2 3 40 43 65 -1 58 3 42 4
-1
0 1
0 2
1 3
2 40
3 40
43 43
65 65 58 3 42 4
Insertion sort: Contoh (lanj.)
-1
0 1
0 2
1 3
2 40
3 40
43 43
65 58 65 3 42 4
-1
0 1
0 2
1 3
2 40
3 43
3 40
65 43
43 58 58
65 65 42 4
-1
0 1
0 2
1 3
2 40
3 43
3 40
65 42 43
43 65 58 65 4
-1
0 1
0 2
1 3
2 40
3 43
3 43
65
4 40
42 42
65 43
43 58 58
65 65
METODE SORTING
5. QUICK SORT
METODE QUICK SORT
y Qick sort banyak digunakan utk proses sorting,karena:
{ merupakan
k proses sorting
i yang umum digunakan
di k
{ mudah untuk diimplementasikan
{ Prosesnya sangat cepat
y Aturan
At Q i kS
Quick Sort:
t
{ Select
Ù Pertama kita pilih elemen yang ditengah sebagai pivot, misalkan X.
{ Partition
Ù kemudian semua elemen tersebut disusun dengan menempatkan X
pada posisi j sedemikian rupa sehingga elemen disebelah kiri1 lebih <
X dan elemen sebelah kanan > X.
{ R k
Rekursifif
Ù Kemudian proses diulang untuk bagian kiri dan kanan elemen X
dengan cara yg sama dengan langkah 1 sampai kondisi terurut
ALGORITMA QUICK SORT
algoritma quicksort
deskripsi
x data[(L+R) div 2]
I L
J R
while ( I < = J ) do
while (data[I] < x ) do inc( I ) endwhile
while ( data[J] > x ) do dec( J ) endwhile
If ( I < = J ) then
tukar(data[I],data[j])
k (d [I] d [j])
inc( I )
Dec( J )
endif
endwhile
If ( L < J ) then quicksort(larikpixel, L, J )
If ( I < R ) then quicksort(larikpixel, I, R )
METODE SORTING
6. HEAP SORT
METODE HEAP SORT
y Adalah binary
y tree dengan
g menggunakan
gg kunci,,
dimana mempunyai aturan-aturan sebagai berikut :
Ù untuk mengisikan heap dimulai dari level 1 sampai ke level
dibawahnya bila dalam level yang sama semua kunci heap belum
dibawahnya,
terisi maka tidak boleh mengisi dibawahnya.
Ù heap dlm kondisi terurut apabila left child < parent dan right child >
p
parent
Ù penambahan kunci diletakkan pada posisi terakhir dari level dan
disebelah kanan child yg terakhir, kemudian diurutkan dengan cara
upheap
Ù Bila menghapus heap dgn mengambil kunci pada parent di level 1
kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali
metode downheap
HEAP REPRESENTATION
y Array
y Left_child(i)
Left child(i) = 2i
y Right_chilrd = 2i +1
y Parent = j div 2
HEAP SORT
y Metode Upheap:
{ bandingkan kunci terakhir dengan parentnya apabila parent < kunci
maka lakukan pertukaran.
{ ulangi
g langkah
g 1 dengan
g membandingkan
b g dengan
g pparent selanjutnya
j y
sampai posisi parent di level 1 selesai dibandingkan
y Metode
M d Downheap:
D h
{ bandingkan parent dengan leftchild dan rightchild apabila parent <
leftchild atau rightchild maka lakukan pertukaran.
{ ulangi langkah 1 dengan membandingkan dengan leftchild dan
rightchild pada posisi level dibawahnya sampai posisi di level
terakhir selesai dibandingkan.
DAFTAR PUSTAKA
y DF Alfatwa, ER Syah P, FM Ahsan, “Implementasi Algoritma
Radix Sort dalam Berbagai Kasus Bilangan Dibandingkan
Algoritma Pengurutan yang lain
lain”. Bandung.
Bandung 2005.
2005
y Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Introduction To Algorithms, McGraw- Hill. 1990.
y Handbook
a dboo U UI,, Algoritma-algoritma
go a a go a pe
pengurutan
gu u a internal
e a
[Link]
tml Tanggal akses : 29 Desember 2007 pukul 04.00 GMT +7
y Wikipedia, (2007). Wikipedia, the free encyclopedia.
[Link] wikipedia org/wiki/Counting Sort Tanggal akses : 29
[Link]
Desember 2007 pukul 04.00 GMT +7
y Wikipedia, (2007). Wikipedia, the free encyclopedia.
p // p g/ / g g
[Link] Tanggal
gg akses :
29 Desember 2007 pukul 04.00 GMT +7
y Wikipedia, (2007). Wikipedia, the free encyclopedia.
[Link] Tanggal akses : 29
Desember 2007 pukul 04.00
04 00 GMT +7