Sistem Informasi – Fakultas Teknik
Universitas Nusantara PGRI Kediri
Praktikum
4 Sorting
A TUJUAN
1. Mahasiswa dapat mengurutkan data menggunakan beberapa metode pengurutan.
2. Mahasiswa dapat menggunakan bahasa C++ untuk mengurutkan data
B PRETEST
1. Sebutkan jenis-jenis algoritma sorting
2. Jelaskan perbedaan antara algoritma selection sort, bubble sort dan insertion sort
3. Dari ketiga algorit diatas manakah yang paling cepat?
C DASAR TEORI
Proses pengurutan data banyak ditemukan dalam proses komputer. Data yang sudah terurut memiliki
beberapa keuntungan seperti memudahkan pencarian, menentukan nilai terbesar dan terkecil. Adanya
kebutuhan pengurutan data memunculkan bermacam-macam metode pengurutan dengan tujuan untuk
memperoleh metode pengurutan yang optimal.
Pengurutan (sorting) merupakan proses mengatur sekumpulan obyek menurut urutan atau susunan
tertentu. Urutan obyek dapat menaik (ascending) maupun menurun (descending). Data yang diurutkan
dapat berupa data bertipe data dasar atau tipe data bentukan (structure). Jika data bertipe structure ,
maka harus disebutkan berdasarkan field data tertentu.
Beberapa metode yang dapat digunakan dalam pengurutan antara lain Bubble Sort, Selection Sort,
Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Shell Sort, Radix Sort, Tree Sort dan Maximum Sort.
Pemilihan metode pengurutan yang cocok akan berperan dalam suatu aplikasi.
Dalam praktikum akan digunakan metode Selection Sort, Bubble Sort dan Insertion Sort.
Selection Sort
Selection Sort membandingkan suatu elemen dengan eleman lain secara urut.
Contoh: data 6,3,5,2,4 dilakukan pengrurutan menaik dari depan
Langkah 1 Langkah 2 Langkah 3
3 6 5 2 4 2 5 6 3 4 2 3 5 6 4
3 6 5 2 4 2 3 6 5 4 2 3 4 6 5
2 5 6 3 4 2 3 6 5 4
2 5 6 3 4
Langkah 4
2 3 4 5 6
Bubble Sort
Bubble Sort merupakan metode pengurutan yang membandingkan suatu elemen dengan elemen
berikutnya. Pembandingan elemen dapat dimulai dari awal atau dari akhir. Apabila elemen tersebut lebih
besar dari elemen selanjutnya (untuk pengurutan menaik) maka posisinya ditukar.
Modul Praktikum Struktur Data 1
Sistem Informasi – Fakultas Teknik
Universitas Nusantara PGRI Kediri
Misal banyaknya data: n , data diurutkan/disorting menaik
Proses
step 1 :
Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-1. Jika nilai kiri>kanan, tukarkan
kedua data itu.
step 2 :
Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-2. Jika nilai kiri>kanan,
tukarkan kedua data itu.
step n-1 :
Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-n-1. Jika nilai kiri>kanan,
tukarkan kedua data itu
Contoh: data 6,3,5,2,4 dilakukan pengrurutan menaik dari belakang
Langkah 1 Langkah 2 Langkah 3
6 3 5 2 4 2 6 3 4 5 2 3 6 4 5
6 3 2 5 4 2 6 3 4 5 2 3 4 6 5
6 2 3 5 4 2 3 6 4 5
2 6 3 5 4
Langkah 4
2 3 4 5 6
Insertion Sort
Insertion Sort merupakan metode pengurutan dengan cara menyisipkan elemen pada posisi yang tepat.
Pencarian elemen yang tepat dilakukan dengan cara melakukan pencarian secara beruntun. Selama
pencarian tersebut, dilakukan pergeseran elemen array.
Contoh: data 6,3,5,2,4 dilakukan pengrurutan menaik dari belakang
Langkah 1 Langkah 2 Langkah 3
6 3 5 2 4 3 6 5 2 4 3 5 6 2 4
Langkah 4 Langkah 5
2 3 5 6 4 2 3 4 5 6
D PERCOBAAN
Percobaan 1
Buatlah Program untuk menukar nilai 2 buah variabel
#include <iostream>
#include <conio.h>
using namespace std;
int main(){
int a,b,c;
a = 10;
b = 20;
cout << 'a=' << a << ' b='<< b <<endl;
cout << 'setelah ditukar ' << endl;
c = a;
a = b;
b = c;
cout << 'a=' << a << ' b='<< b <<endl;
getch();
return 0;
}
Modul Praktikum Struktur Data 2
Sistem Informasi – Fakultas Teknik
Universitas Nusantara PGRI Kediri
Percobaan 2
Buatlah Program untuk menukar nilai 2 buah variabel dengan menggunakan fungsi dengan cara pass by
reference
#include <iostream>
#include <conio.h>
using namespace std;
void swap(int &a, int &b);
int main(){
int x,y;
x = 10;
y = 20;
cout << 'x=' << x << ' y=' << y <<endl;
cout << 'setelah ditukar ' <<endl;
swap(x,y);
cout << 'x=' << x << ' y=' << y <<endl;
getch();
return 0;
}
void swap(int &a, int &b){
int tmp;
tmp = a;
a = b;
b = tmp;
}
Modul Praktikum Struktur Data 3
Sistem Informasi – Fakultas Teknik
Universitas Nusantara PGRI Kediri
Percobaan 3
Buatlah program untuk mengurutkan data array dengan menggunakan selection sort, bubble sort dan
insertion sort dengan menggunakan fungsi
#include <iostream>
#include <conio.h>
using namespace std;
void swap(int &a, int &b);
int data[5] = {4,2,3,5,1};
int jml = 5;
void sorting_selection();
void sorting_bubble();
void sorting_insertion();
void swap(int &a, int &b);
int main(){
int i;
cout << 'Data awal: '
for(i=0;i<jml;i++)
cout<<data[i]<<" ";
cout<<endl;
cout << 'Data urut dengan menggunakan Selection Sort: '
sorting_selection();
…......................................
cout << 'Data urut dengan menggunakan Bubble Sort: '
sorting_bubble();
…......................................
cout << 'Data urut dengan menggunakan Insertion Sort: '
sorting_insertion();
…......................................
getch();
return 0;
}
void sorting_selection(){
int i,j;
for(i=0;i<jml-1;i++){
for(j=i+1;j<jml;j++){
if(data[j] < data[i]){
swap(data[j],data[i]);
}
}
}
}
void sorting_bubble(){
int i,j;
i = jml-1;
do{
for(j=0;j<i;j++){
if(data[j+1] < data[j])
swap(data[j+1],data[j]);
}
}
i--;
}while(i>0);
}
void sorting_insertion(int jns){
int i,j;
for(i=0;i<jml;i++){
j = i;
while(j>0){
if(data[j] < data[j-1])
swap(data[j],data[j-1]);
j--;
}
}
}
void swap(int &a, int &b){
…....................
}
Modul Praktikum Struktur Data 4
Sistem Informasi – Fakultas Teknik
Universitas Nusantara PGRI Kediri
E LATIHAN
Latihan buatlah program untuk mengurutkan data menaik dan menurun yang diinputkan dengan salah
satu algoritma pengurutan.
Contoh tampilan program:
Masukkan jumlah data: 5
Data ke-1 : 4
Data ke-2 : 3
Data ke-3 : 5
Data ke-4 : 2
Data ke-5 : 1
Hasil pengurutan dengan metode bubble sort
Menaik : 1 2 3 4 5
Manurun : 5 4 3 2 1
Modul Praktikum Struktur Data 5