Sorting in Java

 Hello, there!

It must be boring for you guys to read what I have been posting every week. I'm sorry for my inability of writing an interesting blog :( But anyway, for this week, I actually get a new task about how sorting is performed in Java. So, yeah, here we go. There are 3 types of sorting that I'm going to talk about, which is Bubble Sort, Selection Sort, and Insertion Sort.

Right. One more thing. This blog will also be written in bahasa since my lecturer is going to read and score this. Hence, for those who don't speak bahasa but still are curious about this material, you are very welcome to scroll to the bottom and click the link that will send you to the source that I used.

Let's get started!

Bubble Sort

• Definisi

 Bubble sort merupakan salah satu algoritma yang cukup banak digunakan untuk menyusun data di Java. Penyusunan data yang dilakukan oleh Bubble Sort dilakukan secara rekursif dengan membandingkan angka yang bersebelahan dan menggesernya ke urutan lebih kecil atau lebih besar sesuai yang diinginkan. Pergeseran elemen ini akan berakhir jika semua elemen sudah selesai diurutkan sesuai urutan yang diinginkan. Nama "Bubble Sort" sendiri  diambil karena algoritma ini terlihat seperti elemennya bergeser layaknya gelembung.

    Sifat algoritma Bubble Sort adalah sebagai berikut:

1. Jumlah iterasi sama dengan banyaknya bilangan dikurang 1.
2. Di setiap iterasi, jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan.
3. Dalam algoritma Bubble Sort, meskipun deretan bilangan tersebut sudah terurut, proses sorting akan tetap dilakukan.
4. Tidak ada perbedaan cara yang berarti untuk teknik algoritma Bubble Sort ascending dan descending.

• Kelebihan dan Kekurangan

      Keuntungan dari penggunaan Bubble Sort pada Java, antara lain : (1) Kode program sangat mudah untuk ditulis dan dipahami. Biasanya, hanya memakan beberapa menit, (2) implementasinya juga termasuk mudah, (3) Bubble Sort menyimpan banyak memori karena ia mengurutkan nomor dan menyimpannya di dalam memori. 

    Namun, disamping kelebihan di atas, Bubble Sort juga mengalami beberapa kelemahan layaknya manusia. Kelemahan tersebut, antara lain : (1) Algoritma ini tidak sesuai dengan elemen data dengan jumlah yang sangat besar karena akan memakan banyak waktu. Waktu yang dibutuhkan untuk menyortir tiap elemen data meningkat secara eksponensial. (2) O(n^2) merupakan rata-rata kompleksitas dari Bubble Sort, sedangkan O(n) merupakan kompleksitas kasus terbaik (kasus terbaik adalah dimana semua elemennya sudah tersortir sejak awal).

• Kegunaan

      Karena Bubble Sort dapat mendeteksi error sesaat dalam pengurutan, maka algortima ini banyak digunakan dalam computer graphics. Bubble Sort juga digunakan dalam algoritma pengisian polygon dimana barisan vertikal dari sebuah polygon harus diurutkan. Bubble Sort merupakan algoritma yang stabil serta sederhana sehingga cocok untuk digunakan dalam mengurukan data yang berukuran kecil.

• Implementasi dan Dokumentasi

	import java.util.Scanner;
	public class BubbleSort
	{
	static void bubbleSort(int[] arraytest)
	{
	int n = arraytest.length; //nilai dari ukuran array diassign ke integer n
	int temp = 0; //variable sementara
	for(int i =0; i<n; i++)//loop pertama untuk melakukan beberapa iterasi
	{
	for(int j=1; j<n; j++)
	{
	if(arraytest[j-1] > arraytest[j]) //klau yang sebelah kiri lebih besar
	{
	//tukar tempat dengan yang sebelah kanan
	temp = arraytest[j-1]; //masukan bilangan yang lebih besar ke variable temp
	arraytest[j-1] = arraytest[j]; //yang lebih kecil digeser ke kiri
	arraytest[j] = temp; //yang lebih besar geser ke kanan
	}
	}
	}
	}
	public static void main (String[] args)
	{
	int arraytest[] = {23, 16, 3, 42, 75, 536, 61}; //isi value ke dalam array
	System.out.println("Array Before Doing Bubble Sort");
	for(int i=0; i<arraytest.length; i++)
	{
	System.out.println(arraytest[i] + " ");
	}
	System.out.println();
	bubbleSort(arraytest); //diurutkan elemennya
	System.out.println("Array After Doing Bubble Sort");
	for(int i=0; i<arraytest.length; i++)
	{
	System.out.println(arraytest[i] + " ");
	}
	}
	}

view raw BubbleSort.java hosted with ❤ by GitHub

Selection Sort

• Pengertian

        Selection Sort pada Java merupakan salah satu metode pengurutan data yang secara terus-menerus mencari elemen terkecil dan meletakannya pada awal elemen (untuk pengurutan data dari kecil ke yang lebih besar). Proses ini akan terus diulang sampai array yang dimasukkan sudah urut. 

          Pada Selection Sort, array yang diinput akan dibagi menjadi 2 bagian atau 2 subarray, yaitu :

• Subarray terurut untuk menyimpan elemen yang sudah diurutkan
• Subarray tidak terurut untuk menyimpan array yang belum diurutkan

            Sifat algoritma Selection Sort adalah sebagai berikut:

1. Atur pointer minimum (MIN) ke lokasi 0
2. Mencari elemen terkecil dari daftar elemen yang terdapat dalam array
3. Tukar elemen minimum ke lokasi atau posisi nol
4. Pindahkan pointer MIN ke posisi berikutnya
5. Proses ini dilakukan terus-menerus hingga seluruh elemen array sudah terurut.

• Kelebihan dan Kekurangan

      Pada kasus terbaik, kompleksitas performansi dari Selection Sort adalah O(n^2). Ternyata, kompleksitas ini juga berlaku untuk kasus rata-rata, maupun kasus terburuknya. Selection Sort tidak dapat bekerja secara efisien pada daftar dengan jumlah data yang besar karena mengkonsumsi waktu lebih untuk perbandingan.

• Kegunaan

          Selection sort mungkin merupakan pengurutan data dengan waktu terlama bila dibandingkan dengan sistem pengurutan lainnya. Namun, Selection Sort dapat menjadi pilihan untuk mengurutkan data yang sudah berurutan. Selection Sort juga dapat digunakan ketika sisa memori terbatas. Hal ini dikarenakan Selection Sort tidak menukar dan menggeser elemen-elemennya sampai ke elemen terakhir seperti sistem pengurutan lainnya, sehingga penggunaan memorinya lebih sedikit.

• Implementasi dan Dokumentasi

	import java.util.*;
	public class SelectionSort
	{
	public static void main (String[] args)
	{
	int n, i, j, tempvar;
	Scanner sc = new Scanner(System.in); //Ngescan sesuatu atau meminta input dari user
	System.out.println("Masukan ukuran dari array: \n");
	n = sc.nextInt();
	int array[] = new int[n]; //menginisialisasi array dengan ukuran n (input user)
	System.out.print("Masukkan elemen yanggg akan dimasukan ke dalam array: \n");
	//Masukan elemen ke dalam arraynya
	for(i=0; i<n; i++)
	{
	array[i] = sc.nextInt();
	}
	System.out.println("isi array sebelum disorting adalah : \n" + Arrays.toString(array));
	//dibawah ini merupakan selection shortnya
	for(i=0; i<n; i++)
	{
	for(j=i+1; j<n; j++) //membandingkan elemen pertama dengan elemen setelahnya
	{
	if(array[i]>array[j])//jika elemen pertama lebih besar dari elemen-elemen setelahnya
	{
	tempvar = array[i];
	array[i] = array[j];
	array[j] = tempvar;
	}
	}
	}
	System.out.println("Isi array setelah disorting adalah :\n");
	for(i=0; i<n; i++)
	{
	System.out.print(array[i] + " ");
	}
	}
	}

view raw SelectionSort.java hosted with ❤ by GitHub

Insertion Sort

• Pengertian

           Insertion Sort merupakan salah satu jenis sort yang mirip seperti saat kalian melakukan pengurutan kartu remi di tangan. Algoritma ini dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Ide dasar dari algoritma ini adalah mencari tempat yang “tepat” untuk setiap elemen array.

Secara umum, langkah-langkah algoritma insertion sort adalah sebagai berikut.

1. Ambil elemen dari array ke-i.
2. Taruh di urutan sebelumnya ( arr[ …i-1] ) yang telah diurutkan di tempat yang sesuai.

• Kelebihan dan Kekurangan           

          Kasus terbaik pada Insertion Sort adalah ketika semua elemen pada array sudah dalam urutan yang tepat. Hal ini disebabkan karena ketika setiap elemen dibandingkan dengan elemen yang paling kiri, elemen tersebut selalu lebih besar sehingga tidak ada proses penukaran maupun pemindahan elemen yang dilakukan. Dalam kasus ini, kompleksitas kasus akan menjadi liner, yaitu O(n). 

            Namun, apabila semua elemen pada array berada pada urutan yang terbalik, maka itu akan menjadi kasus terburuk bagi Insertion Sort. Setiap saat sebuah elemen dibandingkan dengan elemen paling kiri, elemennya akan selalu lebih kecil dan mengharuskan pemindahan dan penukaran elemen setiap dilakukan perbandingan. Hal ini akan menyebabkan kompleksitas kasusnya menjadi O(n^2).  

        Sedangkan pada kasus rata-rata atau yang umum terjadi, kompleksitas kasus Insertion Sort adalah O(n^2) dimana beberapa elemen tidak membutuhkan penukaran dan penggeseran, namun beberapa memerlukan.

       Keuntungan dari penggunaan Insertion Sort adalah mudah untuk diimplementasikan. Selain itu, semakin terurut arraynya, kompleksitas kasusnya akan semakin mendekati linear. Namun, ada beberapa kekurangannya juga, antara lain : (1) Tidak cocok untuk data dengan jumlah yang besar, dan (2) kompleksitasnya masih polynomial pada kasus terburuk.

• Kegunaan

          Insertion Sort mungkin bukan merupakan algoritma paling efisien, namun kelebihannya ada pada sifat sederhananya. Algoritma ini cocok untuk digunakan pada aplikasi kecil dengan jumlah elemen data di bawah 50.  Untuk aplikasi kecil dan trivial, Insertion Sort dapat dikatakan cukup cepat, bahkan lebih cepat daripada Quick Sort. Selain itu, Insertion Sort juga akan bekerja jauh lebih baik pada array dengan elemen yang sudah terurut sebelumnya.

• Implementasi dan Dokumentasi

	import java.util.*;
	public class InsertionSort
	{
	public static void InsertionSort (int arr[])
	{
	for(int j=1; j<arr.length; j++)
	{
	int key = arr[j];
	int i =j-1;
	while((i>-1) && (arr[i]>key))
	{
	arr[i+1] = arr [i];
	i--;
	}
	arr[i+1] = key;
	}
	}
	static void printArray (int arr[])
	{ //digunakan untuk ngeprint elemen yang ada dalam array
	int len = arr.length;
	for(int i=0; i<len; i++)
	{
	System.out.println(arr[i] + " ");
	System.out.println();
	}
	}
	public static void main (String args[])
	{
	int[] arr1 = {21, 18, 15, 23, 52, 12, 61};
	//panggil fungsi untuk ngesort elemennya
	InsertionSort(arr1);
	//panggil fungsi untuk ngeprint elemen
	printArray(arr1);
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub