ALGORITMA DAN PEMROGRAMAN 2
3 SKS
By : Sri Rezeki Candra Nursari
MATERI Teks/string Pointer File Struktur Kelas/Class Konstruktor dan Destruktor • Kelas dan Obyek • • • • • •
Overloading Operator Inheritance (Pewarisan) Polimorfisme Template Fungsi dan Kelas • Sort • Search • • • •
SELEKSI/SELECTION SORT Pertemuan 13
3 SKS
SORT • Sort adalah suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut. • Pengurutan terbagi menjadi 2 yaitu : –Ascending (pengurutan dari kecil ke besar) –Descending (pengurutan dari besar ke kecil)
SORT • Untuk masalah pengurutan pada array kita tidak dapat langsung menukar isi dari variabel yang ada, tetapi menggunakan metode swap • Macam-macam metode pengurutan, yaitu : – Selection Sort (Metode pengurutan seleksi) – Insertion Sort (Metode pengurutan sisip langsung) – Bubble Sort (Metode pengurutan gelembung)
Selection Sort (Metode pengurutan seleksi) • Melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot • Suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya sampai ke elemen yang terakhir. • Jika ditemukan elemen lain yang kecil elemen sekarang maka dicatat posisinya dan langsung dilakukan penukaran
Selection Sort (Metode pengurutan seleksi)
• Proses pengurutan dengan metode seleksi adalah 1. Dilakukan pengulangan dari 1 sampai dengan (N-1) 2. Tiap-tiap pengulangan dicari data yang paling kecil di antara data ke (i+1) sampai dengan data terakhir (=N) 3. Data terkecil ini kemudian ditukarkan dengan pivot, yaitu data ke-i 4. Apabila data terkecil tersebut lebih besar daripada data ke-i, proses penukaran tidak perlu dilakukan
Selection Sort (Metode pengurutan seleksi)
• Algoritmanya sebagai berikut : 1. 2. 3. 4. 5. 6. 7. 8. 9.
i1 Selama (i <= N-1) kerjakan baris 3 s.d. 9 ki ji+1 Selama (j <= N) kerjakan baris 6 s.d. 7 Jika (Data[k] > Data[j]) maka k j jj+1 Tukar Data [i] dengan Data [k] ii+1
Pengurutan Selection Sort Itera Data Data Data Data Data Data Data Data Data si [1] [2] [3] [4] [5] [6] [7] [8] [9] Awal
65
2
44
26
19
22
5
3
12
i=1
65
2
44
26
19
22
5
3
12
i=2
2
65
44
26
19
22
5
3
12
i=3
2
3
44
26
19
22
5
65
12
i=4
2
3
5
26
19
22
44
65
12
i=5
2
3
5
12
19
22
44
65
26
i=6
2
3
5
12
19
22
44
65
26
i=7
2
3
5
12
19
22
44
65
26
i=8
2
3
5
12
19
22
26
65
44
Akhir
2
3
5
12
19
22
26
44
65
SELECTION SORT • Dapat dilihat dari penggalan program berikut ini : void selectionsort(int Array[ ], const int size) { int i, j, smallest, temp; for(i=0; i<size; i++) { smallest = i; for(j=i; j<size; j++) { if(Array[smallest] > Array[j]) { smallest =j; } } temp = Array[i]; Array[i] = Array[smallest]; numlist[smallest] = temp; } }
Selection Sort - Ascending
Program contoh 01
Algoritma.........????? Pseudocode.......??????
Selection Sort - Descending
Program contoh 02
Algoritma.........????? Pseudocode.......??????
INSERTION SORT Pertemuan 13
3 SKS
INSERTION SORT • Metode ini biasa juga disebut metode penyisipan langsung. • Metode ini sering digunakan dalam kehidupan nyata, misalnya saat anda mengurutkan kartu
Insertion Sort (Metode penyisipan langsung)
• Dimulai dari data ke-2 kemudian disisipkan pada tempat yang sesuai. • Data pada posisi pertama diandaikan memang sudah pada tempatnya ATAU • Suatu metode pengurutan yang dimulai dari data ke-2 nilainya dibandingkan dengan datadata sebelumnya kemudian mencari posisi yang tepat untuk menyisipkan
Insertion Sort (Metode penyisipan langsung)
• Proses pengurutan dengan metode penyisipan langsung adalah 1. Data di cek satu persatu mulai dari yang kedua sampai dengan yang terakhir 2. Apabila ditemukan data yang lebih kecil daripada data yang sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai
Insertion Sort (Metode penyisipan langsung)
•
Algoritmanya sebagai berikut : 1. i 2 2. Selama (i <= N) kerjakan baris 3 s.d. 10 3. x data[i] 4. Data[0] x 5. j i -1 6. Selama (x < data[j]) kerjakan baris 7 s.d. 8 7. data[j+1] > data[j] 8. j j - 1 9. data [j+1] x 10.i i + 1
Pengurutan Straight Insertion Sort Itera Data Data Data Data Data Data Data Data Data si [1] [2] [3] [4] [5] [6] [7] [8] [9] Awal
65
2
70
26
19
22
5
3
12
i=2
65
2
70
26
19
22
5
3
12
i=3
2
65
70
26
19
22
5
3
12
i=4
2
65
70
26
19
22
5
3
12
i=5
2
26
65
70
19
22
5
3
12
i=6
2
19
26
65
70
22
5
3
12
i=7
2
19
22
26
65
70
5
3
12
i=8
2
5
19
22
26
65
70
3
12
i=9
2
3
5
19
22
26
65
70
12
Akhir
2
3
5
12
19
22
26
65
70
INSERTION SORT • Dapat dilihat dari penggalan program berikut ini: for(k=1; k<=n-1; k++) { i=k; x=A[i]; while(i>=0 && A[i-1]>x) { A[i] = A[i-1]; i--; } A[i]=x; }
Program contoh 03
Insertion Sort Ascending
Algoritma.........????? Pseudocode.......??????
Insertion Sort Descending
Program contoh 04
Algoritma.........????? Pseudocode.......??????
Tugas : • Contoh 1,2,3 dan 4, buat program dengan menggunakan class dan konstruktor • Algoritma dan pseudocode contoh nomor 2,3 dan 4 • Kumpulkan tanggal 8
Juni 2015