dosen: condro kartiko & yudha...

S1 InformatikaIT Telkom Purwokerto

Pertemuan XI – ALGORITMA PENGURUTAN

Dosen: Condro Kartiko &

ALGORITMA PEMROGRAMAN (Semester 1 - IF6110202)

Yudha Saintika

“Mahasiswa mampu menerapkan algoritma pengurutan kedalam program.”


Sub-Capaian Pembelajaran MK

We Are Here !!!

Mid Test

Peta Capaian Pembelajaran MK

PUSTAKA WAJIB

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

• BAB 16 – ALGORITMAPENGURUTAN



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


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


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


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


Algoritma Pengurutan (1)

insertion sort


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.


Insertion Sort (2)

Metode ini sebenarnya juga

digunakan dalam kehidupan nyata,

misalnya saat anda mengurutkan

kartu.


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


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


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


Algoritma Insertion Sort


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]


Contoh Persoalan


Potongan Prosedur


Algoritma Pengurutan Seleksi

AlgoritmaPengurutan

Seleksi

Minimum

Maksimum


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


Algoritma Seleksi Maksimum


Petikan Algoritma


Performa Masing-Masing Algoritma


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?

Selanjutnya Baca…

• Munir, Rinaldi., Leony Lidya. 2016.Algoritma dan PemrogramanDalam Bahasa Pascal, C, dan C++Edisi Keenam. Bandung: PenerbitInformatika.

BAB 17 – Pemrosesan Arsip

Selasa, 2 Januari 2018 jam 08.40


dosen: condro kartiko & yudha...

Documents