Praktikum Algoritma dan Pemrograman II
MODUL III
SORTING
Pertemuan :5
Waktu : 2 x 60 menit (di Laboratorium)
3.1 Tujuan Modul III
Setelah mahasiswa mempelajari materi ini, diharapkan dapat :
1. menggunakan algoritma selection sort dalam menyelesaikan masalah
pengurutan menggunakan Bahasa C
2. menggunakan algoritma bubble sort dalam menyelesaikan masalah pengurutan
menggunakan Bahasa C
3. menggunakan algoritma insertion sort dalam menyelesaikan masalah
pengurutan menggunakan Bahasa C
3.2 Landasan Teori
3.2.1 Bubble Sort
Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara
berulang kali membandingkan dua elemen data pada suatu saat dan
menukar elemen data yang urutannya salah. Proses tersebut dilakukan
berulang kali hingga tidak ada pertukaran elemen data lagi, yang berarti
bahwa data telah terurut. Karena algoritma ini melakukan pengurutan
dengan cara membandingkan elemen-elemen data satu sama lain, maka
bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.
Berikut ini adalah algoritma dan bahasa C untuk bubble sort :
Notasi Algoritmik C
Program Bubble Sort #include<stdio.h>
Kamus data : int A[10]={ 5,10,11,2,8,13,7,20,35,18};
A[1..10] : array of integer int i;
=(5,10,11,2,8,13,7,20,35,18) int swap;
i : integer
swap : boolean void tukar(int *a, int *b);
procedure tukar(in/out a,b :
integer) main(){
do{
Algoritma : swap=0;
Repeat for(i=0;i<10;i++){
swap ← false if(A[i] > A[i+1]){
for i←1 to 10 do tukar(&A[i],&A[i+1]);
if (A[i] > A[i+1]) then swap=1;
tukar(A[i], A[i+1]) }
swap ← true }
endif }while(swap==1);
endfor }
until not swap
Laboratorium Software Engineering Versi/Revisi : 2/1 Halaman : 3-1
Praktikum Algoritma dan Pemrograman II
void tukar(int *a, int *b){
int c;
c=*a;
*a=*b;
*b=c;
}
3.2.2 Selection sort
Selection sort adalah proses pengurutan sekelompok data yang dilakukan
dengan cara berulang kali mencari nilai terendah (pengurutan ascending) /
tertinggi (pengurutan descending) dan meletakkan hasilnya di posisi
pertama. Karena setiap kali selection sort harus membandingkan
elemenelemen data, algoritma ini termasuk dalam comparison-based
sorting.
Berikut ini adalah algoritma dan bahasa C untuk selection sort :
Notasi Algoritmik C
Program Selection Sort #include<stdio.h>
Kamus data : int A[10]={ 5,10,11,2,8,13,7,20,35,18};
A[1..10] : array of integer int i,j;
=(5,10,11,2,8,13,7,20,35,18) int min;
i,j : integer
min : integer void tukar(int *a, int *b);
procedure tukar(in/out a,b :
integer) main(){
for(i=0;i<=8;i++){
Algoritma : min=i;
For i←1 to 10-2 do for(j=i+1;j<=9;j++){
min ← i if(A[j]<A[min]{
for j←(i+1) to 10-1 do min=j;
if (A[j] < A[min] }
min ← j }
endif tukar(A[i],A[min]);
endfor }
tukar(A[i], A[min]) }
endfor
void tukar(int *a, int *b){
int c;
c=*a;
*a=*b;
*b=c;
}
3.2.3 Insertion Sort
Insertion sort adalah sebuah algoritma pengurutan yang membandingkan
dua elemen data pertama, mengurutkannya, kemudian mengecek elemen
data berikutnya satu persatu dan membandingkannya dengan elemen data
yang telah diurutkan. Karena algoritma ini bekerja dengan
membandingkan elemenelemen data yang akan diurutkan, algoritma ini
termasuk pula dalam comparison-based sort.
Berikut adalah algoritma dan bahasa C untuk insertion sort :
Laboratorium Software Engineering Versi/Revisi : 2/1 Halaman : 3-2
Praktikum Algoritma dan Pemrograman II
Notasi Algoritmik C
Program Insertion Sort #include<stdio.h>
Kamus data : int A[10]={ 5,10,11,2,8,13,7,20,35,18};
A[1..10] : array of integer int i,j;
=(5,10,11,2,8,13,7,20,35,18) int nilai;
i,j : integer
nilai : integer main(){
for(i=0;i<=8;i++){
Algoritma : nilai=A[i];
For i←1 to 10-1 do j=i-1;
nilai ← A[i] while((j>=0)&&(A[j]>nilai)){
j ← I – 1 A[j+1]=A[j];
while (j >=0) and (A[j] > nilai j=j-1;
do }
A[j+1] ← A[j] A[j+1]=nilai;
j ← j – 1 }
endwhile }
A[j+1] ← nilai
endfor
3.2.4 Contoh Penyelesaian Kasus
Berikut ini adalah program input dan sort data pasien disertai menu. Pelajari
dan perbaiki program di bawah ini ! Jenis sorting apa yang dilakukan ?
#include <stdio.h>
#include <string.h>
main(){
typedef struct{
int kd_pasien;
char nama_pasien[20];
int usia;
} pasien;
int menu=1;
pasien p[10];
int i,j,n;
pasien temp;
while ((menu < 4) && (menu >= 1))
{
printf("Menu Pasien :");
printf("1. Input data pasien");
printf("2. Urutkan data pasien");
printf("3. Tampilkan data semua pasien");
printf("4. Keluar");
printf("Masukkan nomor menu program :");
scanf("%d",&menu);
switch (menu){
case 1 :
{
printf("Masukkan jumlah data pasien (max 10) :");
scanf("%d",&n);
Laboratorium Software Engineering Versi/Revisi : 2/1 Halaman : 3-3
Praktikum Algoritma dan Pemrograman II
for(i=0;i<n;i++){
printf("Masukkan data pasien ke-%d\n",i+1);
printf("Masukkan kode
pasien :");scanf("%d",&p[i].kd_pasien);
printf("Masukkan nama
pasien :");scanf("%s",&p[i].nama_pasien);
printf("Masukkan usia
pasien :");scanf("%d",&p[i].usia);
}
}
case 2 :
{
for(i=0;i<n-1;i++){
for(j=n-1;j>=i;j--){
if(p[j].usia < p[j-1].usia){
temp.kd_pasien=p[j].kd_pasien;
strcpy(temp.nama_pasien,p[j].nama_pasien);
[Link]=p[j].usia;
p[j].kd_pasien=p[j-1].kd_pasien;
strcpy(p[j].nama_pasien,p[j-
1].nama_pasien);
p[j].usia=p[j-1].usia;
p[j-1].kd_pasien=temp.kd_pasien;
strcpy(p[j-
1].nama_pasien,temp.nama_pasien);
p[j-1].usia=[Link];
}
}
}
printf("data berhasil diurut");
}
case 3 :
{
printf("data diurut berdasarkan usia :\n");
for(i=0;i<n;i++){
printf("data pasien ke-%d\n",i+1);
printf("kd_pasien : %d\n",p[i].kd_pasien);
printf("nama pasien : %s\n",p[i].nama_pasien);
printf("usia : %d\n",p[i].usia);
}
}
case 4 :
{
printf("Keluar program");
}
}
}
}
3.3 Praktikum III
3.3.1 Tugas Pendahuluan III
1. Diketahui suatu data tiket sbb.
Laboratorium Software Engineering Versi/Revisi : 2/1 Halaman : 3-4
Praktikum Algoritma dan Pemrograman II
Id_tiket Jurusan harga
T001 Bandung-Jakarta 85000
T002 Bandung-Bekasi 50000
T003 Jakarta-Surabaya 150000
Buatlah program bahasa C menggunakan 3 pilihan menu
1. Isi Data, menu untuk memasukkan data di atas ke dalam struktur tiket
2. Menampilkan data tiket terurut menaik berdasar harga (Gunakan bubble
sort)
3. Keluar Program
2. Buatlah program pengurutan elemen array yang diinput oleh user
sebanyak n buah menggunakan :
a. Selection sort ( pilih : minimum atau maksimum sort)
b. Insertion sort
Gunakan prosedur sorting dengan parameter input/output berupa array!
3.3.2 Latihan-latihan Praktikum III
Kerjakan 2 soal per individu sesuai tempat duduk (1 soal tipe A dan 1 soal
tipe B)
1. [TIPE A]
Diketahui sebuah tiket untuk alat transportasi yang dipakai untuk mudik
dengan harga tetap kemanapun sebagai berikut :
Kode Jenis_transportasi Harga
1 Bus 50.000
2 Kereta Api 100.000
3 Ferry 75.000
4 Pesawat 200.000
Jika calon penumpang membeli tiket lebih dari 3, maka berhak mendapat
diskon sebesar 10% dari total pembelian. Buatlah program dengan
bahasa C untuk memasukkan data rekap penjualan tiket dengan
struktur : nama_pemesan, jenis_transportasi, total penjualan
menggunakan array berdasarkan inputan : nama_pemesan,
kode_transportasi, dan jumlah_tiket. Kemudian tampilkan seluruh data
struktur rekap penjualan secara terurut dari total penjualan yang
terbesar sampai terkecil! (gunakan selection sort maksimum)
2. [TIPE A]
Diketahui sebuah tiket kereta api sebagai berikut :
Kode Asal Tujuan Harga
1 Bandung Jakarta 100.000
Laboratorium Software Engineering Versi/Revisi : 2/1 Halaman : 3-5
Praktikum Algoritma dan Pemrograman II
2 Jakarta Bandung 100.000
3 Bandung Surabaya 300.000
4 Surabaya Bandung 300.000
Jika calon penumpang membeli tiket lebih dari 2, maka berhak mendapat
diskon sebesar 5% dari total pembelian. Buatlah program dengan
bahasa C untuk memasukkan data rekap penjualan tiket dengan
struktur : nama_pemesan, Jurusan, dan total penjualan menggunakan
array berdasarkan inputan : nama_pemesan, kode_jurusan, dan
jumlah_tiket. Kemudian tampilkan seluruh data struktur rekap
penjualan tiket secara terurut dari total penjualan terkecil sampai total
penjualan terbesar ! (gunakan selection sort minimum)
3. [TIPE B]
Buatlah program pengurutan ascending terhadap elemen array A bertipe
integer menggunakan insertion sort. Nilai elemen array A diinput oleh
user. Gunakan prosedur dengan parameter input/output berupa array.
4. [TIPE B]
Buatlah program pengurutan descending terhadap elemen array A bertipe
integer menggunakan bubble sort. Nilai elemen array A diinput oleh user.
Gunakan prosedur dengan parameter input/output berupa array.
3.3.3 Tugas Rumah III
Tugas Rumah III ini hanya untuk praktikan yang belum menyelesaikan seluruh
soal Latihan Praktikum III.
1. Kerjakan sisa soal Latihan Praktikum yang belum selesai di luar jam
praktikum.
2. Buat laporan praktikum berdasarkan hasil pada praktikum pertemuan pertama
ini. Laporan tersebut berisi:
a. Soal latihan praktikum
b. Solusi dengan menggunakan algoritma
c. Solusi program dengan menggunakan bahasa C
d. Screenshot hasil eksekusi program
Keempat poin tersebut disusun per nomor soal latihan.
Jangan lupa mengumpulkannya ke asisten/instruktur maksimal 1x24 jam
setelah praktikum III berakhir.
Perhatikan bahwa laporan ini harus merupakan hasil karya sendiri. Kesamaan
seluruh/sebagian isi laporan dengan mahasiswa lain akan mengakibatkan nilai
laporan menjadi Nol.
Laboratorium Software Engineering Versi/Revisi : 2/1 Halaman : 3-6