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.


/*

* program_praktikum_6.2.cpp

*

* Created on: Apr 18, 2014

* Author: ALBERT

*/

#include <iostream>


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;

}


8


Berikut penjelasan listing program_praktikum_6.2.cpp :


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-.




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.


/*

* Praktikum-7.1.cpp

*

* Created on: 12 Mei, 2014

* Author: ALBERT

*/

9

#include <iostream>


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;

}


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.


/*

* Praktikum-7.2.cpp

*


* Author: ALBERT

*/

#include <iostream>


void tampilkan_larik(int data[], int n)

{

int i;

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


}

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;

}



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


/*

* Praktikum-8.1.cpp

*


* Author: ALBERT

*/

#include <iostream>


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;

}


16


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.


/*

* Praktikum-8.2.cpp

*


* Author: ALBERT

*/

#include <iostream>


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;


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



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.


/*

* Praktikum-6.1.cpp

*


* Author: ALBERT

*/

#include <iostream>


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;

}


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



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.


/*

* Praktikum-6.2.cpp

*


* Author: ALBERT

*/

#include <iostream>


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.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 <<"Elemen ke "<<a.i+1<<"="<<a.Arr[a.i]<<endl;

}

return 0;

}


25


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-.




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).







6. Program menggunakan tipe data abstrak typedef dan tipe data abstrak struct. Typedef

digunakan untuk memberi nama lain terhadap variable no yang menjadikan variable

no merupakan tipe data baru bersifat sama dengan tipe data pada pendeklarasian

typedef. Struct pada program menggunakan nama struct isi dengan member nya yang

mana diakses dengan menyamakan variable struct isi dengan variable baru a dan

digunakan dalam int main() dengan menggunakan dot(.).

26


/*

* Praktikum-7.1.cpp

*


* Author: ALBERT

*/

#include <iostream>


typedef int gaga;

void tampilkan_larik(gaga data[], gaga n)

{

gaga i;

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


}

void insertion_sort (gaga data[], gaga n)

{

gaga i, k;

gaga x;

gaga ketemu;

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

x=data[k];

i=k-1;

ketemu=0;

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

if(x<data[i])

27

{

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

i=i-1;

}

else

ketemu=1;

data[i+1]=x;

}

}

}

struct apa

{

gaga i;

gaga JUM_DATA;

};

gaga main()

{

apa a;

a.JUM_DATA=8;

a.i;

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

insertion_sort(data, a.JUM_DATA);

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

tampilkan_larik(data, a.JUM_DATA);

return 0;

}

28



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

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.

3. Dalam program terdapat tipe data abstrak typedef dan struct. Typedef digunakan untuk

memberi alias terhadap variable gaga sehingga menjadi tipe data baru yang memiliki

sifat sama dengan tipe data saat pendeklarasian typedef. Struct pada program

menggunakan nama struct apa dengan member nya yaitu gaga id an gaga JUM_DATA.

Variable struct terlebih dahulu diganti dengan variable a yang digunakan untuk

mengakses member struct yang dihubungkan dengan tanda titik.

29


/*

* Praktikum-7.2.cpp

*


* Author: ALBERT

*/

typedef int ankka;

#include <iostream>


void tampilkan_larik(ankka data[], ankka n)

{

ankka i;

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


}

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

{

ankka x, i, j, tmp;

x=data[p];

i=p;

j=r;

while(1)

{

while(data[j]>x)

j=j-1;

while(data[i]<x)

i=i+1;

if(i<j)

30

{

tmp=data[i];

data[i]=data[j];

data[j]=tmp;

}

else

return j;

}

}

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

{

ankka q;

if(p<r)

{

q=partisi(data, p,r);

quick_sort(data,p,q);

quick_sort(data,q+1,r);

}

}

struct apa

{

ankka JUM_DATA;

ankka i;

};

ankka main()

{

apa d;

d.JUM_DATA=9;

d.i;

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

31

quick_sort(data, 0, d.JUM_DATA-1);

cout <<"\nHasil Pengurutan\n ";

tampilkan_larik(data,d.JUM_DATA);

return 0;

}



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

32

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

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

3. Dalam program terdapat tipe data abstrak typedef dan struct. Typedef pada program

memberikan alias terhadap variable ankka sehingga menjadi tipe data baru yang bertipe

integer. Struct dideklarasikan dengan menggunakan nama struct apa dengan member nya.

Variable struct kemudian diganti dengan variable d dan digunakan untuk mengakses

member struct yang dihubungkan dengan tanda titik.


/*

* Praktikum-8.1.cpp

*


* Author: ALBERT

*/

#include <iostream>


typedef int iente;

void shellsort(iente a[], iente n)

{

iente 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];

33

a[i+m]=mid;

}

}

}

}

}

struct apa

{

iente a[10];

iente i;

iente n;

};

iente main()

{

apa d;

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

cin >>d.n;

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

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

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

}

cout <<"Data sebelum sorting ";

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

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

shellsort(d.a,d.n);

cout<<"\nData setelah sorting ";

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

34

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

return 0;

}



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.


memberikan alias terhadap variable iente sehingga menjadikan variable tersebut tipe

data baru yang bertipe integer. Struct dideklarasikan dengan menggunakan nama struct

apa beserta member nya. Variable struct kemudian diganti dengan variable d dan

digunakan untuk mengakses member struct yang dihubungkan dengan tanda titik.

35


/*

* Praktikum-8.2.cpp

*


* Author: ALBERT

*/

#include <iostream>


typedef int nombre;

nombre a[50];

void merge(nombre, nombre, nombre );

void merge_sort(nombre low, nombre high){

nombre mid;

if(low<high){

mid=(low+high)/2;

merge_sort(low,mid);

merge_sort(mid+1,high);

merge(low,mid,high);

}

}

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

nombre 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++;

36

}

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++;

}

}

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

a[k]=b[k];

}

}

struct apa

{

nombre num;

nombre i;

};

nombre main(){

apa a;

37


cin >>a.num;

cout<<endl;

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

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

cin>>a[a.i];

}

merge_sort(1,a.num);

cout<<endl;

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

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

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

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

return 0;

}


38


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.


memberikan alias terhadap variable nombre. Hal ini menjadikan variable nombre tipe

data baru bertipe integer. Struct dideklarasikan dengan menggunakan nama struct apa

beserta member nya. Variable struct kemudian diganti dengan variable a dan

digunakan untuk mengakses member struct yang dihubungkan menggunakan dot/titik.

39

BAB III

KESIMPULAN

Kesimpulan yang dapat diambil adalah sorting sangat berguna untuk mempermudah dalam

pengurutan data, karena biasanya data yang ada tidaklah sedikit. Metode sorting yang dilakukan

dalam praktikum ini ada 6 yaitu Selection sort, Bubble sort, Insertion sort, Quick sort, Shell sort,

Merge sort. Perbedaannya adalah selection sort melakukan pengecekan pada data satu persatu.

Lain dengan bubble sort, bubble sort memiliki ciri khusus dimana bubble sort melakukan

perbandingan data sebelum dan setelahnya yang mana akan melakukan pertukaran jika terbukti

tidak sesuai dengan aturan yang ada. Insertion sort merupakan sorting yang paling sederhana

dimana sebuah elemen seolah-olah diambil dan disisipkan sehingga elemen-elemen lainnya

bergeser ke belakang. Quick sort memiliki pivot yang setidaknya tidak terlalu besar dibanding

elemen pada sisi kanan atau tidak terlalu kecil dibanding elemen pada sisi kiri karena pivot

digunakan sebagai acuan pembandingan. Shell sort merupakan sorting yang cepat untuk

eksekusi ketika input telah sebagian terurut, namun shell sort adalah teknik sorting yang tidak

stabil dikarenakan terkadang dapat merubah tatanan elemen-elemen dengan value yang mirip.

Merge sort melakukannya dengan cara memenggal elemen-elemen ke dalam kelompok dimana

akan terjadi pengurutan dan setelah urut akan bergabung dengan kelompok lain dan terjadi

seperti itu seterusnya sehingga elemen menjadi urut dan bergabung menjadi satu kelompok

elemen yang terurut. Untuk kecepatan sorting, apabila jumlah operasi perbandingan semakin

banyak ataupun operasi pemindahan data yang banyak maka kecepatan sorting melambat.

40

Sumber Referensi

Ardhana. YM Kusuma. 2013. Struktur Data Dalam Ilustrasi Eclipse Indigo C++

Yogyakarta : CAPS (Center of Academic Publishing Service)

Kristanto, Andi. 2003. Struktur Data Dengan C++

Yogyakarta : Graha Ilmu

laporan praktikum resmi sorting

Documents