Algoritma dan Pemrograman
2
PENGURUTAN Pengurutan : proses mengatur sekumpulan obyek meurut Keuntungan dari data yang terurut: urutan atau susunan tertentu. - mempercepat proses pencarian Urutan menaik(ascending) : L[0] L[1] L[2] …L[n] - langsung diperoleh nilai maksimum dan Urutan menurun(descending) : L[0] L[1] L[2] …L[n] minimum Contoh : a. data bertipe integer terurut naik: 23 30 40 45 60 b. data bertipe riil terurut menurun: 100,1 60,3 50,4 40,5 10,7 c. data bertipe string terurut naik: Amir Badu Cecep Dudi Rudi d. data bertpe karakter terurut naik: d e g l m e. data terstruktur terurut naik berdasarkan field NIM 135901, Eko, A 135902, Edo, A 135903, Dudi, B 135904, Amir, A Metode pengurutan diklasifikasikan menjadi dua: a. Internal : metode pengurutan untuk data yang disimpan di dalam memori komputer. Umumnya struktur internal yang dipakai untuk mengurutkan internal adalah larik, sehingga pengurutan internal disebut juga pengurutan larik. b. Eksternal : metode pengurutan untuk data yang disimpan didalam disk storage, disebut juga pengurutan arsip (file), karena struktur eksternal yang digunakan adalah arsip. T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
3
I. METODE PENGURUTAN APUNG (BUBBLE SORT) Metode ini diinspirasi oleh gelembung sabun yang berada diatas permukaan air. Gelembung sabun selalu terapung ke atas permukaan air karena berat jenisnya lebih ringan daripada berat jenis air. Jika sebuah array dengan jumlah elemen (ukuran array) sebesar N maka proses pengapungan dilakukan sebanyak N-1 langkah (satu langkah disebut satu pass). Proses pengapungan dilakukan dengan cara perbandingan. Jumlah langkah = N - 1 Jumlah perbandingan = N(N - 1)/2 Algoritma Pengurutan Apung : L = 30 60 35 70 50 25 20 40 43 k = 0 1 .. .. .. .. .. .. n Untuk mendapatkan larik yang terurut menaik, algoritma pengurutan apung secara global sbb: Untuk setiap pass i=1, 2, …, n, lakukan : Mulai dari elemen k=n, n-1,…, i 1) Bandingkan L[k] dengan L[k-1] 2) Pertukarkan L[k] dengan L[k-1] jika L[k] L[k-1] Contoh : Tinjau L dengan N = 6 buah elemen belum terurut (n = 5) : L = 25 27 10 8 76 21 k= 0 1 2 3 4 5 T-Informatika FT UNPAM
Atang Susila
Pass 1: k Elem. yg dibandingkan Pertukarkan? Hasil Sementara 5 L[5] L[4] Ya 25, 27, 10, 8, 21, 76 4 L[4] L[3] Tidak 25, 27, 10, 8, 21, 76 3 L[3] L[2] Ya 25, 27, 8, 10, 21, 76 2 L[2] L[1] Ya 25, 8, 27, 10, 21, 76 1 L[1] L[0] Ya 8, 25, 27, 10, 21, 76 Hasil akhir pass-1: 8 25 27 10 21 76 Pass 2 (berdasarkan hasil akhir pass 1) : k Elem. yg dibandingkan Pertukarkan? 5 L[5] L[4] Tidak 4 L[4] L[3] Tidak 3 L[3] L[2] Ya 2 L[2] L[1] Ya Hasil akhir pass-2: 8 10 25 27 21 76 Pass 3 (berdasarkan hasil akhir pass-2) k Elem yg dibandingkan Pertukarkan? 5 L[5] L[4] Tidak 4 L[4] L[3] Ya 3 L[3] L[2] Ya Hasil akhir pass-3: 8 10 21 25 27 76
Hasil Sementara 8, 25, 27, 10, 21, 76 8, 25, 27, 10, 21, 76 8, 25, 10, 27, 21, 76 8, 10, 25, 27, 21, 76
Hasil Sementara 8, 10, 25, 27, 21, 76 8, 10, 25, 21, 27 , 76 8, 10, 21, 25, 27, 76
Pass 4 (berdasarkan hasil akhir pass-3) k Elem. yg dibandingkan Pertukarkan? Hasil Sementara 5 L[5] L[4] Tidak 8, 10, 21, 25, 27, 76 4 L[4] L[3] Tidak 8, 10, 21, 25, 27, 76 Hasil akhir pass-4: 8 10 21 25 27 76 Pass 5 (berdasarkan hasil akhir pass-4) k Elem. yg dibandingkan Pertukarkan? Hasil Sementara 5 L[5] L[4] Tidak 8, 10, 21, 25, 27, 76 Hasil akhir pass-5: 8 10 21 25 27 76
Hasil akhir pass-5 menyisakan satu elemen (yaitu 76) yang tidak perlu diurutkan, maka pengurutan selesai.
Algoritma pengurutan apung menaik: procedure BubbleSort(input/output L : LarikInt, input n : integer) {Keadaan Awal : Elemen larik L sudah terdefinisi nilai-nilainya} {Keadaan Akhir : Elemen larik L terurut menaik} DEKLARASI i : integer {pencacah untuk jumlah langkah} k : integer {pencacah untuk pengapungan pada setiap langkah} tmp : integer {variabel bantu untuk pertukaran} DESKRIPSI for i 1 to n do for k n downto i do if L(k) < L(k –1) then tmp L[k] L[k] L[k –1] L[k – 1] tmp endif endfor endfor Metode pengurutan ini merupakan metode yang tidak efisien untuk data yang besar, disebabkan oleh banyaknya operasi pertukaran yang dilakukan pada setiap langkah pengapungan.
Algoritma dan Pemrograman
6
Translasi algoritma pengurutan dengan metode bubble sort kedalam bahasa C sbb: /*Mengurutkan data dengan metode Bubble Sort*/ void BubbleSort(int array1[],int n) #include
{ void BubbleSort(int data[],int n); //prototipe fungsi int i,k,tmp; void main(void) for(i=1;i<=n;i++) { { int i; for(k=n;k>=i;k--) int n=9;//Jml Data = 10 maka n = 9 { int data[]={20,10,32,100,60,12,70,25,45,65}; if(array1[k]<array1[k-1]) cout<<"Sebelum diurutkan :"<<endl; { for(i=0;i<=n;i++) tmp=array1[k]; cout<
II. METODE PENGURUTAN SELEKSI (SELECTION SORT) Gagasan metode ini adalah memilih elemen maksimum/minimum dari array, lalu menempatkan elemen maksimum/minimum itu pada ujung (awal atau akhir) array. Selanjutnya elemen terujung tersebut diisolasi dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa. Pemilihan nilai maksimum/ minimum dilakukan pada setiap pass. T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
7
Ditinjau dari pemilihan elemen maksimum/minimum, algoritma pengurutan seleksi dibagi menjadi dua: 1. Algoritma pengurutan seleksi-maksimum, yaitu memilih elemen maksimum sebagai basis pengurutan 2. Algoritma pengurutan seleksi-minimum, yaitu memilih elemen minimum sebagai basis pengurutan Algoritma pengurutan seleksi-maksimum Untuk memperoleh array dengan jumlah elemen N yang terurut menaik, algoritma pengurutan seleksimaksimum dapat ditulis secara garis besar sebagai berikut: Jumlah pass : n = N –1 Jumlah perbandingan : N(N + 1)/2 Untuk setiap pass i = 1, 2, …, n; lakukan: 1) Cari elemen terbesar (maks) mulai dari elemen pertama (ke-0) sampai elemen terakhir (ke-n) 2) Pertukarkan maks dengan elemen ke-n 3) Kurangi n dengan satu (karena elemen ke-n sudah terurut)
procedure SelectionMax(input/output L : LarikInt, input n : integer) DEKLARASI i : integer {pencacah pass} j : integer {pencacah untuk mencari nilai maksimum} imaks : integer {indeks yg berisi nilai maksimum sementara} tmp : integer {variabel bantu untuk pertukaran}
T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
8
DESKRIPSI: for i n downto 1 do imaks 0 for j 1 to i do if L[j] > L[imaks] then imaks j endif endfor tmp L [i] L[i] L[imaks] L[imaks] tmp endfor Contoh: Urutkan elemen larik berikut secara menaik: Elemen : 25 27 10 8 76 21 Index : 0 1 2 3 4 5 Pass 1 : Cari elemen maksimum didalam array L[0…5] hasilnya : maks = L[4] = 76. Pertukarkan maks dengan L[n], diperoleh: 25 27 10 8 21 76 T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
9
Pass 2 (berdasarkan susunan larik hasil pass 1) : Cari elemen maksimum didalam array L[0…4] hasilnya : maks = L[1] = 27. Pertukarkan maks dengan L[4], diperoleh: 25 21 10 8 27 76 Pass 3(berdasarkan susunan larik hasil pass 2) : Cari elemen maksimum didalam array L[0…3] hasilnya : maks = L[0] = 25. Pertukarkan maks dengan L[3], diperoleh: 8 21 10 25 27 76 Pass 4 (berdasarkan susunan larik hasil pass 3) : Cari elemen maksimum didalam array L[0…2] hasilnya : maks = L[1] = 21. Pertukarkan maks dengan L[2], diperoleh: 8 10 21 25 27 76 Pass 5 (berdasarkan susunan larik hasil pass 4) : Cari elemen maksimum didalam array L[0…1] hasilnya : maks = L[1] = 10. Pertukarkan maks dengan L[1], diperoleh: 8 10 21 25 27 76 Tersisa satu elemen (yaitu 8), maka pengurutan selesai. Array sudah terurut naik.
T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
10
Translasi algoritma pengurutan seleksi-maksimum kedalam bahasa C : /*Mengurutkan data dengan metode Seleksi Maksimum*/ #include void SeleksiMaksimum(int data[],int n); /*prototipe fungsi*/ void main(void) { int i; int n=9;//Index terbesar int data[]={20,10,32,100,60,12,70,25,45,65}; cout<<"Sebelum diurutkan :"<<endl; for(i=0;i<=n;i++) cout<
void SeleksiMaksimum(int array1[],int n) { int i,j,tmp,imaks; for(i=n;i>=1;i--) { imaks=0; for(j=1;j<=i;j++) { if(array1[j]>array1[imaks]) imaks=j; } tmp=array1[imaks]; array1[imaks]=array1[i]; array1[i]=tmp; } }
Algoritma pengurutan-minimum menaik : Basis pencarian adalah elemen minimum (terkecil). Elemen minimum ditempatkan di awal larik. Algoritma seleksi-minimum untuk memperoleh larik yang terurut menaik sbb : Untuk setiap pass i = 0, 1, 2, …, n-1, lakukan 1) Cari elemen terkecil (min) mulai dari elemen ke i sampai elemen ke n. 2) Pertukarkan min dengan elemen ke i. T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
11
procedure SelectionMin(input/output L : LarikInt, input n : integer) DEKLARASI i : integer {pencacah pass} j : integer {pencacah untuk mencari nilai minimum} imin : integer {indeks yg berisi nilai minimum sementara} tmp : integer {variabel bantu untuk pertukaran} DESKRIPSI: for i 0 to n-1 do imin 0 for j i+1 to n do if L[j] < L[imin] then imin j endif endfor tmp L [i] L[i] L[imin] L[imin] tmp endfor Contoh: Urutkan elemen larik berikut secara menaik: Elemen : 29 27 10 8 76 21 Index : 0 1 2 3 4 5 T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
12
Pass 0 : Cari elemen terkecil didalam array L[0…5] hasilnya : min = L[3] = 8. Pertukarkan min dengan L[0], diperoleh: 8 27 10 29 76 21 Pass 1 (berdasarkan susunan larik hasil pass 0) : Cari elemen terkecil didalam array L[1…5] hasilnya : min = L[2] = 10. Pertukarkan min dengan L[1], diperoleh: 8 10 27 29 76 21 Pass 2 (berdasarkan susunan larik hasil pass 1) : Cari elemen terkecil didalam array L[2…5] hasilnya : min = L[5] = 21. Pertukarkan min dengan L[2], diperoleh: 8 10 21 29 76 27 Pass 3 (berdasarkan susunan larik hasil pass 2) : Cari elemen terkecil didalam array L[3…5] hasilnya : min = L[5] = 27. Pertukarkan min dengan L[3], diperoleh: 8 10 21 27 76 29 Pass 4 (berdasarkan susunan larik hasil pass 3) : Cari elemen terkecil didalam array L[4…5] hasilnya : min = L[5] = 29. Pertukarkan min dengan L[4], diperoleh: 8 10 21 27 29 76 Tersisa satu elemen (yaitu 76), maka pengurutan selesai. Array sudah terurut naik.
T-Informatika FT UNPAM
Atang Susila
Algoritma dan Pemrograman
Translasi algoritma pengurutan seleksi-minimum kedalam bahasa C : /*Mengurutkan data dengan metode Seleksi Minimum*/ void #include { void SeleksiMinimum(int data[],int n); /*prototipe fungsi*/ void main(void) { int i; int n=9;//Index terbesar int data[]={20,10,32,100,60,12,70,25,45,65}; cout<<"Sebelum diurutkan :"<<endl; for(i=0;i<=n;i++) cout<
T-Informatika FT UNPAM
13
SeleksiMinimum(int array1[],int n) int i,j,tmp,imin; for(i=0;i<=n-1;i++) { imin=i; for(j=i+1;j<=n;j++) { if(array1[j]<array1[imin]) imin=j; } tmp=array1[imin]; array1[imin]=array1[i]; array1[i]=tmp; }
Atang Susila
Algoritma dan Pemrograman
14
TUGAS 1. Tulislah algoritma untuk pengurutan secara menurun menggunakan metode bubble sort dan selection sort(min dan max). 2. Buatlah programnya menggunakan C++ untuk array sbb:
metode
10 40 20 60 15 4 8 100 200 25
T-Informatika FT UNPAM
Atang Susila
