ALGORITMA DAN STRUKTUR DATA
Assalamualaikum Wr. Wb.
Halo...
Nama saya Rofinus Aryanto, Mahasiswa Universitas Muhammadiyah Sidoarjo, jurusan Informatika.
Halo...
Nama saya Rofinus Aryanto, Mahasiswa Universitas Muhammadiyah Sidoarjo, jurusan Informatika.
Rangkuman Modul
Praktikum Algoritma dan Struktur Data
POKOK BAHASAN 1
STRUKTUR DATA, ARRAY,
POINTER, DAN STRUKTUR
A. Konsep
Dasar Struktur Data
Struktur data adalah bagian
dari ilmu pemrograman dasar yang mempunyai karakteristik yang terkait dengan sifat
dan cara penyimpanan sekaligus penggunaan atau pengaksesn data.
Struktur data bertujuan agar
cara merepresentasikan data dalam memebuat 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 :
a. 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 int, char, unsigned).
- Nama_var
: untuk menyatakan nama variabel yang dipakai.
- Ukuran
: untuk menyatakan jumlah maksimal elemen array.
Contoh : float nilai_ujian [5];
b. Array Dua Dimensi
Tipe data array dua diemnsi biasa digunakan
untuk menyimpan, mengolah maupun mendeklarasikan array agar dapatv menyimpan
data adalah :
Tipe_var nama_var[ukuran1][ukuran2];
Dimana :
- Ukuran 1 menunjukkan jumalah/nomor baris.
- Ukuran 2 menunjukkan jumlah/nomor kolom.
c. Array Multidimensi / Dimensi Banyak
Array berdimensi banyak atau multidimensi
terdiri array yang tidak terbatas hanya dua dimensi saja. Bentuk umum
pendeklarasian array multidimesni adalah : tipe_var
nama_var[ukuran1][ukuran2]…[ukurann];
Contoh : int data_angaka[3][6][6];
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 diatas, variabel nilai_tes mempunyai 5 elemen,
maka elemen pertama mempunyai indeks sama dengan 0, elemen kedua mempunyai
indeks 1, dan seterusnya. Bentuk umum pengaksesan suatu elemen variabel array
adalah :
Nama_var[indeks];
Gambar berikut memperlihatkan urutan komponen array dalam
memori.
Untuk variabel array nilai_tes :
Gambar : Struktur Array Satu Dimensi
Inisialisasi Array :
Array dapat diinisialisasikan secara langsung saat pertama kali
dideklarasikan (efisien untuk array berdimensi sedikit).
Contoh : int x[2]={1,2};
Array dapat dideklarasikan terlebih dahulu, baru kemudian diisi
elemnya.
Contoh :
Int x[2];
x[0]=1;
x[1]=2;
C. Konsep
Dasar Pointer
Pointer adalah sebuah variabel yang berisi lamat variabel yang
lain. Suatu ponter dimaksudkan untuk meunjuk koperatore suatu alamat memori
sehingga alamat dari suatu variabel dapat diketahui dengan mudah. Deklarasi
pointer :
Operator painter :
Operator ‘&’ : untuk mendapatkan alamat
memori operand/variabel pointer.
Operatot ‘*’ : untuk mengakses nilai data
operand/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 berkaitanmenjadi sebuah satu kesatuan. Contoh sebuah struktur adalah
informasi data tanggal, yang berisi tanggal, bulan, dan tahun.
Mendeklarasikan Struktur :
Contoh pendefisinian tipe data struktur adalah :
Struct data_tanggal
{ int tanggal;
Masing – masi tioe dari elemen struktur dapat berlainan. Adapun
variabel_struktur1 sampai dengan variabel_struktur M menyatakan bahwa variabel
struktur yag dideklarasikan bisa lebih dari satu. Jika ada lebih dari satu
variabel, antara variabel struktur dipisahkan dengan tandakoma.
Mengakses Elemen Struktur :
Elemen dari struktur dapat diakses dengan menggunakan bentuk :
Variabel_struktur.nama_field
Antara variabel_struktur dana nama_field dipisahkan dengan
operator titik (disebut operator anggota struktur). Contoh berikut merupakan
instruksi untuk mengisikan data padafield tanggal :
tgl_lahir.tang
gal=30 int
bulan;
int tahun;
};
Yang mendefinisikantipe struktur bernamadata_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
filed1;
Tipe
field2;
Tipe
field3;
}variabel_struktur1….variabel_strukturM;
Contoh program :
1. Program
pangkat dengan array dimensi satu.
Script :
#include<stdio.h>
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int
square[100]; // --> Array 1 dimensi dengan tempat yang dipesan sebanyak 100
int i;
int k;
//Perhitungan
for(i=0; i<10; i++) //angka yang ditampilkan 1-10
{
k=i+1;
square[i]=k*k;
printf("\n Pangkat dari %d adalah %d", k, square[i]);
}
_getch();
}
Hasil Output :
POKOK BAHASAN 2
LINKED LIST (SENARAI)
PENYAJIAN (TUTORIAL)
Linked list adalah
sejumlah objek atau elemen yang dihubungkan satu dengan lainnya sehingga
membentuk suatu list.
Struktur dasar sebuah list seperti gambar berikut :
Istilah – istilah dalam linked list :
- Simpul
a. Bagian data
b. Bagian pointer yang menunjuk ke simpul berikutnya
- First/Header
Variabel First/Header berisis alamat (pointer)/acuan (reference) yag
menunjuk lokasi simpul pertama linked list, digunakan sebagai awal
penelusuran linked list.
- Nil/Null
Tidak bernilai, digunakan untuk menyatakan tidak mengacu ke
manapun.
- Simpul Terakhr (Last)
Simpul terakhir linked list berari 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
petujuk elemen yang berisi NULL (kosong), tidak memiliki satu buah elemen pun
sehigga hanya berupa penunjuk awal elemn berisi NULL.
· List
Tunggal
List tuggal adalah list yang elemenya hanya
menyimpan informasi elemen setelahnya (next), sehingga jalanya
pengaksessan list hanya dapat dilakukan secara maju. List tuggal terbagi
menjadi tiga jenis yaitu list tunggal dengan kepala (first), list
tunggal kepala (first) dan ekor (tail), serta list
tunggal yang berputar.
Gambar : List Tunggal dengan Kepala dan Ekor,
List Tunggal Berputar
List Ganda
List ganda adalah sebuah list yang elemenya menyimpan informasi
elemen sebelumnya dan informasi elemen setelahnya, sehingga proses penelusuan
list dapat dilakukan secara maju dan mundur. List ganda terbagi menjadi tiga
jenis yaitu list ganda engan kepala (first), list ganda dengan
kepala (first) dan ekor (tail), serta list ganda
yag berputar.
Gambar : List ganda dengan Kepala, List ganda
dengan Kepala dan Ekor
Operasi Dasar pada Linked List :
IsEmpty :
Fungsi ini menentukan apakan linked list kosong atau tidak.
Size : operasi untuk
mengirim jumlah elemen di linked list.
Create : operasi untuk
penciptaan list baru yang kosong.
Insertfirst :
operasi penyisipan simpul sebagai simpul pertama.
Insertafter :
operasi untu penyisispan simpul setelah simpul tertentu.
Insertlast :
operasi untuk penyisipan simpul sebagai simpul terakhir.
Insertbefore :
operasi untuk penyisipan simpul sebelum simpul tertentu.
Deletefirst :
operasi penghapusan simpul pertama.
Deleteafter :
operasi penghapusan setelah simpul tertentu.
Deletelast :
operasi penghapusan simpul terakhir.
Contoh program :
1. Contoh
program sisip senarai (linked list).
Script :
#include<iostream>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
using namespace std;
typedef struct nod
{
int
data;
struct
nod *next;
}NOD, *NODPTR;
void CiptaSenarai (NODPTR *s)
{
*s =
NULL;
}
NODPTR NodBaru(int m)
{
NODPTR
n;
n =
(NODPTR) malloc
(sizeof(NOD));
if (n
!=NULL)
{
n->data=m;
n->next=
NULL;
}
return
n;
}
void SisipSenarai (NODPTR *s, NODPTR t,
NODPTR p )
{
if(p==NULL)
{
t->next=*s;
*s=t;
}
else
{
t->next=p->next;
p->next=t;
}
}
void CetakSenarai(NODPTR s)
{
NODPTR
ps;
for
(ps=s; ps!=NULL; ps=ps->next)
printf("%d -->", ps->data);
printf("NULL\n");
}
int main()
{
NODPTR
pel;
NODPTR
n;
CiptaSenarai(&pel);
n=NodBaru(55);
SisipSenarai(&pel, n, NULL);
n=NodBaru(75);
SisipSenarai(&pel, n, NULL);
CetakSenarai(pel);
_getch();
}
Hasil Output :
POKOK BAHASAN 3
STACK (TUMPUKAN)
PENYAJIAN (TUTORIAL)
Stack adalah kumpula elemen-elemen yang tersimpan dalam suatu
tumpukan. Dikatakan bahwa elemen Stack tersususn secara LIFO (Last In
First Out).
Gambar : Ilustrasi Stack
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 ke tumpukan.
Penambahan di elemen menyebabakan kondisi kesalahan Overflow.
- 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 tumpukan paling atas.
void Push (itemType 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 memerikasa 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 dinamis
Stack dengan representasi dinamis biasanya diimplementasikan
dengan menggunakan pointer yang mnunjuk pada elemen-elemen yang dialokasikan
pada memori. Illustrasi stack dengan representasi dinamis dapat dilihat pada
gambar :
Gambar : Representasi Stack Dinamis
Karena semua operasi pada sebuah stack diawali dengan elemen
yang paling atas maka jika menggunakan representasi dinamis saat elemen
ditambahkan akan mengguakan penambahan elemenpada awal stack (addfirst) dan
saat pengambilan atau penghapusan elemen menggunakan penghapusan di awal
stack (delfirst).
Contoh program :
1. Program
Stack
Script :
#include<stdio.h>
#include<conio.h>
#include<iostream>
#define MAXSTACK 3
typedef int itemType;
typedef struct
{
int item[MAXSTACK];
int jml;
}Stack;
void init(Stack *s)
{
s->jml=0;
}
int kosong(Stack *s)
{
return
(s->jml==0);
}
int penuh(Stack *s)
{
return
(s->jml==MAXSTACK);
}
void isi(itemType x, Stack *s)
{
if(penuh(s))
printf("\nMAAF!!! Data Penuh\n");
else
{
s->item[s->jml]=x;
++(s->jml);
}
}
void ambil(Stack *s, itemType *x)
{
if(kosong(s))
printf("\nMAAF!!!
Data Kosong\n");
else
{
--(s->jml);
*x=s->item[s->jml];
s->item[s->jml]=0;
printf("\nData %i Berhasil Diambil\n", *x);
}
}
void tampil(Stack *s)
{
if(kosong(s))
printf("\nMaaf Data Masih Kosong\n");
else
printf("\n");
for(int i=s->jml-1;i>=0;i--)
{
printf("Data: %d\n", s->item[i]);
}
}
void hapus(Stack *s)
{
s->jml=0;
printf("\nSemua Data Berhasil Dihapus\n");
}
int main()
{
int pil;
Stack
tumpukan;
itemType
data;
init(&tumpukan);
do
{
printf("\nMENU: \n 1. Isi (Data Angka)\n 2. Ambil\n 3. Lihat\n 4.Hapus
(Hapus Semua Data)\n 5. Keluar\n");
printf("\n");
printf("Masukkan Pilihan : ");
scanf("%i", &pil);
switch(pil)
{
case 1:
printf("\nMasukkan Data Angka : ");
scanf("%i", &data);; isi (data,&tumpukan);
break;
case 2:
ambil(&tumpukan,&data);
break;
case 3:
tampil(&tumpukan);
break;
case 4:
hapus(&tumpukan);
break;
}
}while(pil!=5);
getch();
}
Hasil Output :
POKOK BAHASAN 4
QUEUE (ANTRIAN)
PENYAJIAN (TUTORIAL)
Antrian adalah suatu
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).
Gambar : ilustrasi Antrian dengan 8 Elemen
Karakteristik penting antrian sebagai berikut
:
a. Elemen antrian yaitu item-item data yang
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 di 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
diantranya adalah :
1. Create -> Membuat
antrian baru.
NOEL
(CREATE(Q)) = 0
FRONT (CREATE(Q)) = tidak terdefinisi
REAR (CREATE(Q))=tidak terdefinisi
2. IsEmpty ->Untuk
memeriksa apakah antrian sudah penuh atau belum.
ISEMPTY
(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 kedalam Antrian, penambahan elemen selalu ditambahkan di
elemen paling belakang.
REAR
(INSERT(A,Q)) = A
ISEMPTY
(INSERT(A,Q)) = FALSE
Algoritma QINSERT :
a. IF FRONT = 1 AND REAR = N,
OR IF FRONT =REAR +1, THEN OVERFLOW, RETURN
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 :=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 biasanya
diimplementasikan dengan menggunakan array. Sebuah array memiliki tempat yang
dialokasikan awal 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 dengan representasi dinamis
dapat dilihat pada gambar :
Contoh program :
1. Program
Queue Statis
Script :
#include<queue>
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
queue
<int> que;
que.push(10);
que.push(2);
que.push(3);
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
que.pop();
cout<<"10 sudah dikeluarkan"<<endl;
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
que.push(6);
cout<<"Angka 6 dimasukkan"<<endl;
cout<<"Paling depan : "<<que.front()<<endl;
cout<<"Paling belakang : "<<que.back()<<endl;
_getch();
}
Hasil Output :
POKOK BAHASAN 5
REKURSIF
PENYAJIAN(TUTORIAL)
Fungsi rekursif adalah suatu fungsi yang memanggil dirinya sendiri,
artinya fungsi tersebut dipanggil didalam tubuh fungsi itu sendiri. Contoh
menghitung nilai factorial. 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.
Contoh program :
1. Program
Bilangan Genap dan Bilangan Ganjil
Script :
#include<iostream>
#include<conio.h>
using namespace std;
void odd (int a);
void even (int a);
int main()
{
int i;
do
{
cout<<"Masukkan Bilangan 1-9(0 untuk Keluar) : \n";
cin>>i;
odd(i);
cout<<endl;
}while
(i!=0);
_getch();
}
void odd(int a)
{
if((a%2)
!=0)
cout<<"Bilangan
GANJIL \n";
else
even (a);
}
void even (int a)
{
if((a%2)==0)
cout<<"Bilangan GENAP \n";
else
odd(a);
}
Hasil Output :
MODUL 6
SORTING (PENGURUTAN)
PENYAJIAN (TUTORIAL)
Pengurutan data (string) di definisikan sebagai suatu proses
untuk menyusun kembali himpunan objek menggunakan aturan tertentu. Ada 2 macam
urutan yang bisa digunakan dalam proses pengurutan yaitu :
v Urutan naik (ascending)
yaitu dari data yang mempunyai nilai paling kecil sampai nilai 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.
P
ada 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 pengecekkan apakah ada data yang hilang. Misalnya ;
kamus bahasa , buku telfon.
ü Mempercepat proses
pencarian data yang harus dilakukan berulang kali
Beberapa faktor yang 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.
Gambar : Langkah 1 Bubble Sort
Gambar 6.2 Langkah 2 Bubble Sort
Gambar 6.3 Langkah 3 Bubble Sort
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 data yang terkecil kemudian menukarkannya dengan data yang
digunakan sebagai acuan atau sering dinamakan pivot.
Selama proses, pembandingan 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 dari data kedua sampai terakhir. Data
terkecil yang kita peroleh ditukar dengan data kedua dan dengan demikian
seterunya semua elemen dalam keadaan terurutkan
Gambar : Langkah Selection Sort
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[j], &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 sublist yang 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 sendirinya (langkah solve)
B. Untuk kasus n>1, maka
:
a. DIVIDE : 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-and-C pada masing-masing bagian
c. MERGE : gabung hasil
pengurutan kedua bagian sehingga diperoleh table a yang terurut.
Contoh program :
1. Program
Ascending Dengan Menggunakan Bubble Sort
Script :
#include<iostream>
#include<conio.h>
#include<iomanip>
using namespace std;
int main()
{
int
dataku[]={5, 34, 32, 25, 75, 42, 2};
int
adaPertukaran;
int n;
cout<<"Data BELUM diurutkan : \n";
for(int
ctr=0;ctr<7;ctr++)
{
cout<<setw(3)<<dataku[ctr];
}
cout<<endl<<endl;
//PENGURUTAN
do {
adaPertukaran = 0;
for(int i = 0; i<7-1; i++)
{
if(dataku[i+1]<dataku[i])
{
n = dataku[i];
dataku[i]=dataku[i+1];
dataku[i+1]=n;
adaPertukaran = 1;
}
}
} while
(adaPertukaran == 1);
//MENAMPILKAN HASIL PENGURUTAN
cout<<"Data SETELAH diurutkan : \n";
for(int
i=0;i<7;i++)
{
cout<<dataku[i];
cout<<" ";
}
_getch();
}
Hasil Output :
Wassalamualaikum Wr.
Wb.
Komentar
Posting Komentar