SORTING
• Sort : proses untuk
menyusun kembali himpunan objek dengan menggunakan aturan tertentu.
• Dua jenis sort :
• Ascending : pengurutan data dari yang terkecil sampai data yang
terbesar
• Descending : pengurutan data dari yang terbesar sampai data yang terkecil
• Tujuan sorting : data mudah dicari, dibetulkan, disisipi,
dihapus, dan digabungkan
Tehnik-tehnik sorting
• Insertion Sort (sortir penyisipan)
• Selection Sort (sortir pemilihan)
• Bubble short/ Exchange sort (sortir penukaran)
• Quick sort (sortir cepat)
Insertion Sort (sortir penyisipan)
• Tehnik ini adalah dengan membandingkan elemen ke-n (n mulai dari
2 hingga elemen terakhir) dengan elemen-elemen sebelumnya. Bila elemen yang
dibandingkan lebih kecil, maka sisipkan posisinya.
• contoh : 8, 3, 7, 4
• Berapa langkah yang terbentuk untuk pensortiran??
(awal) : 8, 3, 7, 4
Sisipkan posisi ke 2 = 3 Hasil
: 3, 8, 7, 4
Sisipkan posisi ke 3 = 7 Hasil
: 3, 7, 8, 4
Sisipkan posisi ke 4 = 4 Hasil
: 3, 4, 7, 8
Hasil akhir :
3 langkah
(awal) : 5, 34, 32,
25, 75, 42, 22, 2
Sisipkan pss ke 2 = 34
Hasil : 5, 34, 32, 25, 75, 42, 22, 2
Sisipkan pss ke 3 = 32
Hasil : 5, 32, 34, 25, 75, 42, 22, 2
Sisipkan pss ke 4 = 25
Hasil : 5, 25, 32, 34,
75, 42, 22, 2
Sisipkan pss ke 5 = 75
Hasil : 5, 25, 32, 34, 75, 42, 22, 2
Sisipkan pss ke 6 = 42
Hasil : 5, 25, 32, 34, 42, 75, 22, 2
Sisipkan pss ke 7 = 22
Hasil : 5, 22, 25, 32, 34, 42, 75, 2
Sisipkan pss ke 8 = 2
Hasil : 2, 5, 22, 25, 32, 34, 42, 75
Hasil akhir = 7 langkah
Selection Sort (sortir pemilihan)
• Tehnik ini adalah mencari elemen terkecil kemudian letakkan dan
tukar dengan posisi ke-n (n mulai dari 1 hingga elemen terakhir -1)
• contoh : 8, 3, 7, 4
• Berapa langkah yang terbentuk untuk pensortiran??
(awal) : 8, 3, 7, 4
Tukar 3 dengan 8 Hasil
: 3, 8, 7, 4
Tukar 4 dengan 8 Hasil
: 3, 4, 7, 8
Tukar 7 dengan 8 Hasil
: 3, 4, 7, 8
Hasil akhir =
3 langkah
(awal) : 5, 34, 32,
25, 75, 42, 22, 2
Tukar 2 dgn 5 Hasil : 2, 34, 32, 25, 75,
42, 22, 5
Tukar 5 dgn 34 Hasil
: 2, 5, 32, 25, 75, 42, 22, 34
Tukar 22 dgn 32 Hasil
: 2, 5, 22, 25, 75, 42, 32, 34
Tukar 25 dgn 75 Hasil
: 2, 5, 22, 25, 75, 42, 32, 34
Tukar 32 dgn 75 Hasil
: 2, 5, 22, 25, 32, 42, 75, 34
Tukar 34 dgn 42 Hasil
: 2, 5, 22, 25, 32, 34, 75, 42
Tukar 42 dgn 75 Hasil
: 2, 5, 22, 25, 32, 34, 42, 75
Hasil akhir =
7 langkah
Exchange sort (sortir penukaran) disebut juga buble short
• Algoritma dari tehnik ini adalah dengan melakukan proses
perbandingan sebanyak n elemen dimulai dari n = 1 (selanjutnya disebut mulai =
1)
• Bandingkan seluruh elemen dimulai dari elemen sebelah kanan
hingga ke-n. bila elemen tersebut lebih kecil dari mulai, maka lakukan pertukaran
tempat.
• Lakukan pada elemen mulai +1 seperti proses sebelumnya hingga
mulai +1 = n
Contoh data : 8, 3, 7, 4
Pass 1 : bandingkan
elemen pertama dengan elemen-elemen selanjutnya
Pass 1 : proses 1,
bandingkan 8 dengan 3
:
Hasil 3, 8, 7, 4
:
proses 2, bandingkan 3 dengan 7
:
Hasil 3, 8, 7, 4
:
proses 3, bandingkan 3 dengan 4
:
Hasil 3, 8, 7, 4
Pass 1 selesai. Diperoleh : 3, 8, 7, 4
Pass 2 : bandingkan
elemen kedua dengan elemen-elemen selanjutnya
Pass 2 : proses 1,
bandingkan 8 dengan 7
:
Hasil 3, 7, 8, 4
:
proses 2, bandingkan 7 dengan 4
:
Hasil 3, 4, 8, 7
Pass 2 selesai. Diperoleh : 3, 4, 8, 7
Pass 3 : bandingkan
elemen ketigadengan elemen-elemen selanjutnya
Pass 3 : proses 1,
bandingkan 8 dengan 7
:
Hasil 3, 4, 7, 8
Hasil akhir : Pass 1 = 3 langkah
Pass
2 = 2 langkah
Pass
3 = 1 langkah
Hasil akhir
: 6 langkah
(awal) : 5, 34, 32,
25, 75, 42, 22, 2
Pass 1 : 5 dgn 34 : 5, 34, 32, 25, 75, 42, 22, 2
:
5 dgn 32 : 5, 34, 32, 25,
75, 42, 22, 2
:
5 dgn 25 : 5, 34, 32, 25,
75, 42, 22, 2
:
5 dgn 75 : 5, 34, 32, 25, 75,
42, 22, 2
:
5 dgn 42 : 5, 34, 32, 25, 75, 42,
22, 2
:
5 dgn 22 : 5, 34, 32, 25, 75,
42, 22, 2
:
5 dgn 2 : 2, 34, 32, 25, 75,
42, 22, 5
Pass 1 : 2,
34, 32, 25, 75, 42, 22, 5
Pass 2 : 34 dg 32 : 2, 32, 34, 25, 75, 42, 22, 5
: 32 dg 25 :
2, 25, 34, 32, 75, 42, 22, 5
: 25 dg 75 :
2, 25, 34, 32, 75, 42, 22, 5
: 25 dg 42 :
2, 25, 34, 32, 75, 42, 22, 5
: 25 dg 22 :
2, 22, 34, 32, 75, 42, 25, 5
: 22 dg 5 :
2, 5, 34, 32, 75, 42, 25, 22
Pass 2 : 2,
5, 34, 32, 75, 42, 25, 22
Pass 3 : 34 dg 32 : 2, 5, 32, 34, 75, 42, 25, 22
:
32 dg 75 : 2, 5, 32, 34, 75,
42, 25, 22
:
32 dg 42 : 2, 5, 32, 34, 75, 42,
25, 22
:
32 dg 25 : 2, 5, 25, 34, 75, 42,
32, 22
:
25 dg 22 : 2, 5, 22, 34, 75, 42,
32, 25
Pass 3 : 2,
5, 22, 34, 75, 42, 32, 25
Pass 4 : 34 dg 75 : 2, 5, 22, 34, 75, 42, 32, 25
:
34 dg 42 : 2, 5, 22, 34, 75, 42,
32, 25
:
34 dg 32 : 2, 5, 22, 32, 75, 42,
34, 25
:
32 dg 25 : 2, 5, 22, 25, 75, 42,
34, 32
Pass 4 : 2,
5, 22, 25, 75, 42, 34, 32
Pass 5 : 75 dg 42 : 2, 5, 22, 25, 42, 75, 34, 32
:
42 dg 34 : 2, 5, 22, 25, 34, 75,
42, 32
:
34 dg 32 : 2, 5, 22, 25, 32, 75,
42, 34
Pass 6 : 75 dg 42 : 2, 5, 22, 25, 32, 42, 75, 34
:
42 dg 34 : 2, 5, 22, 25, 32, 34,
75, 42
Pass 7 : 75 dg 42 : 2, 5, 22, 25, 32, 34, 42, 75
Quick sort
• Metode pengurutan yang membandingkan suatu elemen dengan elemen
yang lain, sehingga menjadi elemen yang terletak lebih besar disebelah kanan
pivot, dan elemen yang lebih kecil terletak disebelah kiri pivot.
• Nilai pivot < nilai sebelah kiri
• Pivot berada didalam kurung
• Tukar nilai sebelah kiri pivot dengan kanan pivot
awal :
8, 3, 7, 4
Langkah 1 : 8,
(3), 7, 4
Langkah 2 : 3, 8,
(7), 4
Langkah 3 : 3, 4,
7, 8
Awal : 5,
34, 32, 25, 75, 42, 22, 2
Langkah 1 : 5,
34, (32), 25, 75, 42, 22, 2
Langkah 2 : 5,
(2), 32, 25, 75, 42, 22, 34
Langkah 3 : 2, 5,
32, (25), 75, 42, 22, 34
Langkah 4 : 2, 5,
22, 25, 75, (42), 32, 34
Langkah 5 : 2, 5,
22, 25, 32, 42, 75, (34)
Langkah 6 : 2, 5,
22, 25, 32, 42, (34), 75
Langkah 7 : 2, 5,
22, 25, 32, 34, 42, 75
