RANGKUMAN PRAKTIKUM ALGORITMA DAN STRUKTUR DATA
Rangkuman Praktikum Algoritma dan Pemrograman Modul 1-6
Disusun Oleh :
Nama : Devia Rahma Aprillia Permatasari
NIM : 211080200145
Kelompok : 6
Assalamu'alaikum Wr.Wb.
Materi yang saya lampirkan merupakan hasil rangkuman dari materi praktikum Algoritma dan Pemrogaman satu semester ini dan menjadi salah satu syarat untuk memenuhi tugas Praktikum Algoritma dan Pemrograman. Saya merupakan Mahasiswi Universitas Muhammadiyah Sidoarjo Program Studi Informatika. Jika ingin lebih tahu tentang Universitas Muhammadiyah Sidoarjo bisa langsung mengakses link umsida.ac.id atau fst.umsida.ac.id
POKOK BAHASAN 1
STRUKTUR DATA, ARRAY, POINTER, DAN STRUKTUR
Pada pokok bahasan ini berisi penjelasan disertai contoh mengenai konsep
struktur data, array, pointer, dan struktur yang menjadi pemahaman dasar bagi
mahasiswa sebelum mempelajari struktur data, dimana konsep array, pointer, dan
struktur digunakan untuk mempresentasikan sebuah struktur data, diharapkan
mahasiswa dapat:
a.
Mengetahui konsep dasar struktur data.
b. Memahami konsep array, pointer, dan struktur.
A.
Konsep Dasar Struktur Data
Struktur Data adalah sebuah bagian dari ilmu
pemrograman dasar yang mempunyai karakteristik yang terkait dengan sifat dan
cara penyimpanan sekaligus penggunaan atau pengaksesan data.
Struktur data bertujuan agar cara mempresentasikan data dalam membuat program dapat dilakukan secara efisien dalam pengolahan di memori dan pengolahan penyimpanan dari program ke storage juga lebih mudah dilakukan.
B.
Konsep Dasar Array
Array adalah kumpulan elemen-elemen data. Kumpulan
elemen tersebut mempunyai susunan tertentu yang teratur. Jumlah elemen
terbatas, dan semua elemen mempunyai tipe data yang sama. Jenis-jenis array:
·
Array Satu Dimensi
Struktur array satu dimensi dapat dideklarasikan dengan bentuk umum berupa: tipe_var nama_var [ukuran];
Dengan :
-
Tipe_var : untuk menyatakan jenis elemen array(misalnya inti, char,
unsigned).
-
Nama_var : untuk menyatakan nama variabel yang dipakai.
-
Ukuran : untuk menyatakan jumlah maksimal elemen array.
Contoh : float nilai_ujian [5]
·
Array Dua Dimensi
Tipe data array dua dimensi biasa
digunakan untuk menyimpan, mengolah maupun menampilkan satu data dalam bentuk
tabel atau matriks. Untuk mendeklarasikan array agar dapat menyimpan data
adalah:
tipe_var nama_var [ukuran1] [ukuran2];
Dimana :
-
Ukuran 1 menunjukkan jumlah/nomor baris.
-
Ukuran 2 menunjukkan jumlah/nomor kolom.
Jumlah elemen yang dimiliki array dua dimensi dapat ditentukan dari hasil
perkalian :
ukuran 1 x ukuran 2.
Seperti halnya pada array satu
dimensi, data array dua dimensi akan ditempatkan pada memori secara berurutan.
·
Array Multidimensi / Dimensi Banyak
Array berdimensi banyak atau multidimensi terdiri dari array yang tidak
terbatas hanya dua dimensi saja. Bentuk umum pendeklarasian array multidimensi
adalah:
tipe_var nama_var [ukuran1]
[ukuran2]...[ukuran n];
Contoh : inti data_angaka [3][6][6];
Yang merupakan array tiga dimensi
Mengakses
Elemen Array :
Dalam bahasa C++, data array akan disimpan dalam memori pada alokasi yang
berurutan.
Elemen
pertama biasanya mempunyai indeks bernilai 0. Contoh :
Float
nilai_tes[5];
Jika pada contoh di atas, variabel nilai_tes mempunyai 5 elemen, maka
elemen pertama mempunyai indeks sama dengan 0, elemen kedua mempunyai indeks 1,
dan seterusnya. Bentuk umum pengaksesan satu elemen variabel array adalah :
Nama_var[indeks];
Gambar berikut memperlihatkan urutan komponen array dalam memori. Untuk variabel array nilai_tes:
Inisialisasi
Array :
Array dapat diinisialisasikan secara langsung saat pertama kali
dideklarasikan (efisien untuk array berdimensi sedikit)
Contoh :
inti x[2]={1,2};
Array
dapat dideklarasikan terlebih dahulu, baru kemudian diisi elemennya. Contoh :
Int
x[2];
X[0];
X[1];
C. Konsep Dasar Pointer
Pointer adalah sebuah variabel yang berisi alamat variabel yang lain.
Suatu pointer dimaksudkan untuk menunjuk ke satu alamat memori sehingga alamat
dari satu variabel dapat diketahui dengan mudah. Deklarasi pointer
Operator pointer:
Operator ‘&’ : Untuk mendapatkan alamat memori operand / variabel pointer.
Operator ‘*’ : Untuk mengakses nilai data opeand / variabel pointer.
D. Konsep Dasar Struktur
Struktur adalah koleksi dari variabel yang dinyatakan dengan sebuah nama,
dengan sifat setiap variabel dapat memiliki tipe yang berlainan. Struktur biasa
dipakai untuk mengelompokkan beberapa informasi yang berkaitan menjadi sebuah
satu kesatuan. Contoh sebuah struktur adalah informasi data tanggal, yang
berisi tanggal, bulan, dan tahun.
Mendeklarasikan Struktur :
Contoh pendefinisian tipe data struktur adalah :
Struct data_tanggal
{int tanggal};
Masing-masing tipe dari elemen
struktur dapat berlainan. Adapun variabel_struktur1 sampai dengan
variabel_struktur M menyatakan bahwa variabel struktur yang dideklarasikan bisa
lebih dari satu. Jika ada lebih dari satu variabel, antara variabel struktur
dipisahkan dengan tanda koma.
Mengakses Elemen Struktur :
Elemen dari struktur dapat diakses dengan menggunakan bentuk :
variabel_struktur.nama_field
Antara variabel_struktur dan
nama_field dipisahkan dengan operator titik (disebut operator anggota
struktur). Contoh berikut merupakan instruksi untuk mengisikan data pada field
tanggal:
tgl_lahir.tanggal=30
int bulan;
int tahun;
};
Yang mendefinisikan tipe struktur
bernama data_tanggal, yang terdiri dari tiga buah elemen berupa tanggal, bulan,
dan tahun. Bentuk umum dalam mendefinisikan dan mendeklarasikan struktur adalah
:
Struct nama_tipe_struktur {
Tipe
field1;
Tipe
field2;
Tipe
field3;
}variabel_struktur1......variabel_strukturM;
POKOK BAHASAN 2
LINKED LIST (SENARAI)
Pada pokok bahasan ini akan dibahas mengenai struktur data senarai (list)
yang pembahasannya meliputi definisi dan representasi list, jenis-jenis list,
serta operasi-operasi dasar pada list. Sehingga setelah mempelajari bab ini
diharapkan mahasiswa mampu :
a. Menjelaskan definisi dan
representasi list.
b. Mengetahui jenis-jenis list.
c.
Memahami operasi-operasi pada list.
Linked List adalah objek atau elemen yang dihubungkan satu dengan lainnya
sehingga membentuk satu list. Sedangkan objek atau elemen itu sendiri adalah
merupakan gabungan beberapa data (variabel) yang dijadikan satu kelompok atau structure
atau record yang dibentuk segan perintah struct. Untuk
menggabungkan objek satu dengan lainnya, diperlukan paling tidak sebuah
variabel yang bertipe pointer. Syarat linked list adalah harus dapat
diketahui alamat simpul pertama atau biasa dipakai variabel First/Start/Header.
Struktur dasar sebuah list seperti gambar berikut :
Istilah-istilah
dalam Linked List:
-
Simpul
Simpul terdiri
dari dua bagian yaitu :
a. Bagian data.
b. Bagian pointer yang menunjuk ke simpul berikutnya.
-
First/Header
Variabel
First/Header beri alamat (pointer)/ acuan (reference) yang menunjuk lokasi
simpul pertama Linked List, digunakan sebagai awal penelusuran Linked
List.
-
Nill/Null
Tidak bernilai,
digunakan untuk menyatakan tidak mengacu ke mana pun.
-
Simpul Terakhir (Last)
Simpul terakhir
linked list berarti tidak menunjuk simpul berikutnya. Tidak terdapat alamat
disimpan di field pointer (bagian kedua dari simpul). Nilai null atau
nil disimpan di field pointer di simpul terakhir.
Jenis-jenis
linked list :
·
List Kosong
List Kosong hanya terdiri dari sebuah petunjuk elemen yang
berisi NULL (kosong), tidak memiliki satu buah elemen pun sehingga hanya berupa
petunjuk awal elemen berisi NULL.
·
List Tunggal
List Tunggal adalah lis yang elemennya hanya menyimpan
informasi elemen setelahnya (next), sehingga jalannya pengaksesan list hanya
dapat dilakukan secara maju. List tunggal terbagi tiga jenis yaitu lis tunggal
dengan kepala (First), list tunggal dengan kepala (First) dan ekor (Tail),
serta lis tunggal yang berputar.
·
List Ganda
List Ganda adalah sebuah list yang elemennya menyimpan
informasi elemen sebelumnya dan informasi elemen setelahnya, sehingga proses
penelusuran list dapat dilakukan secara maju dan mundur. List ganda terbagi
menjadi tiga jenis yaitu List ganda dengan kepala(First), list ganda dengan
kepala(First) dan ekor(Tail), serta list ganda yang berputar.
Operasi Dasar Pada
Linked List :
·
IsEmpty : Fungsi ini menentukan apakah Linked List kosong atau
tidak.
·
Size : Operasi untuk mengirim jumlah elemen di Linked List.
·
Create : Operasi untuk penciptaan List baru yang kosong.
·
Insertfirst : Operasi untuk penyisipan simpul sebagai simpul pertama.
·
Insertlast : Operasi untuk penyisipan simpul sebagai simpul terakhir.
·
Insertbefore : Operasi untuk penyisipan simpul sebelum simpul tertentu.
·
Deletefirst : Operasi penghapusan simpul pertama.
·
Deleteafter : Operasi untuk penghapusan setelah simpul tertentu.
·
Deletelast : Operasi penghapusan simpul terakhir.
POKOK BAHASAN 3
STACK (TUMPUKAN)
Pada pokok bahasan ini akan dibahas mengenai struktur
data tumpukan atau stack, dimana stack merupakan suatu kumpulan data yang seolah-olah
ada data yang diletakkan di atas data yang lain. Setelah mempelajari materi ini
diharapkan mahasiswa mampu untuk :
a.
Mengetahui dan memahami definisi stack.
b.
Memahami operasi-operasi dasar stack.
c.
Memahami representasi statis dan dinamis stack.
Stack adalah kumpulan
elemen-elemen yang tersimpan dalam suatu tumpukan. Aturan penyisipan dan
penghapusan elemennya tertentu:
-
Penyisipan selalu dilakukan “di atas” TOP
-
Penghapusan selalu
dilakukan pada TOP
Karena aturan penyisipan dan penghapus semacam itu,
TOP adalah satu-satunya alamat tempat terjadi operasi, elemen yang ditambahkan
paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen
stack tersusun secara LIFO (Last In First Out).
Seperti halnya jika kita mempunyai sebuah tumpukan
buku, agar tumpukan buku itu tidak ambruk ketika kita mengambil sebuah buku di
dalam tumpukan itu maka harus di ambil satu per satu dari tumpukan yang paling
atas dari tumpukan.
Perhatikan bahwa dengan definisi semacam ini,
representasi tabel sangat tepat untuk mewakili stack, karena operasi penambahan
dan pengurangan hanya dilakukan disalah satu ujung tabel.
Beberapa contoh penggunaan stack adalah pemanggilan
prosedur, perhitungan ekspresi aritmetika, rekursifitas, backtracking,
penanganan interupsi, dan lain-lain.
Karakteristik penting stack sebagai berikut:
1.
Elemen stack yaitu item-item data di elemen stack
2.
TOP (elemen puncak dari stack)
3.
Jumlah elemen pada stack
4.
Status/kondisi stack,
yaitu:
-
Penuh
Bila elemen di tumpukan
mencapai kapasitas maksimum tumpukan. Pada kondisi ini, tidak mungkin dilakukan
penambahan ketumpukan. Penambahan di elemen menyebabkan kondisi kesalahan Overflow
-
Kosong
Bila tidak ada elemen
tumpukan. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen
tumpukan. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.
Stack memiliki operasi-operasi pokok sebagai berikut :
·
Push : Untuk
menambahkan item pada tumpulkan paling atas.
Void Push (item Type x, Stack *S) {
If (Full (S))
Printf(“Stack
FULL);
Else {
S->Item[S->Count]=x;
++(S->count);
}
}
·
POP : Untuk
mengambil item teratas
Int Pop
(stack S, itemType x) {
If(Empty (S))
Printf(“Stack Kosong “);
else {
--(S->Count);
X=s->item(s->Count);
}
}
·
Clear : Untuk
mengosongkan stack
Void initializeStack (Stack S) {
S->Count=0;
}
·
IsEmpty :Untuk
memeriksa apakah stack kosong
Int
Empty (Stack*S) {
Return (S->Count==0);
}
·
IsFull :Untuk
memeriksa apakah stack sudah penuh
Int Full
(Stack S) {
Return (S->Count==MAXSTACK);
}
Representasi Stack:
-
Representasi statis
Stack dengan representasi statis biasanya diimplementasikan
dengan menggunakan array. Sebuah array memiliki tempat yang dialokasikan diawal
sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat
yang ada pada array. Karena menggunakan array maka stack dengan representasi
statis dalam mengalami kondisi elemen penuh. Ilustrasi stack dengan
representasi statis dapat dilihat pada gambar 3.2 :
-
Representasi dinamis
Stack dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori. Ilustrasi stack dengan representasi dinamis dapat dilihat pada gambar 3.3 :
Karena semua operasi pada sebuah stack diawali dengan elemen yang paling atas maka jika menggunakan representasi dinamis saat elemen ditambahkan akan menggunakan penambahan elemen pada awal stack (addfirst) dan saat pengambilan atau penghapus elemen menggunakan penghapus di awal stack (delfirst).
POKOK BAHASAN 4
QUEUE (ANTRIAN)
Pada pokok
bahasan ini akan di bahas maengenai antrian atau queue, dimana struktur data
ini hamper sama dengan tumpukan atau stack yang merupakan struktur data yang
linier. Perbedaannya adalah pada operasi penambahan dan pengurangan pada ujung
yang berbeda. Setelah mempelajari materi ini diharapkan mahasiswa mampu:
a.
Mengetahui dan
memahami definisi antian.
b.
Memahami operasi-operasi
dasar pada antrian.
c.
Memahami representasi
statis dan dinamis pada antrian.
PENYAJIAN (TUTORIAL)
Antrian adalah
salah satu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada
suatu ujung (disebut sisi belakang atau REAR), dan penghapusan atau pengambilan
elemen dilakukan lewat ujung yang lain (disebut sisi depan atau FRONT). Prinsip
yang digunakan dalam antrian ini adalah
FIFO (First In First Out) yaitu elemen yang pertama kali masuk akan
keluar pertama kalinya.
Penggunaan
antrian antara lain simulasi antrian di dunia nyata (antrian pembelian tiket),
sistem jaringan komputer (pemrosesan banyak paket yang datang dari banyak
koneksi pada suatu host, bridge, gateway), dan lain-lain.
Gambar 4.1 Ilustrasi Antrian dengan 8 elemen
Elemen Karakteristik penting antrian sebagai berikut:
a.
Elemen antrian yaitu
item-item data terdapat dalam antrian.
b.
Head/front (elemen terdepan antrian).
c.
Tail/rear (elemen terakhir antrian).
d.
Jumlah antrian pada
antrian (count).
e.
Status/kondisi
antrian, ada dua yaitu:
-
Penuh
Bila
elemen pada antrian mencapai kapasitas maksimum antrian. Pada kondisi ini,
tidak mungkin dilakukan penambahan ke antrian. Penambahan di elemen menyebabkan
kondisi kesalahan Overflow.
-Kosong
Bila
tidak ada elemen antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan
elemen antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.
Operasi-operasi
pokok pada antrian diantaranya adalah:
1.
Create → Membuat
antrian baru.
NOEL(CREATE(Q))
= 0
FRONT(CREATE(Q)) = tidak terdefinisi
REAR(CREATE(Q)) = tidak terdefinisi
2.
IsEmpety → Untuk
memeriksa apakah Antrian sudah penuh atau belum.
ISEMPETY(Q)
= True, jika Q adalah queue kosong.
3.
IsFull→mengecek apakah
Antrian sudah penuh atau belum.
ISFULL(Q)
= True, jika Q adalah queue penuh.
4.
Enqueue/Insert →
menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di
elemen paling belakang.
REAR(INSERT(A,Q))
=A
ISEMPETY
(INSERT(A,Q)) = FALSE
Algoritma
QINSERT :
a.
IF FRONT = 1 AND REAR
= N, OR IF FRONT = REAR + 1, THEN OVERFLOW, RETUN
b.
IF FRONT := NULL, THEN
SET
FRONT := 1 AND REAR := 1
ELSE
IF REAR = N, THEN
SET REAR := 1
ELSE
SET REAR := REAR+1
c.
SET QUEUE[REAR] :=
ITEM
d.
RETURN
5.
Dequeue/Remove → untuk
menghapus elemen terdepan/pertama dari Antrian
Algoritma
QDELETE:
a.
IF FRONT := NULL, THEN
UNDERFLOW, RETURN
b.
SET ITEM :=
QUEUE[FRONT]
c.
[FIND NEW VALUE OF
FRONT]
IF FRONT = REAR, THEN
SET FRONT = REAR, THEN SET FRONT := NULL AND
REAR : NULL
ELSE
IF FRONT = N, THEN
SET FRONT =1
ELSE
SET FRONT := FRONT+1
d.
RETURN
Representasi queue :
· Representasi statis
Queue dengan representasi statis biasasnya diimplementasikan dengan menngunakan array. Sebuah array memiliki tempat yang di alokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka queue dengan representasi statis dalam mengalami kondisi elemen penuh. Ilustrasi queue dengan representasi statis dapat dilihat pada gambar:
· Representasi dinamis
Queue dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen –elemen yang dialokasikan pada memori. Ilustrasi queue representasi dinamis dapat dilihat pada gambar :
POKOK BAHASAN 5
REKURSIF
PENDAHULUAN
Pada pokok
bahasan ini akan dibahas mengenai rekursif. Setelah mempelajari bab ini
diharapkan mahasiswa mampu:
a.
Mengetahui dan
memahami defenisi rekursif.
b.
Memahami sifat-sifat
rekursif.
c.
Mengaplikasikan
rekursif.
PENYAJIAN
(TUTORIAL)
Fungsi rekursif
adalah suatu fungsi yang memanggil dirinya sendiri, artinya fungsi tersebut
dipanggil di dalam tubuh fungsi itu sendiri. Contoh menghitung nilai faktorial.
Rekursif sangat memudahkan untuk memecahkan permasalahan yang kompleks.
Sifat-sifat rekursif:
·
Dapat digunakan ketika
inti dari masalah terjadi berulang kali.
·
Sedikit lebih efisien
dari iterasi tapi lebih elegan.
·
Method-methodnya
dimungkinkan untuk memanggil dirinya sendiri.
Data yang berada dalam method tersebut seperti argument disimpan sementara ke dalam stack sampai method pemanggilnya diselesaikan.
POKOK
BAHASAN 6
SORTING (PENGURUTAN)
Setelah
mempelajari bab ini diharapkan mahasiswa mampu:
a.
Menunjukkan beberapa
algoritma dalam pengurutan.
b.
Menunjukkan bahwa
pengurutan merupakan suatu persoalan yang bisa diselesaikan dengan sejumlah
algoritma yang berbeda satu sama lain.
c.
Dapat memilih
algoritma yang paling sesuai untuk menyelesaikan suatu permasalahan
pemrograman.
PENYAJIAN (TUTORIAL)
Pengurutan
data (sorting) didefinisikan sebagai
suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu.
Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu:
v Urutan naik (ascending) yaitu dari data yang
mempunyai nilai paling kecil sampai paling besar.
v Urutan turun (descending) yaitu dari data yang
mempunyai nilai paling besar sampai paling kecil.
Contoh : data bilangan 5, 2, 6,
dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan turun menjadi 6,
5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau
lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence)
seperti dinyatakan dalam tabel ASCII. Keuntungan dari data yang sudah dalam
keadaan terurut yaitu :
ü Data mudah dicari, mudah untuk dibetulkan, dihapus, disisipi
atau digabungkan. Dalam keadaan terurutkan, kita mudah melakukan pengecekan
apakah ada data yang hilang. Misalnya kamus bahasa, buku telepon.
ü Mempercepat proses pencarian data yang harus dilakukan
berulang kali.
Beberapa faktor yang berpengaruh
pada efektifitas suatu algoritma pengurutan antara lain:
ü Banyak data yang diurutkan.
ü Kapasitas pengingat apakah mampu menyimpan semua data yang
kita miliki.
ü Tempat penyimpanan data, misalnya piringan ,pita atau kartu,
dll.
Beberapa
algoritma metode pengurutan dan prosedurnya sebagai berikut :
1.
Bubble sort
Bubble
sort adalah suatu metode pengurutan yang
membandingkan elemen yang sekarang dengan elemen berikutnya. Apabila elemen
sekarang > elemen berikutnya, maka posisinya ditukar. Kalau tidak, tidak
perlu ditukar. Diberi nama “Bubble” karena proses pengurutan secara
berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung
yang keluar dari sebuah gelas bersoda.
Proses Bubble Sort :
Data paling akhir
dibandingkan dengan data di depannya, jika ternyata lebih kecil atau besar maka
tukar sesuai dengan ketentuan (descending atau ascending). Dan pengecekan yang
sama dilakukan terhadap data yang selanjutnya sampai dengan data yang paling
awal.
Algoritma
bubble sort:
1.i=0
2.selama
(i<N-1)kerjakan baris 3 sampai 7
3.j=N-1
Algoritma
Bubble Sort :
1.i = 0
2.selama
(i<N-1) kerjakan baris 3 sampai 7
3.j = N-1
4.selama (j>=i)kerjakan
baris 5 sampai 7
5.jika (data
[j-1]>data[j]maka tukar data[j-1]dengan data[j]
6.j= j-1
7.i = i+1
Prosedur yang
menggunakan metode gelembung :
Void bubblesort()
{
Int i,j;
For(i=1;i<max-1;i++)
For(j=max-1;j>=i;j--)
If(data[j-1]>data[j])
Tukar(&data[j-1],&data[j]);
}
2.
Selection Sort
Metode seleksi
melakukan pengurutan dengan cara mencari dta yang terkecil kemudian menukarnya
dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Selama proses,
pembandingan dan pengubahan hanya dilakukan pada indeks pembanding
saja,pertukaran data secara fisik terjadi pada akhir proses.proses pengurutan
dengan metode seleksi dapat dijelaskan sebagai berikut:
·
Langkah pertama dicari
data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil
ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai
nilai paling kecil dibanding data yang lain.
·
Langkah kedua, data
terkecil kita cari mulai data kedua sampai terakhir.data terkecil yang kita
peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen
dalam keadaan terurutkan.
Algoritma
seleksi dapat dituliskan sebagai berikut:
1.i=0
2.selama(i<N-1)kerjakan
baris 3 sampai dengan 9
3.k=i
4.j=i+1
5.selama
(j<N)kerjakan baris 6 dan 7
6.jika
(data[k]>data[j]maka k=j
7.j=j+1
8.tukar data
[i] dengan data[k]
9.i=i+1
Dibawah ini
merupakan prosedur yang menggunakan metode seleksi:
Void selectionsort()
{
Int i,j,k;
For(i=0;
i<Max-1;i++)
{
K=i;
For(j=i+1;j<max;j++)
If(data[k]>data[j])
K=j;
Tukar(&data[i],&data[k]);
}
}
3. Merger Sort
Algoritma
Merge Sort ialah algoritma pengurutan yang
berdasarkan pada strategi divide and conquer. Algoritma ini terdiri dari dua
bagian utama, pembagian list yang diberikan untuk di-sort ke dalam
beberapa sublist yang lebih kecil,dan sort (mengurutkan) dan merge (menggabungkan) sublist-sublist
yang lebih kecil ke dalam list hasil yang sudah diurutkan. Pembagian bisa
dikatakan cukup mudah karena sublist-sublist tersebut dibagi ke dalam dua
sublist yang ukurannya adalah setengah dari ukuran semula. Hal ini terus
diulang sampai sublist itu cukup kecil untuk di-sort secara efisien
(umumnya telah terdiri dari satu atau dua elemen). Dalam langkah merge dua sublist
disatukan kembali dan diurutkan pada saat yang sama. Algoritma untuk merge
sort ialah sebagai berikut :
A. Untuk kasus n=1,maka table a sudah terurut sendiirinya
(langkah solve)
B. Untuk kasus n>1,maka:
a. DEVIDE : bagi table
a menjadi dua bagian,bagian kiri dan bagian kanan, masing-masing bagian
berukuran n/2 elemen.
b. CONQUER : secara
rekursif,terapkan algoritma D-dan-C pada masing-masing bagian.
c.MERGE:gabung hasil pengurutan
kedua bagian sehingga diperoleh table a yang terurut.
Semoga rangkuman ini bisa bermanfaat bagi penulis dan pembaca. Terimakasih.
Wassalamu'alaikum Wr. Wb
Comments
Post a Comment