MAKALAH
Struktur data
(Sorting)
Disusun oleh :
1.
Eki
syatha rahmat 12152977
2.
Ita
kusumahwaty 12155501
3.
Rahmi utami 12152447
4.
Dwi
fitri novianti 12150205
5.
Deviandayani 12151505
6.
Rafliansyah wiradinata 12153240
7.
Ahmad syauqon annazilli 121554061
8.
Muhammad alnov ceisar 12154772
Kelas 12.2C.07
Jurusan Manajemen Informatika
Mata Kuliah : Struktur Data
BAB I
PENDAHULUAN
1.1.Latar Belakang
Dalam matematika dan
komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan
suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari
awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk
setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan
algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang
memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering
mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika
Boolean dan perbandingan) sampai tugasnya selesai.
Desain dan analisis algoritma adalah suatu cabang khusus
dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu
algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma
tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak,
terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma
yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.
Kompleksitas dari suatu algoritma merupakan ukuran
seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk
menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan
suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah,
sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya
mempunyai kompleksitas yang tinggi.
Sedangkan sorting adalah sebuah proses
merangkai benda dalam urutan tertentu dan/atau dalam himpunan yang berbeda, dan
oleh karena itu dia memiliki dua arti umum yang berbeda:
1. pengurutan: merangkai benda yang
sejenis, sekelas, dll, dalam urutan yang teratur.
2. kategorisasi: pengelompokan dan
pemberian label kepada benda dengan sifat yang serupa.
algoritma sorting terdiri dari beberapa
algoritma seperti Bubble sort, Quick sort, Selection Sort, Insertion
Sort, dan Merge Sort yang dimana setiap jenis sorting ini
memiliki perbedaan satu sama lainnya.
1.2.Rumusan Masalah
Dari latar belakang diatas adapun permasalahan kami adalah
sebagai berikut :
1.2.1. Apa pengertian algoritma sorting?
1.2.2.
Apa saja
bagian-bagian algoritma sorting?
1.2.3. Apa fungsi dari bagian-bagian
algoritma sorting tersebut ?
1.3.
Tujuan
Dari rumusan masalah diatas, adapun
tujuan kami adalah sebagai berikut:
1.3.1. Untuk mengetahui pengertian
algoritma sorting?
1.3.2.
Untuk
mengetahui bagian-bagian algoritma sorting?
1.3.3. Untuk mengetahui fungsi dari
bagian-bagian algoritma sorting tersebut ?
BAB II
PEMBAHASAN
Sorting didefinisikan sebagai pengurutan
sejumlahdata berdasarkan nilai kunci tertentu. Pengurutan dapat dilakukan dari
nilai terkecil ke nilai terbesar (ascending) atau sebaliknya
(descending).Algoritma Sorting termasuk salah satu contoh yangkaya akan solusi.
Dalam makalah ini, hanya akan dibahas lima algoritma sorting yang populer
dipakai didunia informatika.
2.1. Bubble Sort
Bubble Sort merupakan cara pengurutan yang
sederhana. Konsep dari ide dasarnya adalah seperti “gelembung air” untuk elemen
struktur data yang semestinya berada pada posisi awal. Cara kerjanya adalah
dengan berulang-ulang melakukan traversal (proses looping) terhadap
elemen-elemen struktur datayang belum diurutkan. Di dalam traversal tersebut,
nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak
sesuai dengan “pesanan”, maka dilakukan pertukaran (swap). Algoritma sortingini
disebut juga dengan comparison sort dikarenakanhanya mengandalkan perbandingan
nilai elemen untuk mengoperasikan elemennya.
Algoritma bubble sort dapat
diringkas sebagai berikut, jika N adalah panjang elemen struktur data, dengan
elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:
1. Lakukan traversal untuk
membandingkan dua elemen berdekatan. Traversal ini dilakukan dari belakang.
2. Jika elemen pada TN-1 > TN , maka
lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses traversal berikutnya
sampai bertemu dengan bagian struktur data yang telah diurutkan.
3. Ulangi langkah di atas untuk
struktur data yang tersisa.
Pseudocode dari bubble Sort adalah sebagai berikut;
For I = 0 to N - 2
For J = 0 to N - 2
If (A(J)
> A(J + 1)
Temp = A(J)
A(J) = A(J + 1)
A(J + 1) = Temp
End-If
End-For
End-For
2.2. Selection Sort
Selection Sort adalah sort yang melakukan beberapa kali pass
untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending
(menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut,
disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks
yang disimpan tersebut dengan elemen yang paling depan yang belum urut.
Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar
yang disimpan indeksnya kemudian ditukar.
Algoritma selection sort dapat dirangkum sebagai berikut:
1. Temukan nilai yang paling minimum
(atau sesuai keinginan) di dalam struktur data. Jika ascending, maka yang harus
ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai
yang paling maksimum.
2. Tukar nilai tersebut dengan nilai
pada posisipertama di bagian struktur data yang belum diurutkan.
3. Ulangi langkah di atas untuk bagian
struktur datayang tersisa.
Pseudocode dari selection Sort adalah sebagai berikut;
For I = 0 to N-1 do:
Smallsub = I
For J = I + 1 to N-1
do:
If A(J)
< A(Smallsub)
Smallsub = J
End-If
End-For
Temp = A(I)
A(I) = A(Smallsub)
A(Smallsub) = Temp
End-For
2.3. Insertion Sort
Metode pengurutan pada insertion sort adalah metode dengan cara menyisipkan elemen larik pada
posisi yang tepat.Cara kerja insertion sort, Pertama-tama, dilakukan
iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian
menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya
dilakukan. Dari proses iterasi, seperti biasa, terbentuklah bagian yang
telah di-sorting dan bagian yang belum di-sorting.
Algoritma Insertion Sort dapat dirangkum sebagai berikut:
1. Simpan nilai Ti kedalam variabel
sementara, dengan i = 1.
2. Bandingkan nilainya dengan elemen
sebelumnya.
3. Jika elemen sebelumnya (Ti-1) lebih
besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement
i (kurangi nilainya dengan 1).
4. Lakukan terus poin ke-tiga, sampai
Ti-1 ≤ Ti.
5. Jika Ti-1 ≤ Ti terpenuhi, tindih
nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
6. Ulangi langkah dari poin 1 di atas
dengan i di-increment (ditambah satu).
Pseudocode dari Insertion Sort adalah sebagai berikut;
procedure insertion;
var i,j,v: integer;
begin
for i:=2 to N do
begin
v:=a[i];j:=1;
while a[j1] > v do
begin a[j]:=a[j1]; j:=j1 end;
a[j]:=v;
end
end;
2.4. Merge Sort
Algoritma Merge Sort ditemukan oleh John
vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and
conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma
ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu.
Intinya, algoritma ini menggunakan dua ide utama sebagai berikut,
1. Sebuah list yang kecil membutuhkan
langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
2. Untuk membentuk sebuah list terurut
dari duabuah list terurut membutuhkan langkah yangl ebih sedikit daripada
membentuk sebuah list terurut dari dua buah list tak terurut. Contoh:hanya
diperlukan satu kali traversal untuk masing-masing list jika keduanya
sudahterurut.
Algoritma Merge Sort sederhananya, dapat ditulis berikut:
1. Bagi list yang tak terurut menjadi
dua sama panjang atau salah satunya lebih panjang satu elemen.
2. Bagi masing-masing dari 2 sub-list
secara rekursif sampai didapatkan list dengan ukuran 1.
3. Gabung 2 sublist kembali menjadi
satu list terurut.
Berikut
ini adalah tiga proses di dalam menggunakan algoritma Merge Sort :
Divide : Bagi array A[l..r] dengan jumlah elemen n menjadi dua subarray
dengan jumlah elemen masingmasing subarray sebanyak n/2.
Conqueror :
Urutkan masing-masing subarray secara rekursif menggunakan prosedur merge
sort
Combine
:
Satukan subarray untuk menghasilkan elemen array A[l..r] yang
terurut.
Berikut ini adalah algoritma untuk Merge Sort array A[l..r]:
Merge-Sort (A,l,r)
1. if l < r
2.
then q := [(l+r) /2]
3.
Merge-Sort(A,l,q)
4.
Merge-Sort(A,q+1,r)
5. Merge(A,p,q,r)
Sedangkan algoritma untuk prosedure Merge adalah sebagai berikut :
MERGE ( A, l, q, r)
1. n1 ← q − l
+ 1
2. n2 ← r − q
3. create
arrays L[1 . . n 1 + 1] and R[1 . . n 2 + 1]
4. for i ← 1
to n 1
5.
do L[i] ← A[ l + i − 1]
6. for j ← 1
to n 2
7.
do R[ j ] ← A[q + j ]
8. L[n 1 + 1] ← ∞
9. R[n 2 + 1] ← ∞
10. i ← 1
11. j ← 1
12. for k ← l to r
13.
do if
L[i] ≤ R[ j ]
14.
then A[k] ← L[i]
15.
i ←i +1
16.
else A[k] ← R[ j ]
17.
j ← j +1
2.5. Quick Sort
Quick Sort adalah algoritma sorting yang
terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk
perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini
rekursif, dan termasuk paradigma algoritma divide and conquer.
Algoritma ini terdiri dari 4 langkah utama:
1. Jika struktur data terdiri dari 1
atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.
2. Ambil sebuah elemen yang akan
digunakansebagai pivot point (poin poros). (Biasanya elemen yang paling
kiri.)
3. Bagi struktur data menjadi dua
bagian – satu dengan elemen-elemen yang lebih besar daripada pivot point, dan
yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.
4. Ulangi algoritma secara rekursif
terhadap kedua paruh struktur data.
Berikut adalah tiga proses di dalam metode divide dan conqueror
untuk algoritma Quick Sort:
Divide
: Bagi array A[l..r] menjadi dua
subarray A[l..pivot-1] dan A[pivot+1..r] sehingga setiap elemen
di dalam sub array A[l..pivot1] bernilai lebih kecil atau sama dengan A[pivot].
Untuk menghitung nilai pivot merupakan bagian dari
prosedur partition.
Conqueror : Urutkan subarray A[l..pivot1] dan
A[pivot+1..r] secara rekursif ke prosedur quicksort
Combine : Karena subarray sudah terurut, maka array A[l..r] sudah terurut.
Pseudocode dari algoritma quick sort adalah sebagai berikut:
procedure quicksort(l,r:integer);
var pivot: integer;
begin
for r > l then
begin
pivot:=partition(l,r);
quicksort(l,pivot1);
quicksort(pivot+1,r);
end
end;
Algoritma dari partisi array A[l..r] adalah :
x := A[r]
i := l-1
for j := l to r-1
do if
A[j] <= x
then i := i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return
i+1
Contoh program sorting:
Contoh Program Sorting Menggunakan Bubble
Sort pada C++ , berikut Source Codenya :
#include <iostream>
#include <conio.h>
int data[10],data2[10];
int n;
void tukar(int a,int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}
void Input()
{
cout<<"Masukkan jumlah data = ";cin>>n;
cout<<"--------------------------------------"<<endl;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = ";cin>>data[i];
data2[i] = data[i];
}
cout<<endl;
}
void Tampil()
{
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}void bubble_sort()
{
for(int i=1;i<n;i++)
{
for(int j=n-1;j>=i;j--)
{
if(data[j]<data[j-1]) tukar(j,j-1);
}
Tampil();
}
cout<<endl;
}
main()
{
cout<<"*-------------------------------------*"<<endl;
cout<<"* Selamat datang di aplikasi *"<<endl;
cout<<"* Bubble Sort *"<<endl;
cout<<"*-------------------------------------*"<<endl;
Input();
cout<<"Proses Bubble Sort,,,,,,,"<<endl;
cout<<"-------------------------------------"<<endl;
Tampil();
bubble_sort();
cout<<"-------------------------------------"<<endl;
cout<<" TERIMA KASIH "<<endl;
cout<<"-------------------------------------"<<endl;
getch();}
#include <iostream>
#include <conio.h>
int data[10],data2[10];
int n;
void tukar(int a,int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}
void Input()
{
cout<<"Masukkan jumlah data = ";cin>>n;
cout<<"--------------------------------------"<<endl;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = ";cin>>data[i];
data2[i] = data[i];
}
cout<<endl;
}
void Tampil()
{
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}void bubble_sort()
{
for(int i=1;i<n;i++)
{
for(int j=n-1;j>=i;j--)
{
if(data[j]<data[j-1]) tukar(j,j-1);
}
Tampil();
}
cout<<endl;
}
main()
{
cout<<"*-------------------------------------*"<<endl;
cout<<"* Selamat datang di aplikasi *"<<endl;
cout<<"* Bubble Sort *"<<endl;
cout<<"*-------------------------------------*"<<endl;
Input();
cout<<"Proses Bubble Sort,,,,,,,"<<endl;
cout<<"-------------------------------------"<<endl;
Tampil();
bubble_sort();
cout<<"-------------------------------------"<<endl;
cout<<" TERIMA KASIH "<<endl;
cout<<"-------------------------------------"<<endl;
getch();}
Tampilan Hasil :
BAB III
PENUTUP
3.1. Kesimpulan
Algoritma yang mudah dalam hal
implementasi adalah Bubble Sort, Selection Sort, dan Insertion Sort. Ketiganya
memiliki kompleksitas O(n2). Di antara algoritma ini, yang paling effisien
adalah Insertion Sort. Algoritma yang lebih mangkus adalah MergeSort dan
Quick Sort dengan kompleksitasnya adalah O(n log n). Adapun yang paling mangkus
dari lima algoritma ini adalah Quick Sort.
3.2.
Saran
Dengan disusunya makalah ini, semoga makalah ini bias
menjadi infirasi dalam kehidupan sehari-hari, secara tidak sengaja sering kita
malakukan prosedut semacam ini di kehidupan sehari-hari seperti melakukan
langkah mencuci baju, menjalankan sepeda motor.itu semua adalah algoritma yang
dilakukan dalam kehidupan sehari-hari.begitu juga dalam computer atau didalam
bahasa pemrograman. Jika langkah-langkah dalam kehidupan sehari-hari kita
amati, hampir tidak jauh beda dengan langkah-langkah pemrograman.
Tidak ada komentar:
Posting Komentar