Laporan Praktikum Resmi Sorting

LAPORAN PRAKTIKUM RESMI

SORTING

Disusun oleh :

Albert Sugihartono

201301018

Dosen pengampu :

Yosef Murya Kusuma Ardhana.S.T., M.Kom

JURUSAN SISTEM INFORMASI

SEKOLAH TINGGI ILMU KOMPUTER YOS SUDARSO

PURWOKERTO

2014

2

BAB I

TEORI DASAR

1. Pengantar

Sort atau sorting adalah suatu proses pengurutan data yang sebelumnya disusun secara acak

atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu. Biasanya

pengurutan terbagi menjadi dua yaitu ascending dan descending. Dalam melakukan proses

sorting terdapat beberapa hal yang mempengaruhi kecepatan sorting itu sendiri, diantaranya

jumlah operasi perbandingan yang dilakukan dan juga jumlah operasi pemindahan data yang

dilakukan. Pada praktikum ini dilakukan 6 jenis sorting yaitu Selection sort, Bubble sort,

Insertion sort, Quick sort, Shell sort dan Merge sort.

1. Selection sort

Selection sort adalah suatu metode pengurutan yang membandingkan elemen yang ada

sekarang dengan elemen atau bilangan berikutnya sampai ke elemen atau bilangan yang

terakhir. Jika diketemukan bilangan yang lebih kecil daripada bilangan yang ada sekarang,

maka akan dicatat dan dipertukarkan posisinya.

2. Bubble sort

Bubble sort merupakan suatu metode pengurutan yang membandingkan data yang sekarang

dengan data berikutnya. Apabila data yang sekarang lebih besar daripada data berikutnya

maka posisi akan ditukar, bila tidak maka tidak perlu ditukar.

3. Insertion sort

Insertion sort merupakan teknik pengurutan data yang mana seolah-olah mengambil sebuah

elemen dari tempat tertentu, kemudian menyisipkan (insert) ke suatu tempat hingga

elemen-elemen lain bergeser ke belakang sehingga menjadikan teknik ini adalah teknik

yang paling sederhana.

4. Quick sort

Quick sort merupakan teknik sorting yang membandingkan suatu elemen (pivot) dengan

elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen-elemen lain yang

3

lebih kecil dari pivot terletak disebelah kirinya dan elemen-elemen lain yang lebih besar

daripada pivot tersebut terletak disebelah kanannya.

5. Shell sort

Shell sort merupakan teknik sorting yang mengurutkan data dengan cara membandingkan

suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan pertukaran

jika diperlukan.

6. Merge sort

Merge sort merupakan teknik pengurutan data dengan cara menggabungkan setiap kali dua

deretan elemen dan melakukan pengurutan terhadap elemen-elemen tersebut.

4

BAB II

PENJELASAN PROGRAM

1. Latihan Praktikum

Pada bab latihan praktikum ini membahas tentang listing program yang digunakan pada

praktikum ini yaitu listing program_praktikum_6.1.cpp; program_praktikum_6.2.cpp;

program_praktikum_7.1.cpp; program_praktikum_7.2.cpp; program_praktikum_8.1.cpp; dan

program_praktikum_8.2.cpp.

Listing program_praktikum_6.1.cpp

/*

* Praktikum-6.1.cpp

*

* Created on: Apr 18, 2014

* Author: ALBERT

*/

#include <iostream>

using namespace std;

int main(){

int i, j, iMin;

int n, Urut;

int Tmp;

int Arr[50];

cout <<"Inputkan banyak data yang akan diurutkan : ";

cin >>n;

Urut = 1;

for(i=0; i<n;i++){

cout <<"Masukan data ke "<<i+1<<"=";

cin >>Arr[i];

}

for(i=0; i<n-1;i++){

iMin=i;

for(j=Urut; j<n; j++){

if(Arr[j] < Arr[iMin]){

iMin=j;

if(Arr[i] != Arr[iMin]){

Tmp=Arr[i];

if(Arr[i]> Arr[iMin]){

Arr[i]=Arr[iMin];

Arr[iMin]=Tmp;

5

}

Urut = Urut+1;

}

cout <<"\nSetelah Pengurutan\n";

for(i=0; i<n; i++)

{

cout <<"Elemen ke "<<i+1<<"="<<Arr[i]<<endl;

}

return 0;

}

Output program_praktikum_6.1.cpp

Hasil output dari program_praktikum_6.1.cpp adalah sebagai berikut :

Penjelasan program_praktikum_6.1.cpp

Berikut penjelasan dari Listing program_praktikum_6.1.cpp :

1. Pada awal program, dideklarasikan variable-variabel sorting yaitu i untuk data ke- atau

tepatnya untuk indeks array, j dan iMin untuk membandingkan data yang besar atau kecil,

n adalah jumlah data,variable tmp digunakan sebagai tempat penampungan array sementara

dan arr[50] digunakan untuk array data ke-.

2. Untuk input array digunakan perulangan for dimana variable i diset 0 dan apabila i<n

dimana n adalah jumlah yang diinputkan user, maka i bertambah sebanyak 1. Ini akan

memunculkan data ke-i untuk input data arraynya hingga i mencapai dibawah n.

6

3. Sorting diatas merupakan sorting selection secara ascending dimana dilakukan perulangan

for untuk membandingkan data yang ada yaitu iMin (indeks minimum) yang

diassignmentkan kondisinya sama dengan indeks array sekarang (i).

4. iMin dibandingkan dengan variable j yang dsudah diassignmentkan dengan Urut (value =

1) dengan menggunakan fungsi if. Jika j terbukti lebih kecil daripada iMin maka iMin akan

diassignmentkan sama dengan j.

Listing program_praktikum_6.2.cpp

/*

* program_praktikum_6.2.cpp

*

* Created on: Apr 18, 2014

* Author: ALBERT

*/

#include <iostream>

using namespace std;

int main()

{

int j,i,n;

int tmp;

int arr[50];

cout<<"Inputkan banyak data yang akan diurutkan : ";

cin>>n;

for(i=0;i<n;i++)

{

cout<<"Masukkan data ke "<<i+1<<" = ";

cin>>arr[i];

}

7

for(i=1;i<n;i++)

{

for(j=0;j<n-1;j++)

{

if(arr[j]>arr[j+1])

{

tmp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=tmp;

}

cout<<"\nSetelah Pengurutan Data\n";

for(i=0;i<n;i++)

{

cout<<"Elemen ke "<<i+1<<" : "<<arr[i]<<endl;

}

return 0;

}

Output program_praktikum_6.2.cpp

8

Penjelasan program_praktikum_6.2.cpp

Berikut penjelasan listing program_praktikum_6.2.cpp :

1. Pada awal program, dideklarasikan variable-variabel sorting yaitu i untuk data ke- atau

tepatnya untuk indeks array, j membandingkan data yang besar dengan kecil, n adalah

jumlah data,variable tmp digunakan sebagai tempat penampungan array sementara dan

arr[50] digunakan untuk array data ke-.

2. Untuk input array digunakan perulangan for dimana variable i diset 0 dan apabila i<n

dimana n adalah jumlah yang diinputkan user, maka i bertambah sebanyak 1. Ini akan

memunculkan data ke-i untuk input data arraynya hingga i mencapai dibawah n.

3. Untuk proses sort program diatas menggunakan metode bubble sort secara ascending.

Pertama akan dilakukan pengulangan for pada variable j dengan variable j diset 0 hingga j

lebih kecil dari jumlah n-1;n adalah jumlah input yang diberi user.

4. Kemudian variable j dimasukkan kedalam array dan variable j (arr[j]) akan dibandingkan

valuenya dengan value dari variable j setelahnya (arr[j + 1]). Jika ternyata variable j

sebelumya lebih besar dari variable j setelahnya, variable j sebelumnya akan ditampung

sementara pada variable tmp (tmp = ar[j]) sementara variabel j lama akan

diassignmentkan dengan value dari variable j yang baru, kemudian variable j yang baru

akan diassignmentkan dengan value dari variable j yang lama. Dengan begitu value akan

bertukar tempat.

Listing program_praktikum_7.1.cpp

/*

* Praktikum-7.1.cpp

*

* Created on: 12 Mei, 2014

* Author: ALBERT

*/

9

#include <iostream>

using namespace std;

void tampilkan_larik(int data[], int n)

{

int i;

for(i=0; i<n; i++)

cout <<data[i]<<" "<<endl;

}

void insertion_sort (int data[], int n)

{

int i, k;

int x;

int ketemu;

for(k=1; k<n; k++){

x=data[k];

i=k-1;

ketemu=0;

while((i>=0) && (!ketemu)){

if(x<data[i])

{

data[i+1]=data[i];

i=i-1;

}

else

ketemu=1;

data[i+1]=x;

}

10

}

int main(){

int JUM_DATA=8;

int i;

int data[]={25, 57, 48, 37, 12, 92, 80, 33};

insertion_sort(data, JUM_DATA);

cout <<"Hasil Pengurutan Data :\n";

tampilkan_larik(data, JUM_DATA);

return 0;

}

Output program_praktikum_7.1.cpp

Penjelasan listing program_praktikum_7.1.cpp

Berikut penjelasan listing program dari program_praktikum_7.1.cpp :

1. Pertama kali dibuat sebuah fungsi perulangan for yang digunakan untuk memberikan

data ke-i dari x yang disisipkan ke dalam data.

2. Dari data ke i, kemudian dilakukan sebuah perbandingan dengan data selanjutnya. i

dibandingkan dengan data sebelumnya dan jika i lebih besar dari data yang

11

dibandingkan, maka i akan ditukar tempatnya dengan data tersebut, jika i lebih kecil

dari data yang dibandingkan maka i tidak akan ditukarkan namun akan dibandingkan

dengan data sebelumnya lagi dan akan dibandingkan lagi seperti sebelumnya.

Listing program_praktikum_7.2.cpp

/*

* Praktikum-7.2.cpp

*

* Created on: 12 Mei, 2014

* Author: ALBERT

*/

#include <iostream>

using namespace std;

void tampilkan_larik(int data[], int n)

{

int i;

for(i=0; i<n; i++)

cout <<data[i]<<" "<<endl;

}

int partisi(int data[],int p, int r)

{

int x, i, j, tmp;

x=data[p];

i=p;

j=r;

while(1)

{

while(data[j]>x)

12

j=j-1;

while(data[i]<x)

i=i+1;

if(i<j)

{

tmp=data[i];

data[i]=data[j];

data[j]=tmp;

}

else

return j;

}

void quick_sort(int data[], int p, int r)

{

int q;

if(p<r)

{

q=partisi(data, p,r);

quick_sort(data,p,q);

quick_sort(data,q+1,r);

}

int main()

{

int JUM_DATA=9;

int i;

int data[]={25, 57, 48, 12, 37, 92, 80, 33, 1};

quick_sort(data, 0, JUM_DATA-1);

13

cout <<"\nHasil Pengurutan\n ";

tampilkan_larik(data,JUM_DATA);

return 0;

}

Output program_praktikum_7.2.cpp

Penjelasan listing program_praktikum_7.2.cpp

Berikut penjelasan dari listing program_praktikum_7.2.cpp :

1. Program memiliki variable i dan j dimana kedua variable tersebut merupakan variable

yang digunakan sebagai elemen yang akan dibandingkan dengan elemen yang lain. i

dimulai dari indeks 0 dan bertambah 1 dan j dimulai dari indeks ke n data dan berkurang

1.

2. Pada kasus i, jika elemen yang dibandingkan lebih besar dengan elemen yang

dibandingkan yaitu x (pivot) maka tidak akan ditukar dengan elemen pivot dan jika lebih

kecil, maka akan ditukarkan dengan elemen pivot dan i bertambah 1 sehingga indeks

bergeser sebanyak 1. Begitu juga sebaliknya pada kasus j hanya saja j bukan bertambah 1

untuk bergeser indeks namun berkurang 1. Jika saat i dibandingkan dengan pivot lebih

kecil, proses berikutnya yaitu j dibandingkan dan i bertambah satu. Jika saat proses j

dibandingkan dengan pivot lebih besar, maka j akan berkurang 1.

14

Listing program_praktikum_8.1.cpp

/*

* Praktikum-8.1.cpp

*

* Created on: 12 Mei, 2014

* Author: ALBERT

*/

#include <iostream>

using namespace std;

void shellsort(int a[], int n)

{

int j, i, k, m, mid;

for(m=n/2; m>0;m/=2){

for(j=m; j<n; j++){

for(i=j-m; i>=0; i-=m){

if(a[i+m]>=a[i])

break;

else{

mid=a[i];

a[i]=a[i+m];

a[i+m]=mid;

}

int main()

{

int a[10], i, n;

15

cout <<"Inputkan banyak data yang akan disorting : ";

cin >>n;

for(i=0; i<n; i++){

cout <<"Data "<<i+1<<"=";

cin >>a[i];

}

cout <<"Data sebelum sorting ";

for(i=0; i<n; i++)

cout <<a[i]<<" ";

shellsort(a,n);

cout<<"\nData setelah sorting ";

for(i=0; i<n; i++)

cout<<a[i]<<" ";

return 0;

}

Output program_praktikum_8.1.cpp

16

Penjelasan listing program_praktikum_8.1.cpp

Berikut penjelasan listing program_praktikum_8.1.cpp:

1. Pada awal perulangan dimasukkan data yang diinputkan user yaitu a[i] dimana i

merupakan indeks atas value yang diinputkan user dan n yang merupakan banyaknya

data yang ada.

2. Pada proses perulangan, data dibagi 2 menjadi bagian atas dan bagian bawah yaitu

dilakukan oleh perulangan terluar pada program sehingga menjadikannya pengontrol

gap antar elemen yang dibandingkan.

3. Elemen yang dibandingkan berdasarkan bagian yang ada. Sebagai contoh elemen

pertama atas dengan elemen kedua atas dibandingkan dan seterusnya. Jika elemen

bagian pertama lebih besar dengan elemen bagian kedua, maka akan terjadi

pertukaran dan jika tidak maka tidak ada pertukaran dan “gap” akan berkurang satu

hingga tersisa elemen dengan gap berada ditengah.

Listing program_praktikum_8.2.cpp

/*

* Praktikum-8.2.cpp

*

* Created on: 12 Mei, 2014

* Author: ALBERT

*/

#include <iostream>

using namespace std;

int a[50];

void merge(int, int, int );

void merge_sort(int low, int high){

int mid;

if(low<high){

mid=(low+high)/2;

17

merge_sort(low,mid);

merge_sort(mid+1,high);

merge(low,mid,high);

}

void merge(int low, int mid, int high){

int h, i, j, b[50],k;

h=low;

i=low;

j=mid+1;

while((h<=mid) && (j<=high)){

if(a[h]<=a[j]){

b[i]=a[h];

h++;

}

else{

b[i]=a[j];

j++;

}

i++;

}

if(h>mid){

for(k=j; k<=high;k++){

b[i]=a[k];

i++;

}

else{

for(k=h; k<=mid;k++){

b[i]=a[k];

i++;

}

18

}

for(k=low;k<=high;k++){

a[k]=b[k];

}

int main(){

int num, i;

cout <<"Inputkan banyak data yang akan diurutkan : ";

cin >>num;

cout<<endl;

cout <<"Masukkan ("<<num<<") data "<<endl;

for(i=1; i<=num; i++){

cin>>a[i];

}

merge_sort(1,num);

cout<<endl;

cout <<"\nSetelah pengurutan (Merge Sort) :"<<endl;

for(i=1;i<=num;i++)

cout<<a[i]<<" ";

cout <<endl<<endl<<endl<<endl;

return 0;

}

19

Output program_praktikum_8.2.cpp

Penjelasan listing program_praktikum_8.2.cpp

1. Pertama kali, program dibuat sublist atau penggalan yaitu low, mid dan high dengan

menggunakan prosedur merge_sort dan dimasukkan ke dalam prosedur merge

dimana low di set 1 saat pemanggilan prosedur merge_sort dan high adalah jumlah

banyaknya data.

2. Data pada masing-masing penggalan dibandingkan pada fungsi perulangan while

yang mana elemen sudah dimasukkan ke dalam sublist yang terurut (h, i, j).

3. Setelah elemen pada sublist terurut, maka sublist akan bergabung dengan sublist lain

yang terurut menjadikan jumlah elemen sublist bertambah. Sublist dengan elemen

yang telah terurut akan bergabung dengan sublist yang telah urut elemennya hingga

menjadikan satu sublist yang terurut.

20

Tugas Praktikum

Pada tugas praktikum ini akan dijelaskan program praktikum 6.1, 6.2, 7.1, 7.2, 8.1 dan 8.2

dengan menggunakan typedef dan struct.

Listing program_praktikum_6.1.cpp

/*

* Praktikum-6.1.cpp

*

* Created on: 12 Mei, 2014

* Author: ALBERT

*/

#include <iostream>

using namespace std;

typedef int ini;

struct apa

{

ini i, j, iMin;

ini n, Urut;

ini Tmp;

ini Arr[50];

};

struct apa a;

ini main()

{

cout<<"Inputkan banyak data yang akan diurutkan : ";

cin >>a.n;

a.Urut = 1;

for(a.i=0;a.i<a.n;a.i++)

{

cout <<"Masukan data ke "<<a.i+1<<"=";

21

cin >>a.Arr[a.i];

}

for(a.i=0;a.i<a.n-1;a.i++){

a.iMin=a.i;

for(a.j=a.Urut;a.j<a.n;a.j++){

if(a.Arr[a.j]<a.Arr[a.iMin]){

a.iMin=a.j;

if(a.Arr[a.i] != a.Arr[a.iMin]){

a.Tmp=a.Arr[a.i];

if(a.Arr[a.i]>a.Arr[a.iMin]){

a.Arr[a.i]=a.Arr[a.iMin];

a.Arr[a.iMin]=a.Tmp;

}

a.Urut = a.Urut+1;

}

cout <<"\nSetelah Pengurutan\n";

for(a.i=0;a.i<a.n;a.i++)

{

cout <<"Elemen ke "<<a.i+1<<"="<<a.Arr[a.i]<<endl;

}

return 0;

}

22

Output program_praktikum _6.1.cpp

Penjelasan program_praktikum_6.1.cpp

1. Pada awal program, dideklarasikan variable-variabel sorting yaitu i untuk data ke- atau

tepatnya untuk indeks array, j dan iMin untuk membandingkan data yang besar atau

kecil, n adalah jumlah data,variable tmp digunakan sebagai tempat penampungan

array sementara dan arr[50] digunakan untuk array data ke-.

2. Untuk input array digunakan perulangan for dimana variable i diset 0 dan apabila

i<n dimana n adalah jumlah yang diinputkan user, maka i bertambah sebanyak 1. Ini

akan memunculkan data ke-i untuk input data arraynya hingga i mencapai dibawah n.

3. Sorting diatas merupakan sorting selection secara ascending dimana dilakukan

perulangan for untuk membandingkan data yang ada yaitu iMin (indeks minimum)

yang diassignmentkan kondisinya sama dengan indeks array sekarang (i).

4. iMin dibandingkan dengan variable j yang dsudah diassignmentkan dengan Urut

(value = 1) dengan menggunakan fungsi if. Jika j terbukti lebih kecil daripada iMin

maka iMin akan diassignmentkan sama dengan j.

5. Program menggunakan tipe data abstrak typedef dan struct. Typedef dalam program

digunakan untuk memberi alias terhadap variable ini yang menjadikan variable ini

tipe data baru bertipe integer (bersifat sama dengan tipe datanya saat typedef). Struct

menggunakan nama struct apa dengan member nya yang digunakan untuk

23

perulangan. Member pada struct diakses dengan menyamakan variable struct apa

dengan variable baru a dan digunakan dalam int main() dengan menggunakan dot(.).

Sebagai contoh a.Urut.

Listing program_praktikum_6.2.cpp

/*

* Praktikum-6.2.cpp

*

* Created on: 12 Mei, 2014

* Author: ALBERT

*/

#include <iostream>

using namespace std;

typedef int no

struct isi

{

no i, j, n;

no Tmp;

no Arr[50];

};

no main(){

isi a;

cout <<"Inputkan banyak data yang akan diurutkan :";

cin >>a.n;

for(a.i=0;a.i<a.n;a.i++){

cout <<"Masukan data ke "<<a.i+1<<"=";

cin >>a.Arr[a.i];

24

}

for(a.i=1;a.i<a.n;a.i++){

for(a.j=0;a.j<a.n-1;a.j++){

if(a.Arr[a.j]>a.Arr[a.j+1]){

a.Tmp=a.Arr[a.j];

a.Arr[a.j]=a.Arr[a.j+1];

a.Arr[a.j+1]=a.Tmp;

}

cout <<"\nSetelah Pengurutan\n";

for(a.i=0;a.i<a.n;a.i++){

cout <<"Elemen ke "<<a.i+1<<"="<<a.Arr[a.i]<<endl;

}

return 0;

}

Output program_praktikum_6.2.cpp

25

Penjelasan program_praktikum_6.2.cpp

1. Pada awal program, dideklarasikan variable-variabel sorting yaitu i untuk data ke-

atau tepatnya untuk indeks array, j dan iMin untuk membandingkan data yang besar

atau kecil, n adalah jumlah data,variable tmp digunakan sebagai tempat

penampungan array sementara dan arr[50] digunakan untuk array data ke-.