Algoritma dan Pemrograman
4/27/2008
PENGURUTAN (SORTING) 1 Algoritma dan Pemrograman Tahar Agastani Teknik Informatika UIN - 2008
Overview • • • • •
Kuliah Minggu ke 13
Definisi dan Tujuan Jenis Pengurutan Teknik Pengurutan Selection Sort Bubble Sort
1
Algoritma dan Pemrograman
4/27/2008
Definisi dan Tujuan • Definisi umum: proses pengaturan kembali serangkaian objek dalam urutan tertentu • Tujuan: untuk mempercepat pencarian suatu target dalam suatu daftar (list) Membaca data dari keyboard:
Jenis Pengurutan • Berdasar bentuk pengurutan: – Ascending : Pengurutan dilakukan mulai dari nilai terkecil menuju nilai terbesar – Descending: Pengurutan dilakukan mulai dari nilai terbesar menuju nilai terkecil
• Berdasar data yang akan diurutkan: – Internal sorting: Pengurutan dilakukan terhadap array – External sorting: Pengurutan dilakukan terhadap file sekuensial
Kuliah Minggu ke 13
2
Algoritma dan Pemrograman
4/27/2008
Teknik Pengurutan • Sederhana: – Selection Sort – Bubble Sort – Insertion Sort • Lanjut: – Quick Sort – Merge Sort
SELECTION SORT Ide dasar: Mencari nilai ekstrim (terbesar atau terkecil) dalam array dan menukarkannya dengan elemen terujung.
Kuliah Minggu ke 13
3
Algoritma dan Pemrograman
4/27/2008
Algoritma: for(i=0; i<=N/* N=Banyak data dlm daftar */ i<=N-2;i++){ for(j=i;j<=Nfor(j=i;j<=N-1;j++){ /* Tentukan index dari data terkecil antara A[j] s/d A[NA[N-1], dan simpan di variabel k. Kemudian tukar A[i] dengan A[k]. */ } }
Baca Data
519
Data Pertama
419 Tukarkan
127 69
Data Terkecil
381
Algoritma: for(i=0; i<=N/* N=Banyak data dlm daftar */ i<=N-2;i++){ for(j=i;j<=Nfor(j=i;j<=N-1;j++){ /* Tentukan index dari data terkecil antara A[j] s/d A[NA[N-1], dan simpan di variabel k. Kemudian tukar A[i] dengan A[k]. */ } }
519
69
419
419
Kuliah Minggu ke 13
Data Pertama Tukarkan
Baca Data
127
127
69
519
381
381
Data Terkecil
4
Algoritma dan Pemrograman
4/27/2008
Algoritma: for(i=0; i<=N/* N=Banyak data dlm daftar */ i<=N-2;i++){ for(j=i;j<=Nfor(j=i;j<=N-1;j++){ /* Tentukan index dari data terkecil antara A[j] s/d A[NA[N-1], dan simpan di variabel k. Kemudian tukar A[i] dengan A[k]. */ } }
519
69
69
419
419
127
127
127
419
Data Pertama
69
519
519
Tukarkan
381
381
381
Baca Data
Data Terkecil
Algoritma: for(i=0; i<=N/* N=Banyak data dlm daftar */ i<=N-2;i++){ for(j=i;j<=Nfor(j=i;j<=N-1;j++){ /* Tentukan index dari data terkecil antara A[j] s/d A[NA[N-1], dan simpan di variabel k. Kemudian tukar A[i] dengan A[k]. */ } }
Baca Data
Kuliah Minggu ke 13
519
69
69
69
419
419
127
127
127
127
419
381
69
519
519
519
381
381
381
419
Data Pertama Tukarkan Data Terkecil
5
Algoritma dan Pemrograman
4/27/2008
Algoritma: for(i=0; i<=N/* N=Banyak data dlm daftar */ i<=N-2;i++){ for(j=i;j<=Nfor(j=i;j<=N-1;j++){ /* Tentukan index dari data terkecil antara A[j] s/d A[NA[N-1], dan simpan di variabel k. Kemudian tukar A[i] dengan A[k]. */ } }
519
69
69
69
69
419
419
127
127
127
127
127
419
381
381
69
519
519
519
419
381
381
381
419
519
Data Terakhir Berhenti
/* Fungsi-fungsi pada Selection Sort */ #include <stdio.h> void Cari_Min(int *Arr, int mulai, int akhir,int *k) { unsigned int i; int min; min = Arr[mulai]; for (i=mulai; i<=akhir;i++){ if (Arr[i] < min){ min = Arr[i]; *k = i; } } } void Tukar(int *x, int *y) { int z ; z = *x; *x = *y; *y = z; }
Kuliah Minggu ke 13
6
Algoritma dan Pemrograman
4/27/2008
void Selection(int *Arr, int n) { int i,k; for(i=0;i<=n-2;i++){ Cari_Min(Arr,i,n-1,&k); Tukar(&Arr[i],&Arr[k]); } } /* Program Utama */ void main() { int DataArr[] = {519,419,127,69,381}; int i; for(i=0; i<5; i++) printf(“%d ”,DataArr[i]); printf(“\n”); Selection(DataArr,5); for(i=0; i<5; i++) printf(“%d ”,DataArr[i]); printf(“\n”); }
BUBBLE (EXCHANGE) SORT Ide dasar: ‘Mengapungkan’ elemen yang nilainya kecil dengan pertukaran, sehingga array akan terurut membesar (ascending).
Kuliah Minggu ke 13
7
Algoritma dan Pemrograman
4/27/2008
Algoritma (Dengan Ilustrasi) Ilustrasi)
Kuliah Minggu ke 13
519
519
519
519
69
419
419
419
69
519
127
127
69
419
419
69
69
127
127
127
381
381
381
381
381
69
69
69
69
519
519
519
127
419
419
127
519
127
127
419
419
381
381
381
381
69
69
69
127
127
127
519
519
381
419
381
519
381
419
419
Pola Pergerakan Elemen Pada Putaran Pertama
Pola Pergerakan Elemen Pada Putaran Kedua
Pola Pergerakan Elemen Pada Putaran Ketiga
69
69
69
127
127
381
381
381
519
419
419
419
519
519
127 Putaran Keempat
Terakhir
8
Algoritma dan Pemrograman
4/27/2008
Fungsi Bubble Sort void Bubble(int *DataArr, int n) { int i,j; for (i=1; i
=i; j--) if (DataArr[j-1] > DataArr[j]) Tukar(&DataArr[j-1],&DataArr[j]); } • Bila data telah terurut, procedure diatas berlaku ‘bodoh’, yaitu tetap melakukan pembandingan. • Perbaikan secara sederhana, yaitu menambah : ‘flag’ yang memberitahu, bila pada suatu putaran data telah terurut.
Fungsi Bubble Sort void Bubble_Flag(int *Arr, int n) { int i,j; int urut; /* Flag */ urut = 0; i = 1; while ((i < n) && (!urut)) { urut = 1; for (j=n-1; j>=i; j--) { if (Arr[j-1] > Arr[j]){ Tukar (&Arr[j-1], &Arr[j]); urut = 0; } } i = i + 1; } }
Kuliah Minggu ke 13
9
Algoritma dan Pemrograman
4/27/2008
Latihan 1. Modifikasi prosedur pengurutan dengan pemilihan (selection) untuk mengurutkan data sehingga terurut mengecil (descending). 2. Modifikasi prosedur pengurutan dengan teknik bubble untuk mengurutkan data sehingga terurut mengecil (descending). 3. Buat main program untuk memanggil fungsi Bubble_Flag diatas.
Kuliah Minggu ke 13
10
