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

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 permasalahannya adalah sebagai berikut :

1.2.1.  Apa pengertian sorting?

1.2.2.  Apa saja bagian-bagian sorting?

1.2.3.  Apa fungsi dari bagian-bagian sorting tersebut ?

1.3.   Tujuan

Dari rumusan masalah diatas, adapun tujuan nya adalah sebagai berikut:

1.3.1.  Untuk mengetahui pengertian sorting

1.3.2.  Untuk mengetahui bagian-bagian sorting

1.3.3.  Untuk mengetahui fungsi dari bagian-bagian sorting tersebut

BAB II

PEMBAHASAN

Sorting didefinisikan sebagai pengurutan sejumlah data berdasarkan nilai kunci tertentu. Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending) atau sebaliknya (descending). 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[j­1] > v do

 begin a[j]:=a[j­1]; j:=j­1 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 masing­masing 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 untukalgoritma 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..pivot­1] bernilai lebih kecil atau sama dengan A[pivot]. Untuk menghitung nilai pivot merupakan bagian dari prosedur partition.

Conqueror :  Urutkan subarray A[l..pivot­1] 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,pivot­1);

 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

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 bisa menjadi inspirasi dalam kehidupan sehari-hari, secara tidak sengaja sering kita malakukan prosedur 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.

DAFTAR PUSTAKA

http://en.wikipedia.org/wiki/Sorting_algorithm

lecturer.eepisits.edu/~entin/Struktur%20Data/Minggu%2011/Minggu%2011%20Quick.pdf

http://www.informatika.org/~rinaldi/Stmik/2006/Makalah2006/MakalahStmik2006-27.pdf

http://lecturer.ukdw.ac.id/anton/strukdat.php

http://blog.binadarma.ac.id/andri/?p=65#

http://acieee.wordpress.com/2010/03/10/algoritma-sorting/

http://id.wikipedia.org/wiki/Algoritma_sorting