tugas bab 4 bagus haruman - ms rabbani
TRANSCRIPT
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
1/24
TUGAS BAB 4
STRUKTUR DATA
Bagus Haruman 10110710
M Sayyaf Rabbani 10109289
Jurusan Teknik InformatikaFakultas Teknik dan Ilmu Komputer
UNIVRSITAS K!"#UTR IND!NSIA$%&'
22 23
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
2/24
Pendahuluan
1.1 Latar Belakang
Dalam ilmu lo(ika dan al(oritma serin( kali menemui masala) tentan( *a(aimana
mendapatkan suatu data dalam kumpulan data+ Dalam keperluann,a untuk men-ari
data. terdapat *era(am al(oritma pen-arian/sear-) al(oritm0+ Al(oritma sendiri
merupakan 1al(oritma ,an( menerima se*ua) ar(umen 2a3 dan men-o*a untuk
menemukan se*ua) rekaman ,an( memiliki kun-i 2a3+ #en-arian dapat dilakukan
ter)adap data ,an( se-ara keseluru)an *erada dalam memor, komputer ataupun
,an( *erada dalam pen,impanan ekternal /)ardisk0+ #en-arian ,an( dilakukan
ter)adap data ,an( *erada dalam komputer di kenal den(an pen-arian internal
sedan(kan pen-arian ,an( dilakukan pada media pen,impanan eksternal dise*ut
pen-arian ekternal+ #en-arian internal meliputi #en-arian sekuensial /seuential
sear-)0 dan pen-arian *iner /*inar, sear-)0+
1.2 Rumusan Masalah
Ba(aimana al(oritma pen-arian *erurutan itu dan men(aplikaskann,a pada
se*ua) pro(ram+
1.3 Tujuan dan manfaat
&+ "en(ka5i metode Sear-)in( 6inier seuential se*a(ai pro(ram dalam
men,elesaikan pen-arian *erurutan+
$+ #en((unaan "etode Sear-)in( 6inier Seuential dalam men,elesaikan masala)7masala) ,an( ada+
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
3/24
2.1 Pembahasan
Seuential Sear-) adala) proses mem*andin(kan setiap elemen larik satu per satu
se-ara *eruntun. mulai dari elemen pertama sampai elemen ,an( di-ari ditemukan
atau seluru) elemen suda) diperiksa+ Al(oritma pen-arian se-ara linear di(unakan
untuk men-ari se*ua) nilai pada ta*el sem*aran(+ Ada dua ma-am -ara pen-arian
pada ta*el+ Al(oritma ini mempun,ai dua 5enis metode ,aitu den(an *oolean dan
tanpa *oolean+ Al(oritma pen-airan se-ara linear melakukan pen(ulan(an se*an,ak
& kali untuk kasus ter*aik /8alue sama den(an elemen pertama dalam ta*el0 dan
Nma9 kali untuk kasus ter*uruk+ Se)in((a al(oritma ini mempun,ai kompleksitas
al(oritma +
#roses pen-arian data den(an metode ini -ukup seder)ana dan muda) dipa)ami+
Dalam pen-arian ini proses dilakukan den(an -ara men-o-okan data ,an( akan
di-ari den(an semua data ,an( ada dalam kelompok data+ #roses pen-arian data
dilakukan den(an -ara men-o-okan data ,an( akan di-ari den(an semua data ,an(
ada dalam kelompok data+ #roses pen-o-okan data dilakukan se-ara *erurut satu
demi satu dimulai dari data ke7& )in((a data pada ururtan terak)ir+ Jika data ,an(
di-ari mempun,ai )ar(a ,an( sama den(an data ,an( ada dalam kelompok data.
*erarti data tela) ditemukan+ Tetapi 5ika data ,an( di-ari tidak ada ,an( -o-ok
den(an data7data dalam sekelompok data. *erarti data terse*ut tidak ada dalam
sekelompok data+ Selan5utn,a kita tin((al menampilkan )asil ,an( diperole)
terse*ut+
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
4/24
Bentuk Al(oritma
program searching
!input " user memasukan ban#akn#a jumlah n $ dan angka #ang ingin di cariangka pada piranti masukan%!output " menampilkan hasil urutan&n angka #ang di cari user pada pirantikeeluaran'
(amus
const nmin ) 1
nma* ) 1++t#pe arrint ) arra# ,nmin..nma*' of integer
* " integer tabint " arrint n$i " integer indeks " integer function se-search1** " integer/" integer i " integer 0lgoritma " i & 1 hile in/ and tabint,i' **// do i")i41 if tabint,i' ) ** then se-search1&i else se-search1&+ inputn/
for i&1 to n do inputtabint,i'/ input*/ indeks&se-search1*/ if indeks + then output*$5 ditemukan pada indeks ke&5$indeks/ elseoutput*$5 tidak ditemukan5/
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
5/24
Bentuk #as-al Den(an 6a:arus
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
6/24
;asil Runnin( #ro(ram
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
7/24
0L67R8TM0 97RT8:6
Desain dan analisis al(oritma adala) suatu -a*an( k)usus dalam ilmu
komputer ,an( mempela5ari karakteristik dan performa dari suatu al(oritma dalam
men,elesaikan masala). terlepas dari implementasi al(oritma terse*ut+ Dalam
-a*an( disiplin ini al(oritma dipela5ari se-ara a*strak. terlepas dari sistem komputer
atau *a)asa pemro(raman ,an( di(unakan+ Al(oritma ,an( *er*eda dapat
diterapkan pada suatu masala) den(an kriteria ,an( sama+
Kompleksitas dari suatu al(oritma merupakan ukuran se*erapa *an,ak
komputasi ,an( di*utu)kan al(oritma terse*ut untuk men,elesaikan masala)+
Se-ara informal. al(oritma ,an( dapat men,elesaikan suatu permasala)an dalam
meran(kai *enda ,an( se5enis. sekelas. dll. dalam urutan ,an(
teratur+
$+ kate(orisasi> pen(elompokan dan pem*erian la*el kepada *enda den(an
sifat ,an( serupa+
al(oritma sortin( terdiri dari *e*erapa al(oritma seperti Bu**le sort. ?ui-k sort.
Sele-tion Sort. Insertion Sort. dan "er(e Sort ,an( dimana setiap 5enis sortin( ini
memiliki per*edaan satu sama lainn,a+ *erikut ini merupakan pem*a)asan umum
men(enai 5enis75enis atau al(oritma sortin( ,an( tela) di5elaskan diatas >
0. Bubble 9ort
Bu**le Sort merupakan -ara pen(urutan ,an(seder)ana+ Konsep dari ide
dasarn,a adala) seperti1(elem*un( air@ untuk elemen struktur data ,an(semestin,a
*erada pada posisi a
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
8/24
diurutkan+ Di dalam tra8ersal terse*ut.nilai dari dua elemen struktur data
di*andin(kan+ Jikatern,ata urutann,a tidak sesuai den(an [email protected]
dilakukan pertukaran /s
&+ 6akukan tra8ersal untuk mem*andin(kan dua elemen *erdekatan+ Tra8ersal
ini dilakukan dari *elakan(+
$+ Jika elemen pada TN7& TN . maka lakukan pertukaran /s
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
9/24
:otasi 0lgoritma Bubble sort
pro(ram Bu**lesortE
Kamus >
i.n.5 > inte(erE
a> arra, &++&%% of inte(erE
pro-edure *u*leE
:> inte(erE
for I H7 & to n7& do
for 5H7 n do
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
10/24
B. 9election 9ort
Al(oritma sortin( seder)ana ,an( lain adala)Sele-tion Sort+ Ide dasarn,a
adala) melakukan *e*erapa kali pass untuk melakukan pen,eleksianelemen
struktur data+ Untuk sortin( as-endin(/menaik0. elemen ,an( palin( ke-il di antara
elemenelemen,an( *elum urut. disimpan indeksn,a.kemudian dilakukan pertukaran
nilai elemen den(anindeks ,an( disimpan terse*ut den(an elemen ,an(palin(
depan ,an( *elum urut+ Se*alikn,a. untuksortin( des-endin( /menurun0. elemen
,an( palin(+ *esar ,an( disimpan indeksn,a kemudian ditukar+
0lgoritma 9election 9ort
Al(oritma sele-tion sort dapat diran(kum se*a(ai*erikut>
&+ Temukan nilai ,an( palin( minimum /atau sesuaikein(inan0 di dalam struktur
data+ Jika as-endin(. maka ,an( )arus ditemukan adala) nilai ,an( palin(
minimum+ Jika des-endin(. maka temukan nilai ,an( palin( maksimum+
$+ Tukar nilai terse*ut den(an nilai pada posisipertama di *a(ian struktur data
,an( *elum diurutkan+
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
11/24
+ Ulan(i lan(ka) di atas untuk *a(ian struktur data,an( tersisa+
#ro(ram Sele-tionsortDes-endin(E
-onst
maks L M%E
t,pe
6arik L arra,&++maks of inte(erE
Kamus >
n.i.5 > inte(erE
6> larikE
min > inte(erE
temp > inte(erE
Al(oritma >
input/n0E
for I HL & to n do
input/6i0E
for i>L& to n do
output/6i. 0E
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
12/24
For I H7 & to n7& do
"in>LiE
For 5 H7 i to n do
If 65 6min t)en
"in H7 5E
Temp H7 6i
6i H7 6min
6min H7 temp
for i H7 & to n do
output/6i. 0E
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
13/24
;. 8nsertion 9ort
ara ker5a insertion sort se*a(aimana naman,a+#ertama7tama. dilakukan
iterasi. dimana di setiap iterasi insertion sort meminda)kan nilai elemen.kemudian
men,isipkann,a *erulan(7ulan( sampai ketempat ,an( tepat+ Be(itu seterusn,a
dilakukan+ Dariproses iterasi. seperti *iasa. ter*entukla) *a(ian ,an( tela) di7
sortin( dan *a(ian ,an( *elum di7sortin(+
0lgoritma 8nsertion 9ort
Al(oritma Insertion Sort dapat diran(kum se*a(ai *erikut
&+ Simpan nilai Ti kedalam 8aria*el sementara. den(an i L &+
$+ Bandin(kan nilain,a den(an elemen se*elumn,a+Jika elemen se*elumn,a
/Ti7&0 le*i) *esar nilain,a daripada Ti. maka tindi) nilai Ti den(an nilai Ti7&
terse*ut+ De-rement i /kuran(i nilain,a den(an &0+
+ 6akukan terus poin ke7ti(a. sampai Ti7& O Ti+
4+ Jika Ti7& O Ti terpenu)i. tindi) nilai di Ti den(an 8aria*el sementara ,an(
disimpan se*elumn,a+
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
14/24
M+ Ulan(i lan(ka) dari poin & di atas den(an i di7in-rement /ditam*a) satu0+
pro(ram insertionsortE
Kamus >
5mldata.i.5>inte(erE
data>arra, &++&%% of inte(erE
pro-edure as-insertE
temp > inte(erE
*e(in
For iH7 $ to 5mldata do
Temp H7 iE
5 H7 i7&E
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
15/24
input/5mldata0E
for H7 & to 5mldata do
input/datai0E
*a(i
dan atasi0+ ;al ini dikarenakan al(oritma ini melakukan pem*a(ian struktur data
se*elum kemudian dioperasi satu per satu+ Intin,a. al(oritma ini men((unakan dua
ide utama se*a(ai *erikut.
&+ Se*ua) list ,an( ke-il mem*utu)kan lan(ka) ,an( le*i) sedikit untuk
pen(urutan daripada se*ua) list ,an( *esar+
$+ Untuk mem*entuk se*ua) list terurut dari dua*ua) list terurut mem*utu)kan
lan(ka) ,an(l e*i) sedikit daripada mem*entuk se*ua) list terurut dari dua
*ua) list tak terurut+ onto)>)an,a diperlukan satu kali tra8ersal untuk
masin(7masin( list 5ika keduan,a suda)terurut+
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
16/24
0lgoritma Merge 9ort
Al(oritma "er(e Sort seder)anan,a. dapat ditulis *erikut>
&+ Ba(i list ,an( tak terurut men5adi dua sama pan5an( atau sala) satun,a le*i)
pan5an( satu elemen+
$+ Ba(i masin(7masin( dari $ su*7list se-ara rekursif sampai didapatkan list
den(an ukuran &+
+ Ga*un( $ su*list kem*ali men5adi satu list terurut+
=. >uick 9ort
?ui-k Sort adala) al(oritma sortin( ,an( terkenal ,an( diran-an( ole) +A+R+
;oare pada ta)un &P'% ketika *eker5a untuk perusa)aan manufaktur komputer
saintifik ke-il. lliott Brot)ers+ Al(oritma ini rekursif. dan termasuk paradi(ma
al(oritma di8ide and -onuer+
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
17/24
0lgoritma >uick 9ort
Al(oritma ini terdiri dari 4 lan(ka) utama>
&+ Jika struktur data terdiri dari & atau % elemen ,an( )arus diurutkan.
kem*alikan struktur data itu apa adan,a+
$+ Am*il se*ua) elemen ,an( akan di(unakanse*a(ai pi8ot point /poin poros0+
/Biasan,a elemen ,an( palin( kiri+0
+ Ba(i struktur data men5adi dua *a(ian Q satu den(an elemen7elemen ,an(
le*i) *esar daripada pi8ot point. dan ,an( lainn,a den(an elemen7elemen
,an( le*i) ke-il dari pada pi8ot point+
4+ Ulan(i al(oritma se-ara rekursif ter)adap kedua paru) struktur data+
Bentuk Pascal 0lgoritma Metode Bubble 9ort
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
18/24
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
19/24
Tampilan
Bentuk Pascal 0lgoritma Metode 8nsertion 9ort
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
20/24
Tampilan
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
21/24
Bentuk Pascal 0lgoritma Metode 9election 9ort
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
22/24
Tampilan
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
23/24
(=98MP?L0:
-
8/18/2019 TUGAS BAB 4 Bagus Haruman - MS Rabbani
24/24
Al(oritma ,an( muda) dalam )al implementasi adala) Bu**le Sort. Sele-tion
Sort. dan Insertion Sort+ Keti(an,a memiliki kompleksitas !/n$0+ Di antara al(oritma
ini. ,an( palin( effisien adala) Insertion Sort+ Al(oritma ,an( le*i) man(kus adala)
"er(eSort dan ?ui-k Sort den(an kompleksitasn,a adala) !/n lo( n0+ Adapun ,an(
palin( man(kus dari lima al(oritma ini adala) ?ui-k Sort+