Algoritma Sorting (Selection – Insertion)
Algoritma Insertion Sort • Dengan Algoritma Insertion bagian kiri array terurut sampai seluruh array • Misal pada data array ke-k, data tersebut akan disisipkan pada indeks sebelum k, sesuai dengan urutannya. Proses ini dilakukan berulang-ulang sehingga seluruh data terurut
Algoritma Insertion Sort 1. i 1 2. selama (i < N) kerjakan baris 3 sampai dgn 9
3. key A[i] 4. j i – 1
C = Comparison
5. selama j >= 0 dan (A[j] > key) kerjakan baris 6 dan 7
6. A[j + 1] A[j]
M = Move
7. j j – 1 8. A[j+1] key
9. i i + 1
M = Move
Proses Insertion Sort 3
10
4
6
8
9
7
2
1
5
Nilai yang paling kiri (3) terurut terhadap dirinya sendiri. Sehingga kita tidak perlu melakukan apa-apa
3
10
4
6
8
9
7
2
1
5
3
10
4
6
8
9
7
2
1
5
Key = 10
Cek apakah nilai pada indek ke-2 (10) lebih kecil dari indek ke-1 (3). Jika ya maka tukar. Kondisi diatas maka data tidak perlu diswap
3
10
4
6
8
9
7
2
1
5
1
5
Dua data pertama sudah terurut
3
10
4
6
8
9
7
2
Selanjutnya menyisipkan 4 di daerah abuabu sehingga setelah penyisipan daerah abu-abu menjadi urut.
Simpan nilai yang akan diurutkan dalam variabel key Key = 4 C C = Comparison
4
3
10
6
8
9
7
2
1
5
Nilai 10 digeser pada indek ke-3 M
3
4 10
M = Move 6
8
9
7
2
1
5
7
2
1
5
Sisipkan 4 pada posisi yang tepat
3
4
10
6
8
9
Sekarang 3 data pertama sudah terurut secara relatif dan sisipkan data ke-4 ke daerah abu-abu. 4 Data pertama sudah terurut secara relatif
3
4
6
10
8
9
7
2
1
5
Ulangi Proses ini sampai data terurut semuanya.
3
4
6
8
10
9
7
2
1
5
3
4
6
8
9
10
7
2
1
5
7 3
4
6 8
9
10
2
1
5
3
4
6
7
8
9
10
2
1
5
2
3
4
6
7
8
9
10
1
5
1
2
3
4
6
7
9
10
5
1
2
3
4
5
6
8
9
10
8 7
Analisa Insertion Sort • Basic Operation (Operasi Dasar) terdapat pada perbandingan key (A[j] > key)
Analisa Insertion Sort Best Case - Array sudah dalam keadaan terurut naik - Data ke-k yang akan diurutkan dibandingkan sebanyak satu kali dengan data ke- (k-1) - Loop terdalam tidak pernah dieksekusi - Jumlah pergeseran (movement) M = 0 - Jumlah pembandingan key (comparison) C =
n – 1
Worst Case: - Array dalam urutan kebalikannya
- Loop terdalam dieksekusi sebanyak p-1 kali, untuk p = 2,3,..,n - Jumlah pergeseran
M = (n-1) + (1 + 2 + .. + n-1) M = (n-1) +
n * ( n-1)/2
- Jumlah pembandingan key C =
(1 + 2 + .. + n-1) = n * (n-1) / 2
Selection Sort
Algoritma Selection Sort 1.
i0
2.
selama (i < N-1) kerjakan baris 3 sampai dengan 11
3.
min i
4.
ji+1
5.
Selama (j < N) kerjakan baris 6 dan 7
6.
Jika (A[j] < A[min]) maka min j
7.
jj+1
8.
temp = A[i]
9.
A[i] = A[min]
10. A[min] = temp
11.
ii+1
Selection Sort Algorithm Min = 0
Perbandingan diawali pada dat indeks ke-0. Dibandingkan dengan data sesudahnya untuk mencari elemen yang paling kecil (menggunakan indeks data)
(A[j] < A[min]) ? min j
j=1 70
61
60 50
52 45
40 30
21
20
9
15
10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 15
Selection Sort Algorithm – 1 Min = 0
Data ke-0 dibandingkan dengan data ke-1. Ternyata data min pada indeks ke-1 (min=1)
21 < 45 min = 1
j=1 70
61
60 50
52 45
40 30
21
20
9
15
10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 16
Selection Sort Algorithm – 2 Min = 1
Data ke1 dibandingkan dengan Data ke-2. Nilai yang paling kecil tetap pada data indeks ke1
52 < 21 min = 1
j=2 70
61
60 50
52 45
40 30
21
20
9
15
10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 17
Selection Sort Algorithm – 3 Min = 1
Data ke1 dibandingkan dengan Data ke-3
61 < 21 min = 1
j=3 70
61
60 50
52 45
40 30
21
20
9
15
10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 18
Selection Sort Algorithm – 4 Min = 1
Data ke1 dibandingkan dengan Data ke-4. Data yang paling kecil sekarang pada data indeks ke-4 (min =4)
9 < 21 min = 4
j=4 70
61
60 50
52 45
40 30
21
20
9
15
10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 19
Selection Sort Algorithm – 5 Min = 4
Data ke-4 dibandingkan dengan Data ke-5
15< 9 min = 4
j=5 70
61
60 50
52 45
40 30
21
20
9
15
10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 20
Selection Sort Algorithm – 2 • Diawali dengan mencari elemen 70 yang paling kecil 60 • Tukar elemen 50 yang paling kecil 40 dengan Data 30 indeks ke-0 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 21
Selection Sort Algorithm – 3
Diawali dengan mencari elemen yang paling kecil Tukar elemen yang paling kecil dengan Data indeks ke-0
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 22
Selection Sort Algorithm – 4 Sudah terurut
• Bagian dari Data yang sudah terurut
Belum terurut
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 23
Selection Sort Algorithm – 5 Sudah terurut
Belum terurut
70
• Cari elemen 60 terkecil pada 50 bagian yang 40 belum 30 terurut 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 24
Selection Sort Algorithm – 6 Sudah terurut
Belum terurut
70
• Diawali dengan 60 mencari elemen yang 50 40 paling kecil • Tukar dengan 30 data paling 20 depan pada 10 daerah yang belum terurut 0
[1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 25
Selection Sort Algorithm – 7 Sudah terurut
• Dua data telah terurut
Belum terurut
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 26
Selection Sort Algorithm – 8 Sudah terurut
• Proses dilanjutkan
Belum terurut
70 60
Elemen terkecil
50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 27
Selection Sort Algorithm – 9 Sudah terurut
• Proses dilanjutkan
Belum terurut
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 28
Selection Sort Algorithm – 10 Sudah terurut
• Proses dilanjutkan
Belum terurut
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 29
Selection Sort Algorithm – 11 Sudah terurut
Belum terurut
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 30
Selection Sort Algorithm – 12 • Berhenti pada saat bagian yang terurut tinggal hanya satu Data karena Data yang ada pasti bilangan yang paling besar
Sudah terurut
Belum teruru
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 31
Selection Sort Algorithm – 13 • Data sudah terurut
70 60 50 40 30 20 10 0 [1] [0]
[2] [1]
[3] [2]
Slide copyright Pearson Education 2002
[4] [3]
[5] [4]
[6] [5] 32
Analisa Selection Sort Basic Operasi (A[j] < A[min]) Tidak ada Best Case dan Worst Case Total pergeseran M = 3 * n-1 (pada setiap penukaran terjadi 3 x pergeseran)
Jumlah pembandingannya C = 1 + 2 + .. + n-1 = n*(n-1)/2
