Tugas Minggu 11 - Alpro 1 - SI UNIPDU

ALGORITMA PENGURUTAN

Dua Macam Pengurutan

  • Ascending (urut naik) merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar.
  • Descending (urut turun) adalah sebaliknya, yaitu pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.

Pengurutan Gelembung (Bubble Sort).

Bubble Sort merupakan metode pengurutan yang paling banyak digunakan di kalangan programmer dikarenakan penggunaannya yang simple dan sederhana. Namun, dibalik kesederhanaannya itu terdapat proses algoritma yang terlalu lama sehingga bisa dikatakan bahwa Metode Bubble Sort merupakan metode yang paling lambat dibanding dengan metode pengurutan yang lainnya. Pengurutan dilakukan dengan memilih elemen terbesar dan menempatkan pada posisinya, kemudian mencari element terbesar berikutnya dan menempatkan pada tempatnya, dan seterusnya.

Proses Bubble Sort Ascending

  • Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih besar maka tukar.
  • Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih kecil maka tukar.

Proses Bubble Sort Descending

  • Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih kecil maka tukar.
  • Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih besar maka tukar.

Penjelasan Algoritma Bubble Sort:

  1. Dalam Bubble Sort. Jumlah Iterasi sebesar banyaknya Data. Diatas jumlah datanya ialah 5 maka, jumlah iterasinya ialah 5. Selain itu, setiap iterasi terdapat proses yang jumlahnya ialah sebesar banyaknya Data. Diatas jumlah datanya ialah 5 maka, jumlah proses setiap iterasinya ialah 5. Dan untuk iterasi berikutnya harus dikurang 1.
  2. Dalam Bubble Sort, Walaupun data sudah terurut seperti pada kasus diatas, data sudah terurut pada iterasi ke-4. Namun, proses sorting tetap jalan sampai jumlah iterasinya terpenuhi.
  3. Proses Pertukaran Datanya dimulai dari data pertama dibandingkan dengan data kedua atau bisa digambarkan dengan Data[n] <==> Data[n+1]. Lakukan langkah ini sampai berada pada Data Terakhir.

Contoh Implementasi Bubble Sort pada Java

package Erlangga;
import java.util.Scanner;

public class BubbleSort {
    public static void main(String[] args)
    {
        //    Buat Objek Scanner
        Scanner scan = new Scanner(System.in);
         
        //    Input jumlah Data
        System.out.print("Masukkan jumlah Data : ");    int jlh_data = scan.nextInt();
         
        //    Input nilai tiap Data
        int[] data = new int[jlh_data];        //    Array untuk menampung nilai tiap Data
        System.out.println();
        for(int a = 0; a < jlh_data; a++)
        {
            System.out.print("Nilai Data ke-"+(a+1)+" : ");
            data[a] = scan.nextInt();
        }
         
        //    Tampilkan Data Sebelum di Sorting
        System.out.println("\nData Sebelum di Sorting");
        for(int a = 0; a < jlh_data; a++)
            System.out.print(data[a]+" ");
         
        //    Proses Bubble Sort
        System.out.println("\nProses Bubble Sort");
        for(int a = 0; a < jlh_data; a++)
        {
            System.out.println("Iterasi ke-"+(a+1)+" :");
            for(int b = 0; b < jlh_data; b++)
                System.out.print(data[b]+"  ");
             
            System.out.println("   Bandingkan "+data[0]+" dengan "+data[1]);
            for(int b = 0; b < jlh_data-1; b++)
            {
                String pesan = "   Tidak ada pertukaran";
                if(data[b] > data[b+1])
                {
                    //    proses pertukaran nilai Data
                    pesan = "   Data "+data[b]+" ditukar dengan "+data[b+1];
                    int temp = data[b];        //    Variable Sebagai pihak ketiga
                    data[b] = data[b+1];    
                    data[b+1] = temp;
                     
                }
             
                if(b < jlh_data-(a+1))
                {
                    for(int c = 0; c < jlh_data; c++)
                        System.out.print(data[c]+"  ");
                     
                    System.out.println(pesan);;
                }
            }
 
            System.out.println("\n");
        }
         
        //    Tampilkan Data Setelah di Sorting
        System.out.print("Data Setelah di Sorting : ");
        for(int a = 0; a < jlh_data; a++)
            System.out.print(data[a]+"  ");
         
    }
}


contoh output

Masukkan jumlah Data : 5


Nilai Data ke-1 : 8

Nilai Data ke-2 : 5

Nilai Data ke-3 : 2

Nilai Data ke-4 : 6

Nilai Data ke-5 : 12


Data Sebelum di Sorting

8 5 2 6 12

Proses Bubble Sort

Iterasi ke-1 :

8  5  2  6  12     Bandingkan 8 dengan 5

5  8  2  6  12     Data 8 ditukar dengan 5

5  2  8  6  12     Data 8 ditukar dengan 2

5  2  6  8  12     Data 8 ditukar dengan 6

5  2  6  8  12     Tidak ada pertukaran



Iterasi ke-2 :

5  2  6  8  12     Bandingkan 5 dengan 2

2  5  6  8  12     Data 5 ditukar dengan 2

2  5  6  8  12     Tidak ada pertukaran

2  5  6  8  12     Tidak ada pertukaran



Iterasi ke-3 :

2  5  6  8  12     Bandingkan 2 dengan 5

2  5  6  8  12     Tidak ada pertukaran

2  5  6  8  12     Tidak ada pertukaran



Iterasi ke-4 :

2  5  6  8  12     Bandingkan 2 dengan 5

2  5  6  8  12     Tidak ada pertukaran



Iterasi ke-5 :

2  5  6  8  12     Bandingkan 2 dengan 5



Data Setelah di Sorting : 2  5  6  8  12

Pengurutan Selection Sort

Dibanding Bubble Sort, Selection Sort jelas lebih baik dari segi kecepatan proses pengurutannya. Karena, Inti dari algoritma Selection Sort ialah mencari nilai yang paling kecil(Jika Ascending) atau nilai yang paling besar(Jika Descending) di urutan data berikutnya. Proses pengurutan menggunakan metode selection sort secara terurut naik adalah:

  1. Mencari data terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya dengan data pertama.
  2. mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.
  3. mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga
  4. dan seterusnya sampai semua data urut naik. apabila terdapat n data yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena tinggal satu satunya.

Proses Selection sort Ascending

  • Elemen yang paling besar diletakkan di akhir.
  • Elemen yang paling kecil diletakkan di awal.

Proses Selection sort Descending

  • Elemen yang paling kecil diletakkan di akhir.
  • Elemen yang paling besar diletakkan di awal

Penjelasan Algoritma Selection Sort:

  • Jumlah Iterasi untuk Selection Sort ialah berjumlah sebesar Jumlah Data – 1. Untuk kasus diatas, Jumlah Datanya ialah 6. Maka, jumlah Iterasinya ialah sebesar 6 – 1 = 5.
  • Proses pertukaran Data dimulai dari Data Pertama sampai Data Terakhir dengan cara membandingkan Data ke-n dan cari nilai yang paling kecil di sisi kanan nilai n.
  • Keterangan bahwa nilai Data yang sudah di tukar(nilai yang paling kecil) tidak akan dibandingkan lagi untuk proses iterasi berikutnya.

Contoh Implementasi Selection Sort Pada Java

package Erlangga;
import java.util.Scanner;

public class SelectionSort {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.print("Masukkan jumlah Data : ");
        int jlh_data = scan.nextInt();
        // Input nilai tiap Data
        int[] data = new int[jlh_data]; // Array untuk nilai tiap Data
       
            System.out.println();
            for(int x = 0; x < jlh_data; x++) {
                System.out.print("Input nilai Data ke-"+(x+1)+" : ");
                data[x] = scan.nextInt();
        }
        // Tampilkan Data Sebelum di sorting
        System.out.println();
        System.out.print("Data Sebelum di Sorting : ");
        for(int x = 0; x < jlh_data; x++)
            System.out.print(data[x]+" ");

        // Proses Selection Sort
        System.out.println("\n\nProses Selection Sort");
        for(int x = 0; x < jlh_data-1; x++) {
            System.out.println("Iterasi ke-"+(x+1)+" : ");
            for(int y = 0; y < jlh_data; y++)
                System.out.print(data[y]+" ");

            System.out.println("Apakah Data "+data[x]+" Urut?");

            boolean tukar = false;
            int index = 0;
            int min = data[x];
            String pesan = "Tidak Ada Pertukaran";
            for(int y = x+1; y < jlh_data; y++){
                if(min > data[y]) {
                    tukar = true;
                    index = y;
                    min = data[y];
                }
            }
            if(tukar == true) {
                // Pertukaran Data
                pesan = "Data "+data[x]+" ditukar dg "+data[index];
                int temp = data[x];
                data[x] = data[index];
                data[index] = temp;
            }
            for(int y = 0; y < jlh_data; y++)
                System.out.print(data[y]+" ");
       
            System.out.println(pesan+"\n");
        }
        // Tampilkan Data Setelah di Sorting
        System.out.print("Data Setelah di sorting : ");
        for(int x = 0; x < jlh_data; x++)
            System.out.print(data[x]+" ");
        }
       
}


contoh output

Masukkan jumlah Data : 4

 

Input nilai Data ke-1 : 7

Input nilai Data ke-2 : 5

Input nilai Data ke-3 : 4

Input nilai Data ke-4 : 2

 

Data Sebelum di Sorting : 7 5 4 2

 

Proses Selection Sort

Iterasi ke-1 :

7 5 4 2 Apakah Data 7 Urut?

2 5 4 7 Data 7 ditukar dg 2

 

Iterasi ke-2 :

2 5 4 7 Apakah Data 5 Urut?

2 4 5 7 Data 5 ditukar dg 4

 

Iterasi ke-3 :

2 4 5 7 Apakah Data 5 Urut?

2 4 5 7 Tidak Ada Pertukaran

 

Data Setelah di sorting : 2 4 5 7

Komentar

Posting Komentar