ALGORITMA DAN PEMOGRAMAN II "Graf dan Pohon"

“TI Politala Algoritma dan Pemograman II 2C”

[ Tugas Kuliah ] Algoritma dan Pemograman “Graf dan Pohon”

“Graf dan Pohon”

   A. Pengertian Algoritma Kruskal

Algoritma Kruskal adalah algoritma dalam teori graph yang menemukan suatu pohon rentang minimum untuk terhubung dalam graf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak terhubung, maka menemukan hutan rentang minimum (pohon rentang minimum untuk setiap komponen terhubung). Algoritma Kruskal adalah contoh dari algoritma rakus. Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society , hal 1956. Algoritma lain untuk masalah ini termasuk Algoritma Prim , Reverse-Hapus algoritma, dan algoritma Borůvka's

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf G adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyalah sebuah pohon yang merentang minimum.

   B. Kelebihan Dan Kekurangan Algoritma Kruskal

1.    Kelebihan

Kelebihan dari algortima kruskal adalah sangat cocok digunakan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan urutan bobot sisi bukan simpul.

2.    Kekurangan

Kekurangan dari algortima kruskal kurang cocok digunakan saat graf dimana setiap simpul terhubungkan dengan semua simpul yang lain. Karena algoritma ini menitik beratkan pada pencarian sisi yang diurutkan.

    C. Pengertian Algoritma Djikstrak

Algoritma Dijkstra diterapkan untuk mencari lintasan terpendek pada graf berarah. Namun, algoritma ini juga benar untuk graf tak berarah. Algoritma Dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip greedy. Prinsip greedy pada algoritma dijkstra menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya dalam himpunan solusi. Djikstrak merupakan salah satu varian bentuk algoritma popular dalam pemecahan persoalan terkait masalah optimasi pencarian  lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada algoritma Dijkstrak, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute lintasan terpendek.

    D. Penerapan Algoritma Djikstrak Pada Jaringan Komputer

Jaringan komputer dapat dimodelkan sebagai sebuah graf, dengan setiap simpul menyatakan sebuah komputer/router dan sisi di dalam graf menyatakan saluran komunikasi (sering disebut link). Setiap sisi mempunyai label nilai (yang disebut bobot). Bobot tersebut dapat menyatakan jarak geografis (dalam km), kecepatan transfer data, waktu pengiriman).

  E. Kasus Pencarian Rumah Sakit dengan Algoritma Djikstra dan Algoritma Kruskal

1.    Maps

2.    Graf

Keterangan:

0: Rumah Sakit Khusus Ibu dan Anak Annisa

1: Rumah Sakit TPT Dr. R. Soeharsono

2: Rumah Sakit Umum Suaka Insan

3: Rumah Sakit Islam Banjarmasin

4: Rumah Sakit Mata Banjarmasin

5: RSUD Sultan Suriansyah Banjarmasin

6: RS B. Ibunda Siti

7: Rumah Sakit Umum Daerah Ulin

8: RS. Bhayangkara TK. III Banjarmasin

9: Rumah Sakit Khusus Bedah Banjarmasin Siaga

3.    Tabel matriks dari graf diatas yaitu:

        F.  Program Algoritma Djikstrak

    G. Hasil Running

    

    H. Program Algoritma Kruskal

    

    I. Hasil Running

    

    Sumber :      http://student.blog.dinus.ac.id/matematikadiskritricorianalvian/2018/12/31/9/. Diakses pada tanggal 26 Mei 2019.  Pukul 10.00 WITA.

  http://bobo-magazine.blogspot.com/2010/05/algoritma-kruskall.html. Diakses pada tanggal 26 Mei 2019. Pukul 10.30 WITA.

  http://student.blog.dinus.ac.id/mfadhilhabibie/2018/12/27/algoritma-kruskala-materi/. Diakses pada tanggal 26 Mei 2019. Pukul 21.56 WITA.

  https://wirasetiawan.blog/2015/04/02/tentang-algoritma-dijkstra/. Diakses pada tanggal 26 Mei 2019. Pukul 22.01 WITA.

 

Algoritma dan Pemograman II "Sorting (Buble dan Quick)

“TI Politala Algoritma dan Pemograman II 2C”

[ Tugas Kuliah ] Algoritma dan Pemograman “Sorting (Buble dan Quick)”

“Sorting (Buble dan Quick)”

        A.  Pengertian dan Konsep Pada Buble Sort

Pengurutan merupakan proses dasar yang ada dalam algoritma dan stuktur data. Terdapat banyak algoritma pengurutan yang sering digunakan, namun pada tulisan kali ini akan dibahas mengenai dasar algoritma Bubble Sort. Algortima ini merupakan algortima pengurutan sederhana dan biasanya dipelajari sebagai pokok bahasan seputar pengurutan. Algoritma Bubble Sort ini merupakan proses pengurutan yang secara berangsur-angsur berpindah ke posisi yang tepat karena itulah dinamakan Bubble yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang terbesar ke yang terkecil (ascending) atau sebaliknya (descending). Secara sederhana, bisa didefenisikan algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data disebelahnya secara terus menerus sampai dalam satu iterasi tertentu tidak ada lagi perubahan. Untuk belajar algoritma Bubble Sort ini kita hanya perlu memahami cara yang digunakan untuk mengurutkan data, sederhananya algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Di bawah ini merupakan gambaran dari algoritma Bubble Sort dengan array “3 1 4 2 8”.

          Proses pertama :

(3 1 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 3 2 4 8)

Proses kedua :

(1 3 2 4 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

Proses ketiga :

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

Jika kita perhatikan proses diatas, para proses kedua data sudah terurut dengan benar. Tetapi algoritma Bubble Sort tetap berjalan hingga proses kedua berakhir. Proses ketiga masih terus berjalan karena pada algoritma Bubble Sort maksud terurut itu adalah tidak ada satupun penukaran pada suatu proses. Proses ketiga ini dilakukan untuk verifikasi data. Algoritma Bubble Sort ini mempunyai kelebihan dan kekurangan, untuk kelebihannya metode ini merupakan metode paling sederhana untuk mengurutkan data. Selain sederhana, algoritma Bubble Sort mudah dipahami. Sementara itu, kekurangannya terletak pada efisiensi. Bubble Sort ini merupakan metode pengurutan yang tidak efisien karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya. Selain itu, jumlah pengulangan akan tetap sama jumlahnya meskipun data sudah cukup terurut.

  B. Contoh Program Pada Buble Sort

#include<iostream>

#include <conio.h>

using namespace std;

main()

{

    int data[6];

    int a, b, c, i;

    int buble;

    int pilihan;

    string fg;

    cout<<"Banyak Data Yang Di Masukkan :";cin>>a;

    cout<<endl;

    for (i=0; i<a; i++)

    {

        cout<<"Masukkan Data Ke - "<<i+1<<" :";cin>>data[i];

        cout<<endl;

    }

    ulang :

        cout<<"Pilih Metode Yang Ingin Digunakan :"<<endl;

        cout<<"1. Ascending"<<endl;

        cout<<"2. Descending"<<endl;

        cout<<endl;

        cout<<"Masukkan Metode Yang Dipilih :";cin>>pilihan;

        cout<<endl;

        if (pilihan ==1)

        {

            for (i=0; i<a-2; i++)

            {

                for (c=a-1; c>=i+1; c--)

                {

                    if (data[c] < data[c-1])

                    {

                        buble = data[c];

                        data[c] = data[c-1];

                        data[c-1] = buble;

                    }

                }

            }

            cout<<"Data Yang Terurut Menggunakan Ascending"<<endl;

            cout<<endl;

            for (i=0; i<a; i++)

            {

                cout<< "Data ke - "<<i+1<< " :"<<data[i]<<endl;

            }

        }

        else if (pilihan ==2)

        {

            for (i=0; i<=a-2; i++)

            {

                for (c=a-1; c>=i+1; c--)

                {

                    if (data[c] > data[c-1])

                    {

                        buble = data[c];

                        data[c] = data[c-1];

                        data[c-1] = buble;

                    }

                }

            }

            cout<<"Data Yang Terurut Menggunakan Descending"<<endl;

            cout<<endl;

            for (i=0; i<a; i++)

            {

                cout << "Data ke - " <<i+1<< " : "<<data[i]<<endl;

            }

        }

        else

        {

            cout << "Data Yang Anda Masukkan Salah "<<endl;

            cout << "Jika Anda ingin mengulang Pilihlah Yes Jika Tidak Pilih Tidak :"; cin>>fg;

            cout <<endl;

            if (fg =="Y" || fg=="T")

            {

                goto ulang;

            }

            else

            {

                cout << "Stop"<<endl;

            }

        }

}

C. Metode Quick Sort

Algoritma quicksort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di Computer Journal 5 pada April 1962. Bentuknya yang sederhana, efisien dan efektif dengan cepat membuatnya menjadi algoritma pengurutan (sorting) yang paling banyak digunakan, terutama dalam bahasa pemrograman. Berbagai penelitian dan pengembangan telah banyak dilakukan hingga saat ini. Tercatat peneliti seperti Sedgewick, Bentley, McIlroy, Clement, Flajolet, Vallee, hingga Martinez, membuat analisis dan implementasi dari quicksort. Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif.Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort. Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data,  kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa. Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini mempunyai efektifitas yang tinggi dengan teknik menukarkan dua elemen dengan jarak yang cukup besar. Metode pengurutan quick sort dapat diimplementasikan dalam bentuk non rekursif dan rekursif. Berbagai varian dari quicksort pada intinya berupaya untuk mengembangkan teknik-teknik pembuatan partisi yang efektif untuk berbagai macam masukan.Hal ini merupakan bahan yang terus dipelajari hingga kini.Ditambah pula dengan perbaikan dari segi pemrograman sehingga lebih efisien (seperti mengurangi operasi pembandingan, pertukaran maupun perulangan). Pada tahun 1998 M.D. McIlroy membuat tulisan berjudul “A Killer Adversary for Quicksort” yang menguraikan cara untuk membuat susunan data tertentu (dalam array) hingga operasi pengurutan menggunakan quicksort mendekati kuadratik O(n2). Cara ini berlaku untuk setiap varian dari quicksort dengan syarat tertentu.Dikenal juga dengan istilah antiqsort.

   D.  Program yang Berjalan Pada Quick Sort

#include <iostream>

using namespace std;

int n;

void quick_sort(int arr[], int left, int right);

int main()

{

    int jmlhbil=5;

    cout << "Masukkan jumlah bilangan : "<<endl; cin>>jmlhbil;

    int ar[jmlhbil];

    for (int i=0; i<jmlhbil; i++)

    {

        cout << "Bilangan ke-"<<i+1<<endl;

        cin>>ar[i];

    }

    quick_sort(ar, 0, jmlhbil-1);

    cout << "Data yang telah diurutkan : "<<endl;

    for(int i=0; i<jmlhbil; i++)

    {

        cout<<ar[i]<<"\n";

    }

}

void quick_sort(int arr[], int left, int right)

{

    int i=left, j=right;

    int tmp;

    int pivot=arr[(left+right)/2];

    while (i<=j)

    {

        while (arr[i]<pivot) i++;

        while (arr[j]>pivot) j--;

        if (i<=j)

        {

            tmp=arr[i];

            arr[i]=arr[j];

            arr[j]=tmp;

            i++;

            j--;

        }

    }

    if(left<j)

        quick_sort(arr,left,j);

    if (i<right)

        quick_sort(arr,i,right);

}

Sumber :

https://muhammadhaluanrangkuti.blogspot.com/2016/10/pengertian-dan-metode-quick-sort.html

https://teknojurnal.com/pengertian-algoritma-bubble-sort/