pb11mat_pert11 algoritma pemrograman.ppt

algoritma pemrograman

1. Pengurutan (sorting)

2. DEFINISI SORT
•Sorting = pengurutan
•Sorted = terurut menurut kaidah/aturan tertentu
•Data pada umumnya disajikan dalam bentuk sorted.
•Contoh:
•Data Mahasiswa
•Kata-kata dalam kamus
•File-file di dalam sebuah directory
•Indeks sebuah buku
•Data mutasi rekening tabungan
•dll
•Bayangkan jika data di atas tidak terurut!

3. Metode Sorting
•Metode:
–ascending (urut naik)
–descending (urut turun)
•contoh
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25 ; Amir Budi Badu Dudi
Descending : 25 10 8 6 5 3 1

4. Sorting-1
•Bentuk:
–Ascending if N obyek disimpan dalam
larik L, then menyusun elemen larik
L[1] ≤ L[2] ≤ L[3] ≤ …≤ L[N]
–Descending if N obyek disimpan dalam
larik L, then menyusun elemen larik
L[1] ≥ L[2] ≥ L[3] ≥ … ≥ L[N]

5. Tujuan sorting
•Mudah dalam Membaca data
•Mudah dalam menemukan data
•Penyajian data lebih teratur
•dll

6. Jenis Algoritma Sorting
•Beberapa algoritma untuk melakukan
sorting:
–Bubble sort
–Selection sort
–Insertion sort
–Shell sort

7. (Bubble Sort/pengurutan gelembung)
•Metode sorting termudah
•Bubble Sort mengurutkan data dengan cara
membandingkan elemen sekarang dengan elemen
berikutnya.
•Ascending :
if elemen sekarang > dari elemen berikutnya
then kedua elemen ditukar
•Descending:
if elemen sekarang < dari elemen berikutnya
then kedua elemen ditukar

8. Bubble Sort (2)
Algoritma:
banyaknya data: n
Data diurutkan/disorting dari yang bernilai besar
Proses
step 1 :
Periksalah nilai dua elemen mulai dari urutan ke-n sampai
urutan ke-1. Jika nilai kiri<kanan, tukarkan kedua data itu.
step 2 :
Periksalah nilai dua elemen mulai dari urutan ke-n sampai
urutan ke-2. Jika nilai kiri<kanan, tukarkan kedua data itu.
step n-1 :
Periksalah nilai dua elemen mulai dari urutan ke-n sampai
urutan ke-n-1. Jika nilai kiri<kanan, tukarkan kedua data itu.

9. Bubble Sort: pseudocode
BUBBLESORT(A)
1for i←1 to length[A]
2 do for j←length[A] downto i+1
3 do if A[j] < A[j-1]
4 then exchange A[j] ↔ A[j-1]

10. banyaknya data: n
Data diurutkan/disorting dari yang bernilai
besar
Proses
step 1 : Periksalah nilai dua elemen mulai
dari urutan ke-n sampai urutan ke-1. Jika
nilai kiri<kanan, tukarkan kedua data itu.
step 2 : Periksalah nilai dua elemen mulai
dari urutan ke-n sampai urutan ke-2. Jika
nilai kiri<kanan, tukarkan kedua data itu.
…
Contoh Algoritma: BUBBLE SORT

11. step n-1 : Periksalah nilai dua elemen
mulai dari urutan ke-n sampai
urutan ke-n-1. Jika nilai kiri<kanan, tukarkan
kedua data itu.

12. 7 4 5 8 10Awal
Bubble Sort: tahap demi tahap

13. 7 4 5 8 10
7 4 5 8 10Step-1
Awal
Bubble Sort: tahap demi tahap

14. 7 4 5 8 10
7 4 5 10 8Step-1
Awal
Bubble Sort: tahap demi tahap

15. 7 4 5 8 10
7 4 10 5 8Step-1
Awal
Bubble Sort: tahap demi tahap

16. 7 4 5 8 10
7 10 4 5 8Step-1
Awal
Bubble Sort: tahap demi tahap

17. 7 4 5 8 10
10 7 4 5 8Step-1
Awal
Bubble Sort: tahap demi tahap

18. 7 4 5 8 10
10 7 4 5 8
10 7 4 5 8
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap

19. 7 4 5 8 10
10 7 4 5 8
10 7 4 8 5
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap

20. 7 4 5 8 10
10 7 4 5 8
10 7 8 4 5
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap

21. 7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap

22. 7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 4 5
Step-1
Awal
Step-2
Step-3
Bubble Sort: tahap demi tahap

23. 7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 5 4
Step-1
Awal
Step-2
Step-3
Bubble Sort: tahap demi tahap

24. 7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 5 4
Step-1
Awal
Step-2
Step-3
Bubble Sort: tahap demi tahap

25. 7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 5 4
10 8 7 5 4
Step-1
Awal
Step-2
Step-3
Step-4
Bubble Sort: tahap demi tahap

26. Selection Sort
•Merupakan kombinasi antara sorting dan searching
•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.
•Misalnya untuk putaran pertama, akan dicari data
dengan nilai terkecil dan data ini akan ditempatkan di
indeks terkecil (data[0]), pada putaran kedua akan dicari
data kedua terkecil, dan akan ditempatkan di indeks
kedua (data[1]).
•Selama proses, pembandingan dan pengubahan hanya
dilakukan pada indeks pembanding saja, pertukaran
data secara fisik terjadi pada akhir proses.

27. Selection Sort: Pseudocode
SELECTIONSORT(A)
1for i← 1 to length[A]-1
2 min = i;
3 do for j ← i+1 to length[A]
4 do if A[j] < A[min]
5 min = j;
6 exchange A[min] ↔ A[i]
Prinsip kerja:
Dari elemen sebanyak n,
Carilah elemen terkecil dari array A, dan swap-lah elemen terkecil
tersebut dengan elemen pertama (A[1] ).
Carilah elemen terkecil kedua dari array A, dan swap-lah elemen
tersebut dengan elemen kedua (A[2])
Ulangi sampai n-1 elemen pertama dari array A

28. Selection Sort: contoh
524613
123456
1





2







3






4






5







6
124653
124653
123654
123456
Carilah elemen terkecil &
tukar dengan “5”
1 fixed. Carilah elemen terkecil
& tukar dengan “2”
1,2 fixed. Carilah elemen
terkecil & tukar dengan “4”
1,2,3 fixed. Carilah elemen
terkecil & tukar dengan “6”
1,2,3,4 fixed. Carilah elemen
terkecil & tukar dengan “5”
1,2,3,4,5 fixed, otomatis elemen
terakhir sudah pada posisi yang
benar
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6

29. Insertion Sort
•Mirip dengan cara orang mengurutkan kartu,
selembar demi selembar kartu diambil dan
disisipkan (insert) ke tempat yang seharusnya.
•Pengurutan dimulai dari data ke-2 sampai
dengan data terakhir, jika ditemukan data yang
lebih kecil, maka akan ditempatkan (diinsert)
diposisi yang seharusnya.
•Pada penyisipan elemen, maka elemen-elemen
lain akan bergeser ke belakang

30. Insertion Sort: pseudocode
INSERTION-SORT(A)
1 for j←2 to length[A]
2 do key←A[j]
3Insert A[j] ke sekuens yang sudah disorting A[1…j-1]
4i← j-1
5while i>0 and A[i] > key
6do A[i+1] ←A[i]
7i ← i -1
8A[i+1] ←key

31. Insertion Sort: contoh
524613
1 2 3 4 5 6
254613
1 2 3 4 5 6
245613
1 2 3 4 5 6
245613
1 2 3 4 5 6
124563
1 2 3 4 5 6
123456
1 2 3 4 5 6
1





2







3






4






5







6

32. Shell Sort(1)
•Metoda pertambahan menurun (diminishing
increment).
•Metoda dikembangkan oleh Donald L. Shell
tahun 1959.
•Metoda ini memanfaatkan penukaran
sepasang elemen untuk mencapai keadaan
urut. Dalam hal ini jarak dua elemen yang
dibandingkan dan ditukarkan tertentu.

33. Shell Sort(2)
•Algoritma ini bisa dipandang sebagai modifikasi dari algoritma
Insertion Sort, lebih tepatnya memanfaatkan kondisi-kondisi
positif dari Insertion Sort.
•Keuntungan:
1.Insertion Sort bisa sangat efisien untuk data dalam kondisi
hampir terurut.
2.Karena Insertion Sort sangat sederhana, maka overhead cost
untuk proses-proses tambahannya pun amat kecil sehingga
untuk jumlah data n yang kecil masih bisa lebih cepat dari
algoritma O(n log n).

34. Algoritma Shell Sort
•Langkah pertama, ambil elemen pertama dan kita bandingkan
dengan elemen pada jarak tertentu dari elemen pertama
tersebut.
•Kemudian elemen kedua dibandingkan dengan elemen lain
dengan jarak yang sama.
•Demikian seterusnya sampai seluruh elemen dibandingkan.

35. 4021433650-1583424
Original:
5-sort: Sort setiap item yang berjarak 5:
4021433650-1583424
Shell sort

36. 4021433650-1583424
Original:
400-14334221583654
After 5-sort:
20-131440342436558
After 3-sort:
Shell sort
After 1-sort:
1234043650 42123343 650-1 584 43 6542 5840 43 65

37. Shell sort: Gap values
•Gap: jarak antara elemen yang di-sort.
•Seiring berjalannya waktu, gap diperkecil. Shell sort
juga dikenal sebagai Diminishing Gap Sort.
•Shell mengusulkan mulai dengan ukuran awal gap =
N/2, dan dibagi 2 setiap langkah.
•Ada banyak variasi pemilihan gap.

38. Shell's Nilai gap ganjilDibagi 2.2
1000 122 11 11 9
2000 483 26 21 23
4000 1936 61 59 54
8000 7950 153 141 114
16000 32560 358 322 269
32000131911 869 752 575
64000520000 2091 1705 1249
Shell sort
N
Insertion
sort
O(N
3/2
) O(N
5/4
) O(N
7/6
)
Kinerja Shell sort
Ada 3 “nested loop”, tetapi Shell sort masih lebih baik
dari Insertion sort. Mengapa?