pb11mat_pert11 logika & algoritma pemrograman.ppt

logika & 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. Contoh Algoritma: BUBBLE SORT
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.
…

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]
←
3 Insert A[j] ke sekuens yang sudah
disorting A[1…j-1]
4 i j-1
←
5 while i>0 and A[i] > key
6 do A[i+1] A[
←
i]
7 i
←
i -1
8 A[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?