Algoritma Sorting

Assalamualaikum Wr. Wb

Untuk kasus kali ini kita akan membahas tentang algoritma sorting. Dalam Ilmu Komputer, Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical. Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia.

Tetapi sebelum itu output harus melengkapi dua syarat tertentu :

1. Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.

2. Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan.

Sejak permulaan komputasi, masalah pengurutan ini telah menarik penelitian yang serius, mungkin dikarenakan kerumitan dari penyelesaian secara efisien disamping mudah, dan dengan statemen yang kita mengerti. Sebagai contoh, bubble sort pertama sekali ditemukan pada tahun 1956. Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritma sorting baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006). Algoritma sorting sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritma untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritma inti, seperti Notasi Big O, Algoritma Pembagi, Struktur Data, Algoritma Acak, Analisa Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah.

Perbandingan Algoritma

Pada table ini merupakan angka dari rekord yang akan diurut. Kolom "Average" dan "Worst" memberikan kompleksitas waktu pada setiap case, dengan asumsi panjang setiap nilai merupakan konstan, dan oleh karena segala perbandingannya, penukarannya, dan segala operasi yang dibutuhkan dapat diproses pada waktu konstan. "Memori" menunjukkan jumlah dari simpanan tambahan dibutuhkan yang digunakan oleh list ini sendiri. Segala Sorting Pembanding ini. Waktu kalkulasi dan memori dari algoritma dapat diukur menggunakan notasi beragam seperti theta, omega, Big-O, small-o, dll. Memori dan waktu kalkulasi dibawah dapat diaplikasikan pada semua dari 5 notasi dibawah.

1. Algoritma Bubble Sort

salah satu algoritma klasik dan paling sederhana dalam hal pengurutan (sorting) adalah algoritma Bubble Sort. Terlepas dari beberapa kekurangan yang membuat algoritma ini tidak banyak digunakan dalam proses pengurutan di aplikasi, namun tidak bisa dipungkiri, algoritma ini boleh dikatakan sebagai pionir algoritma sorting. Di dalam matakuliah Algoritma dan Struktur Data di berbagai perguruan tinggi juga bisa dipastikan memasukkan konsep pengurutan menggunakan algoritma Bubble sebagai salah satu pokok bahasan.

Untuk itulah, saya rasa tidak ada salahnya untuk sedikit membahas mengenai algoritma bubble sort ini. Tentunya disertai contoh program sederhana yang menerapkan pengurutan menggunakan algoritma bubble sort. Contoh program akan disajikan dalam Bahasa C dan PHP. Algoritma bubble sort dalam proses pengurutan data secara sederhana bisa diibaratkan seperti halnya gelembung udara (bubble). Algoritma ini akan menggeser  nilai yang terkecil atau terbesar (sesuai dengan jenis pengurutan, ascending atau descending) ke posisi ujung dari daftar. Demikian seterusnya hingga semua daftar dalam keadaan terurut. Proses dasar yang terjadi dalam algoritma ini adalah proses pertukaran nilai (swapping)

Berikut ini algoritma Bubble Sort yang saya kutip dari Wikipedia:

1. procedure bubbleSort( A : list of sortable items ) defined as:
2. do
3. swapped := false
4. for each i in 0 to length(A) - 2 inclusive do:
5. if A[i] > A[i+1] then
6. swap( A[i], A[i+1] )
7. swapped := true
8. end if
9. end for
10. while swapped
11. end procedure

Contoh penerapan algoritma bubble sort dalam Bahasa Java

import java.util.Scanner;
public class pengurutan {

    int[] angka=new int[5];
    public pengurutan()
    {
        Scanner input = new Scanner(System.in);
        for(int i=0;i<5 i="" p="">        {
            System.out.print("Masukkan Angka ke "+(i+1)+" : ");
            angka[i] = input.nextInt();
        }

        tampilkanAngka();
        urutkanAngka();
        tampilkanAngka();

     
    }

    void tampilkanAngka()
    {
        System.out.println("\n--------------------------------");
        for (int i=0;i<5 i="" p="">        {
            System.out.print(angka[i]+" ");
        }
    }

    void urutkanAngka()
    {
        int tampung;
        for (int i=0;i        {
            for(int j=0;j            {
                if(angka[j]>angka[j+1])
                {
                    tampung=angka[j];
                    angka[j]=angka[j+1];
                    angka[j+1]=tampung;
                }

            }
         
        }

    }

    public static void main(String[] aksi)
    {
        pengurutan urut = new pengurutan();
    }
}

2. Quick Sort

Pengerian Quick Sort adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Implementasi dalam Bahasa Pemograman Java

import jeliot.io.*;

public class QuickSort{

  public static void main(String a[]){

    int i;

    int array[] = {12,9,4,29,7,1,3,10};

    System.out.println("Values Before the sort:\n");

    //for(i = 0; i < array.length; i++)

      //System.out.print( array+"  ");

    System.out.println();

    quickSort(array,0,7);

    System.out.print("Values after the sort:\n");

    for(i = 0; i

      System.out.print(array+"  ");

    System.out.println();

    System.out.println("PAUSE");

  }

 public static int partition(int arr[], int left, int right) { 

      int i = left, j = right; 

      int tmp; 

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

      while (i <= j) { 

            while (arr < pivot) 

                  i++; 

            while (arr[j] > pivot) 

                  j--; 

            if (i <= j) { 

                  tmp = arr; 

                  arr = arr[j]; 

                  arr[j] = tmp; 

                  i++; 

                  j--; 

            } 

      }; 

      return i; 

    } 

3. Implementasi Algoritma Selection Sort Menggunakan Java

Selection Sort merupakan salah satu algoritma pengurutan yang sederhana. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar.

Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut:

1. Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list

2. Menukarkan nilai ini dengan elemen pertama list

3. Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua

Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan. 

contoh simulasi algoritma selection sort sbb :

jika kita memiliki elemen array sbb :  {5, 1, 12, -5, 16, 2, 12, 14}

Algoritma di dalam Selection Sort terdiri dari kalang bersarang. Dimana kalang tingkat pertama (disebut pass)

berlangsung N-1 kali. Di dalam kalang kedua, dicari elemen dengan nilai terkecil. Jika didapat, indeks yang didapat ditimpakan ke variabel min. Lalu dilakukan proses penukaran. Begitu seterusnya untuk setiap Pass. Pass sendiri makin berkurang hingga nilainya menjadi semakin kecil. Berdasarkan operasi perbandingan elemennya.

implementasinya dalam bahasa pemrograman sbb :

/**

 *

 * @author Edi Zhou

 */

public class selectionSort {

    int[] angka={5, 1, 12, -5, 16, 2, 12, 14};

    public selectionSort()

    {

        tampilkanAngka();

        urutkanAngka();

        tampilkanAngka();

        

    }

    void tampilkanAngka()

    {

        System.out.println("\n--------------------------------");

        for (int i=0;i

        {

            System.out.print(angka[i]+" ");

        }

    }

    void urutkanAngka()

    {

        int tampung;

        for (int i=0;i

        {

            int minindek=i;

            for(int j=i+1;j

            {

                if(angka[j]

                    minindek=j;

                if(minindek!=i)

                {

                    tampung=angka[i];

                    angka[i]=angka[minindek];

                    angka[minindek]=tampung;

                }            

            }

            

         //tampilkanAngka();

        }

    }

    public static void main(String[] aksi)

    {

        selectionSort urut = new selectionSort();

    }

}

Nah smoga bermanfaat, terimakasih sudah berkunjung. jika ingin download source code silahkan klik Disini

Related product you might see: