11 12 -pengurutan dan-pencarian

STRUKTUR DATASTRUKTUR DATA

Mempelajari bagaimana mengatur sekumpulan

data berdasar pada pengurutan dan pencarian

Tujuan:


Pengurutan adalah upaya mengatur

sekumpulan data berdasar pada urutan

(naik atau turun)

Pencarian adalah upaya mencari/mendapatkan satu atau lebih objek

dari sekumpulan data


SortingSorting

�� Pengurutan data dalam struktur data sangat Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik penting untuk data yang beripe data numerik ataupun karakter.ataupun karakter.

�� Pengurutan dapat dilakukan secara ascending Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)(urut naik) dan descending (urut turun)

�� Pengurutan (Sorting) adalah proses menyusun Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.secara teratur menurut aturan tertentu.

�� Contoh:Contoh:

�� Data AcakData Acak : 5 6 8 1 3 25 10: 5 6 8 1 3 25 10

�� AscendingAscending : 1 3 5 6 8 10 25: 1 3 5 6 8 10 25

�� DescendingDescending : 25 10 8 6 5 3 1: 25 10 8 6 5 3 1


6 (enam) metode pengurutan yang akan dipaparkan

� Penyisipan Langsung (Straight Insertion Sort)

� Penyisipan Biner (Binary Insertion Sort)

� Seleksi (Selection Sort)

� Gelembung (Bubble Sort)

� Shell (Shell Sort)

� Quick (Quick Sort)


2 (dua) metode pencarian yang akan dipaparkan

Pencarian

Sekuensial

(Sequential Search)

Pencarian

Biner

(Binary

Search)


Pengurutan dilakukan agar data dapat dilihat dengan mudah.

Algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu, berdasarkan satu atau beberapa kunci dalam tiap––––tiap

elemen

2 (dua) model urutan yaitu model urut naik (increase sort) dan urut turun (decrease sort).

Contoh: Data 5,2,4,6.

Diurut naik menjadi 2,4,5,6 Diurut turun menjadi 6,5,4,2.

(Mengapa perlu pengurutan?)


Bubble SortBubble Sort

�� MetodeMetode sorting sorting termudahtermudah

�� DiberiDiberi namanama ““BubbleBubble”” karenakarena prosesproses pengurutanpengurutan

secarasecara berangsurberangsur--angsurangsur bergerak/berpindahbergerak/berpindah keke

posisinyaposisinya yang yang tepattepat, , sepertiseperti gelembunggelembung yang yang

keluarkeluar daridari sebuahsebuah gelasgelas bersodabersoda..

�� Bubble Sort mengurutkan data dengan cara Bubble Sort mengurutkan data dengan cara

membandingkan elemen sekarang dengan membandingkan elemen sekarang dengan

elemen berikutnya.elemen berikutnya.


Bubble Sort (2)Bubble Sort (2)�� PengurutanPengurutan Ascending :Ascending :JikaJika elemenelemen sekarangsekarang lebihlebih

besarbesar daridari elemenelemen berikutnyaberikutnya makamaka keduakedua elemenelementersebuttersebut ditukarditukar..

�� PengurutanPengurutan Descending: Descending: JikaJika elemenelemen sekarangsekarang lebihlebihkecilkecil daridari elemenelemen berikutnyaberikutnya, , makamaka keduakedua elemenelementersebuttersebut ditukarditukar..

�� AlgoritmaAlgoritma iniini seolahseolah--olaholah menggesermenggeser satusatu per per satusatuelemenelemen daridari kanankanan keke kirikiri atauatau kirikiri keke kanankanan, , tergantungtergantung jenisjenis pengurutannyapengurutannya..

�� KetikaKetika satusatu prosesproses telahtelah selesaiselesai, , makamaka bubble sort bubble sort akanakan mengulangimengulangi prosesproses, , demikiandemikian seterusnyaseterusnya daridari 0 0 sampaisampai dengandengan iterasiiterasi sebanyaksebanyak nn--1.1.

�� KapanKapan berhentinyaberhentinya?? Bubble sort Bubble sort berhentiberhenti jikajika seluruhseluruharray array telahtelah diperiksadiperiksa dandan tidaktidak adaada pertukaranpertukaran lagilagiyang yang bisabisa dilakukandilakukan, , sertaserta tercapaitercapai perurutanperurutan yang yang telahtelah diinginkandiinginkan. .


Bubble Sort (3)Bubble Sort (3)



�� DenganDengan prosedurprosedur diatasdiatas, data , data terurutterurut naiknaik

(ascending), (ascending), untukuntuk uruturut turunturun (descending) (descending)

silahkansilahkan ubahubah bagianbagian: :

if (if (data[jdata[j]<data[j]<data[j--1]) tukar(&data[j],&data[j1]) tukar(&data[j],&data[j--1]);1]);

MenjadiMenjadi: :

if (if (data[jdata[j]>data[j]>data[j--1]) tukar(&data[j],&data[j1]) tukar(&data[j],&data[j--1]);1]);

�� ““The bubble sort is an easy algorithm to program, The bubble sort is an easy algorithm to program,

but it is slower than many other sortsbut it is slower than many other sorts””


Selection SortSelection Sort

�� MerupakanMerupakan kombinasikombinasi antaraantara sorting sorting dandan searchingsearching

�� UntukUntuk setiapsetiap prosesproses, , akanakan dicaridicari elemenelemen--elemenelemen yang yang belumbelum diurutkandiurutkan yang yang memilikimemiliki nilainilai terkecilterkecil atauatau terbesarterbesarakanakan dipertukarkandipertukarkan keke posisiposisi yang yang tepattepat didi dalamdalam array.array.

�� MisalnyaMisalnya untukuntuk putaranputaran pertamapertama, , akanakan dicaridicari data data dengandengannilainilai terkecilterkecil dandan data data iniini akanakan ditempatkanditempatkan didi indeksindeksterkecilterkecil (data[0]), (data[0]), padapada putaranputaran keduakedua akanakan dicaridicari data data keduakedua terkecilterkecil, , dandan akanakan ditempatkanditempatkan didi indeksindeks keduakedua(data[1]).(data[1]).

�� SelamaSelama prosesproses, , pembandinganpembandingan dandan pengubahanpengubahan hanyahanyadilakukandilakukan padapada indeksindeks pembandingpembanding sajasaja, , pertukaranpertukaran data data secarasecara fisikfisik terjaditerjadi padapada akhirakhir prosesproses..


Selection Sort (2)Selection Sort (2)


Insertion SortInsertion Sort

�� Mirip dengan cara orang Mirip dengan cara orang mengurutkanmengurutkan kartu, kartu,

selembar demi selembar kartu diambil dan selembar demi selembar kartu diambil dan

disisipkandisisipkan (insert) ke tempat yang seharusnya.(insert) ke tempat yang seharusnya.

�� Pengurutan dimulai dari data kePengurutan dimulai dari data ke--2 sampai dengan 2 sampai dengan

data terakhir, jika ditemukan data yang data terakhir, jika ditemukan data yang lebih lebih

kecilkecil, maka akan ditempatkan (, maka akan ditempatkan (diinsertdiinsert) diposisi ) diposisi

yang seharusnya.yang seharusnya.

�� Pada penyisipan elemen, maka elemenPada penyisipan elemen, maka elemen--elemen elemen

lain akan bergeser ke belakanglain akan bergeser ke belakang


Insertion Sort (2)Insertion Sort (2)


Insertion Sort (3)Insertion Sort (3)


PerbandinganPerbandingan

�� TabelTabel PerbandinganPerbandingan KecepatanKecepatan MetodeMetode

PengurutanPengurutan Data Data

�� UntukUntuk data data sejumlahsejumlah 10.000 data 10.000 data padapada

komputerkomputer Pentium II 450 MHz Pentium II 450 MHz


SoalSoal

CarilahCarilah 3 3 metodemetode sorting sorting lainnyalainnya dandan

tuliskantuliskan dalamdalam paper paper besertabeserta source code, source code,

caracara dandan analisisanalisis dandan tiaptiap--tiaptiap metodemetode

sorting yang sorting yang adaada!!


Begin

Writeln('Masukan bilangan n yang anda inginkan');

Readln (x);

n_faktorial := Factorial(x);

Writeln (x, '! adalah ', n_faktorial);

End.

Program Rekursi1_Faktorial;

uses crt, dos;

Var n_faktorial,x : longint;

Function faktorial (n: longint) : longint;

Begin

if (n = 0) or (n = 1) then

faktorial := 1

else

faktorial := n * faktorial ( n - 1);

End;

Implementasi AlgoritmaImplementasi AlgoritmaImplementasi AlgoritmaImplementasi Algoritma Rekursi1_Faktorial Rekursi1_Faktorial Rekursi1_Faktorial Rekursi1_Faktorial

dalam pascaldalam pascaldalam pascaldalam pascal


Contoh : Permutasi untuk n = 2 adalah :

A B

B A

Contoh Pemakaian Rekursi (Permutasi).

Untuk menampilkan semua permutasi dari N karakter ’A’, ’B’, ’C’, dan seterusnya, diperlukan rekursi karena proses permutasi akan

menampilkan karakter yang sama secara berulang.

Contoh : Permutasi untuk n = 3 adalah :

AAAA BBBB CCCC

AAAA CCCC BBBB

BBBB AAAA CCCC

BBBB CCCC AAAA

CCCC AAAA BBBB

CCCC BBBB AAAA


Procedure DoPermutasi (Input/Output A: TPermutasi ;

mulai :byte)

{prosedur untuk mengerjakan hitungan permutasi untuk n objek}{K.Awal : sebuah nilai n diberikan untuk menyatakan banyaknya objek}{K.Akhir: Susunan huruf alphabet sebagai permutasi dari n objek dan

dicetak ke piranti keluaran}

DEKLARASIi : byte;

Temp : char;

Prosedur DoPermutasi


DESKRIPSI:

If ( mulai = N ) then

For i �� 1 to N do

write ( A [ i ] )

Endfor

Else

For i �� mulai to N do

temp �� A [ i ]

A [ i ] �� A [ mulai ]

A [ mulai ] �� temp

DoPermutasi (A, mulai +1)

Endfor

Endelse

Endif


Contoh :Algoritma Permutasi yang memanggil prosedur bernama DoPermutasi.

DEKLARASI

Const Max = 10Type TPermutasi = array [ 1..10 ] of char

Procedure DoPermutasi (Input/Output A: TPermutasi ;

mulai :byte){prosedur dengan parameter formal input/output}

Algoritma Permutasi{Algoritma program utama menentukan permutasi dari n obejk}

{K.Awal : nilai n yang menyatakan banyak objek berupa huruf aplhabet

sudah terdefinisi}

{K.Akhir: susunan permutasi yang mungkin dari n objek berupa huruf

alphabet dan dicetak ke piranti keluaran}


DESKRIPSI:

If ( mulai = N ) thenfor i ← 1 to N do

write ( A [ i ] )endfor

elsefor i ← mulai to N do

temp ← A [ i ]A [ i ] ← A [ mulai ]A [ mulai ] ← tempDoPermutasi (A, mulai +1)

endforendif

11 12 -pengurutan dan-pencarian

Documents