pertemuan xi algoritma pengurutan...

33
S1 Sistem Informasi IT Telkom Purwokerto Pertemuan XI – ALGORITMA PENGURUTAN (Sorting) Koordinator Mata Kuliah : Fathushahib, S.Kom., M.Kom Tim Dosen: Yudha Saintika, S.T., M.T.I ALGORITMA PEMROGRAMAN (Semester 1)

Upload: hoangdat

Post on 30-Mar-2019

237 views

Category:

Documents


1 download

TRANSCRIPT

Page 1: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Pertemuan XI – ALGORITMA PENGURUTAN(Sorting)

• Koordinator Mata Kuliah :

• Fathushahib, S.Kom., M.Kom

• Tim Dosen:

• Yudha Saintika, S.T., M.T.I

ALGORITMA PEMROGRAMAN (Semester 1)

Page 2: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

“Mahasiswa mampu menerapkan algoritma pengurutan kedalam program.”

S1 Sistem InformasiIT Telkom Purwokerto

Sub-Capaian Pembelajaran MK

Page 3: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

We Are Here !!!

Mid Test

Peta Capaian Pembelajaran MK

Page 4: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

PUSTAKA WAJIB

• Munir, Rinaldi., Leony Lidya.2016. Algoritma danPemrograman Dalam BahasaPascal, C, dan C++ EdisiKeenam. Bandung: PenerbitInformatika.

• BAB 16 – ALGORITMAPENGURUTAN

S1 Sistem InformasiIT Telkom Purwokerto

Page 5: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Definisi

“algoritma untuk meletakkan kumpulan elemen data ke dlm urutan tertentu, berdasarkan satu atau beberapa kunci ke dalam tiap-tiap elemen”

Ada 2 macam urutan dalam proses pengurutan:1. Ascending2. Descending

Page 6: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Mengapa Data Harus Diurutkan ?

• Agar data dapat dilihat dengan mudah. Untuksemua algoritma pengurutan yang akandipelajari, kita menggunakan tipe data larik.

DEKLARASI

const max = 1000

type LarikInt : array [1 .. N] of integer

Page 7: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Metode Pengurutan

Beberapa metode pengurutan akan menemukan pemanggilanTUKAR. Kegunaan prosedur ini adalah menukar isi dua variabel.Berikut definisi Tukar :

procedure Tukar (input/output a,b: integer)

{mempertukarkan nilai a dan b}

DEKLARASI

temp : integer

ALGORITMA

temp a

a b

b temp

Page 8: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Menentukan Pengurutan yang Baik

Ada 2 hal yang harus diperhatikan untukmenentukan pengurutan yang baik:

1. Jumlah pembandingan yang dilakukan

2. Jumlah penukaran atau penggeseran data yangdilakukan

Page 9: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Pengurutan (1)

insertion sort

Page 10: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Insertion Sort (1)

Cara mengurutkannya adalah dicek satu persatu mulai dari yang kedua sampai dengan yang terakhir.

Apabila ditemukan data yang lebih

kecil dari data sebelumnya, maka

data tersebut disisipkan pada posisi

yang sesuai.

Page 11: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Insertion Sort (2)

Metode ini sebenarnya juga

digunakan dalam kehidupan nyata,

misalnya saat anda mengurutkan

kartu.

Page 12: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Insertion Sort

1. i 22. Asumsikan L[1] dianggap sudah pada tempatnya3. Selama (i<=N) kerjakan baris 4 sampai dengan 104. x Data[i]5. j i – 16. Selama (x < Data[j] ) kerjakan baris 7 dan 87. Data [j+i] Data [j]8. j j – 19. Data[j+1] x10. i i + 1

Page 13: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Contoh Persoalan (1)

Iterasi Data [1]

Data [2]

Data [3]

Data [4]

Data [5]

Data [6]

Data [7]

Data [8]

Data [9]

Awal 12 35 9 11 3 17 23 15 31

i=2 12 35 9 11 3 17 23 15 31

i=3 12 35 9 11 3 17 23 15 31

i=4 9 12 35 11 3 17 23 15 31

i=5 9 11 12 35 3 17 23 15 31

i=6 3 9 11 12 35 17 23 15 31

i=7 3 9 11 12 17 35 23 15 31

i=8 3 9 11 12 17 23 35 15 31

i=9 3 9 11 12 15 17 23 35 31

Akhir 3 9 11 12 15 17 23 31 35

Page 14: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Penjelasan

• i = 2, x samadengan Data[2], yaitu 35 dan j=1. karenaData[1]=12 dan 35>12 maka proses dilanjutkan

• i=3, x samadengan Data[3], yaitu 9 dan j=2. karenaData[2]=35 dan 9<35 maka dilakukan penggeseransampai menemukan yang lebih kecil dari 9. Hasilnya,Data[2]=12 dan Data[3]=35. Bagaimana dengan Data[1]?Data[1] = x yaitu 9.

• i=4, x samadengan Data[4], yaitu 11 dan j=3. karenaData[3]=35 dan 11<35, maka dilakukan penggeseransampai ditemukan data yang lebih kecil dari 11. Hasilpenggeseran Data[3]=12 dan Data[4]=45, Data[2] diisi 11

• dst

Page 15: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Insertion Sort

Page 16: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Pengurutan (2)

Bubble sort

Page 17: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma

Algoritma pengurutan Buble (Apung) membandingkanelemen-elemen larik dari kanan ke kiri

1. Untuk setiap pass i = 1,2,…,n-1, kerjakan:2. Untuk setiap k=n, n-1, …, i+1, kerjakan:3. Bandingkan L[k] dengan L[k-1]. Jika L[k] < L[k-1] kerjakan:4. Pertukarkan L[k] dengan L[k-1]

Page 18: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Contoh Persoalan

Page 19: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

Contoh Persoalan

Page 20: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

Contoh Persoalan

Page 21: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Potongan Prosedur

Page 22: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Pengurutan (3)

Selection sort

Page 23: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Pengurutan Seleksi

AlgoritmaPengurutan

Seleksi

Minimum

Maksimum

Page 24: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Seleksi Maksimum

Untuk setiap pass ke-i= n,n-1, …, 2, lakukan:

1. Cari elemen terbesar (maks) mulai dari elemenke-1 sampai dengan elemen ke-i

2. Pertukarkan maks dengan elemen ke-i

Page 25: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Seleksi Maksimum

Page 26: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Seleksi Maksimum

Page 27: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Algoritma Seleksi Maksimum

Page 28: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Petikan Algoritma

Page 29: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Performa Masing-Masing Algoritma

Page 30: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto

Latihan

int arr[6]

id 1 2 3 4 5 6

arr[id] 22 10 15 3 8 2

Jelaskan langkah-langkah pengurutan data secara ascendingmenggunakan Buble Sort, Selection Sort, dan Insertion sort

Page 31: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

PREPARE FOR QUIZ NEXT WEEK ,

KEEP SPIRIT GUYSSS!!!

Page 32: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

Tugas Besar (25%)

• Buatlah suatu program beserta laporannya dengan topik bebas dimana didalam program tersebut memuat komponen larik, prosedur atau fungsi,dan sorting atau searching.

• Gunakan Kelompok sebelumnya (3 atau maksimal 4 orang)

• Minimal terdiri dari 50 baris (line of code)

• Topik antar kelompok harus berbeda.

• Jadwal Presentasi setelah pertemuan terakhir (Quiz) atau sebelumpelaksanaan UAS.

• Format laporan terdiri dari cover, source code, dan penjelasan singkattentang program dan masing-masing prosedur/fungsi yang digunakan.

Page 33: Pertemuan XI ALGORITMA PENGURUTAN (Sorting)yudha.dosen.ittelkom-pwt.ac.id/wp-content/uploads/sites/73/2018/10/... · Pascal, C, dan C++ Edisi Keenam. Bandung: ... dalam program tersebut

S1 Sistem InformasiIT Telkom Purwokerto