ALGORITMA DAN STRUKTUR DATA
Assalamualaikum Wr. Wb.
Halo...
Nama saya Siti Nur Haliza, Mahasiswa Universitas Muhammadiyah Sidoarjo, jurusan Informatika.
Halo...
Nama saya Siti Nur Haliza, 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