Bogo Sort in Java

Dalam postingan kali ini, saya akan menjelaskan secara sederhana tentang Bogo Sort (penyortiran Bogo)

Bogo Sort
Dalam ilmu computer, Bogo Sort (bisa disebut juga stupidsort/slowsort/randomsort dan lain sebagainya) adalah algoritma sorting yang cukup tidak efektif berdasarkan generalisasi dan hasil tes paradigmanya. Bogo Sort tidak terlalu sering digunakan untuk menyortir, tapi masih sering digunakan untuk tujuan pendidikan, dan dikombinasikan dengan algoritma lain yang lebih riil. Bogo Sort digunakan dibanyak contoh pemrograman logika. Jika Bogo Sort digunakan untuk menyortir setumpuk kartu, maka hasilnya akan memeriksa apakah dek kartu tersebut sudah dalam urutan atau tidak,dan jika tidak, maka dek tersebut akan diacak, lalu dia mengambil satu kartu acak lalu menyusunnya, proses terus berlanjut hingga dek tersebut tersusun rapi. Nama Bogo diambil dari kata Bogus yang artinya palsu dalam bahasa inggris.


Deskripsi Algoritma Bogo Sort
Di bawah ini adalah contoh cara bekerja Bogo Sort dalam pseudocode:

while not isInOrder(deck):

shuffle(deck)

Jika semua elemen yang akan di sortir berbeda, maka jumlah perbandingan di setiap rata-rata hampir sama dengan (e-1)n! dan jumlah pertukaran nomer di setiap rata-rata akan sama dengan (n-1)n!. Jumlah pertukaran nomer akan lebih banyak dibandingkan dengan jumlah perbandingan, karena jika elemen-elemennya tidak berada dalam urutan, biasanya akan ditemukan setelah beberapa perbandingan dan tidak peduli berapa banyak elemen tersebut, tapi proses mengacaknya tetap berlanjut. Pada hal buruknya, jumlah perbandingan dan pertukaran elemen-elemen tidak terbatas, alasan yang sama jika kita melempar koin(head/tail) yang kemungkinan bisa terus-terusan muncul kepala dalam beberapa kali percobaan.

Hal baiknya jika elemen-elemennya sudah tersusun, jika begitu maka jumlah perbandingan adalah n-1 dan tidak ada pertukaran yang dilakukan.

Dari setiap jenisnya, lama proses suatu algoritma mempunyai batas sama halnya dengan dalil infinite monkey : ada beberapa kemungkinan untuk mendapat permutasi yang benar, jadi saat mencoba terus-terusan pasti akan ketemu juga pada akhirnya.

Berikut adalah beberapa Algoritma sorting yang sering dikombinasikan dengan Bogo Sort:

1. Gorosort
2. Bogobogosort
3. Bozosort
4. Quantum Bogosort

Flowchart Bogo Sort
berikut gambaran flowchart dari sortir Bogo :

Implementasi di Java

Dan berikut implementasinya dalam Java :

Dan berikut implementasinya dalam Java : import java.util.*;

public class BogoSort{
 
  private static final Random generator = new Random();  
 
  public static void bogoSort(int[] array)  {  
    while (!isSorted(array)) {  
      for (int i = 0; i < array.length; i++){  
        int randomPosition = generator.nextInt(array.length);  
        int temp = array[i];  
        array[i] = array[randomPosition];  
        array[randomPosition] = temp;  
      }  
    }  
  }  
 
  private static boolean isSorted(int[] array)  {  
    for (int i = 1; i < array.length; i++){
      if (array[i] < array[i - 1]) {
        return false;  
      }
    }
    return true;  
  }  
 
  public static void main(String[] args) {
    int [] array = {5,3,0,2,4,1,0,5,2,3,1,4}; 
    System.out.println("Before: " + Arrays.toString(array));
    bogoSort(array);
    System.out.println("After:  " + Arrays.toString(array));
  }
}



Hasil outputnya akan seperti dibawah ini :



Java Bogo Sort :


Before: [5, 3, 0, 2, 4, 1, 0, 5, 2, 3, 1, 4]

After:  [0, 0, 1, 1, 2,
2, 3, 3, 4, 4, 5, 5]