Angga Noviar Cipta Pahlevi UMSIDA

Assalamu’alaikum Wr. Wb.

Perkenalkan sobat pembaca saya Angga Noviar Cipta Pahlevi, saya merupakan mahasiswa semester 2 Program Studi Informatika, Fakultas Sains dan Teknologi dari Universitas Muhammadiyah Sidoarjo. Membuat Rangkuman ini merupakan salah satu dari penilaian yang diberikan demi menyelesaikan Praktikum Algoritma dan Struktur Data di Program Studi Informatika, Fakultas Sains dan Teknologi dari Universitas Muhammadiyah Sidoarjo.

Pada Praktikum Algoritma dan Pemrogram ini bahasa yang digunakan adalah Bahasa C++. Dan dalam proses praktikum menggunakan Dev C++ dan Visual C++ sebagai IDE (Integrated Development Environment) yang mana adalah program komputer yang memiliki fasilitas yang diperlukan dalam pembangunan perangkat lunak, tetapi tidak hanya kedua program tersebut masih ada IDE lain yang dapat digunakan seperti Code::Blocks, Eclipse, Netbean, Atom.

--------------------------------------------------

Rangkuman Praktikum Algoritma dan Struktur Data

--------------------------------------------------

Pokok Bahasan 4 : Queue (Antrian)

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai 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 antrian.

b) Memahami operasi-operasi dasar pada antrian.

c) Memahami representasi statis dan dinamis pada antrian.

PENYAJIAN

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) 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 Iain-lain.

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 diantaranya 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 ke dalam 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

1. Dequeue/Remove untuk menghapus elemen terdepan/pertama dari Antrian. Algoritma QDELETE :

IF FRONT := NULL, THEN UNDERFLOW, RETURN

SET ITEM := QUEUE[FRONT]

|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

RETURN

Representsi

queue :

Representasi

statis

Queue 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 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 :

Pokok Bahasan 5 : Rekursif

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai rekursif. Setelah mempelajari bab ini diharapkan mahasiswa mampu :

a) Mengetahui dan memahami definisi rekursif.

b) Memahami sifat-sifat rekursif.

c) Mengaplikasikan rekursif.

PENYAJIAN

Fungsi rekursif adalah suatu fungsi yang memanggil dirinya sendiri，artinya fungsi tersebut dipanggil di dalam tubuh fungsi itu sendiri. Contoh menghitung nilai factorial. Rekursif sangat memudahkan untuk memecahkan permasalahan yang kompleks. Sifat-sifat rekursif:

a) Dapat digunakan ketika inti dari masalah terjadi berulang kali.

b) Sedikit lebih efisien dari iterasi tapi lebih elegan.

c) 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)

PENDAHULUAN

Setelah mempelajari bab ini diharapkan mahasiswa mampu :

a. Menunjukkan beberapa algoritma dalam pengurutan.

b. Menunujukkan 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

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 :

Urutan naik {ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar.
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 yng kita miliki. Tempat penyimpanan data, misalnya piringan, pita atau kartu, dll.

Beberapa algoritma metode pengurutan dan prosedurnya sebagai berikut:

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.

Langkah 1 Bubble Sort

Langkah Bubble Sort

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

6. i = i + 1

Prosedur yang menggunakan metode gelembung :

void BubbleSort()

{

inti, 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]);

}

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 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 dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.

Langkah Selection Sort

Algoritma seleksi dapat dituliskan sebagai berikut:

1. i = 0

2. selama (i < N-1) kerjakan baris 3 sampai dengan 9 3

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. 9.i = i + 1

Di bawah ini merupakan prosedur yang menggunakan metode seleksi:

void SelectionSort()

{

inti, 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]);

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 eflsien (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=l, maka table a sudah terurut sendirinya (langkah solve)

B. Untuk kasus n>l, maka :

a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masingmasing 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.

Di atas merupakan rangkuman dari pokok bahasan untuk Tugas Praktikum Algoritma dan Struktur Data, sekian dari saya mohon maaf jika terdapat kurangnya. Terimakasih untuk yang telah meluangkan waktu untuk membaca semuanya dan atas apresiasinya.

Search This Blog