Tugas 3, Konsep Sorting

 Tugas 3

KONSEP SORTING

1. BUBBLE SORT

Fungsi algoritma ini adalah untuk mengurutkan data dari yang terkecil ke yang terbesar (ascending) atau sebaliknya (descending). 

Source code: 

	import java.util.Scanner;
	public class BubbleSort {
	static void bubbleSort(int[] arraytest) {
	int n = arraytest.length; //length of the array is initialized to the integer n
	int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
	for(int i=0; i < n; i++){ // first for loop performs multiple iterations
	for(int j=1; j < (n-i); j++){
	if(arraytest[j-1] > arraytest[j]){ // if loop compares the adjacent numbers
	// swaps the numbers
	temp = arraytest[j-1]; // assigns the greater number to temp variable
	arraytest[j-1] = arraytest[j]; // shifts the lesser number to the previous position
	arraytest[j] = temp; // bigger number is then assigned to the right hand side
	}
	}
	}
	}
	public static void main(String[] args) {
	int arraytest[] ={23,16,3,42,75,536,61}; // defining the values of array
	System.out.println("Array Before Doing Bubble Sort");
	for(int i=0; i < arraytest.length; i++){ // for loop used to print the values of array
	System.out.print(arraytest[i] + " ");
	}
	System.out.println();
	bubbleSort(arraytest); // array elements are sorted using bubble sort function
	System.out.println("Array After Doing Bubble Sort");
	for(int i=0; i < arraytest.length; i++){
	System.out.print(arraytest[i] + " "); // for loop to print output values from array
	}
	}
	}

view raw Bubble Sort hosted with ❤ by GitHub

output:

Kelebihan algorima Bubble Sort adalah mudah dipahami dan sistem kerjanya simpel. Kekurangannya jika jumlah datanya banyak, maka akan memakan waktu yang lebih lama dalam proses pengurutannya.

2. SELECTION SORT

Selection Sort adalah perbaikan dari algoritma bubble sort, dengan mengurangi jumlah perbandingan. Dikatakan selection sort karena algoritma ini mencoba memilih satu per satu elemen data dari posisi awal, untuk mencari data paling kecil dengan mencatat posisi index-nya saja, lalu dilakukan pertukaran hanya sekali pada akhir setiap tahapan.

Source code: 

	import java.util.*;
	public class SelectionSort {
	//Method that implements Selectionsort
	public static void selsort(int[] arr)
	{
	int n=arr.length; //length of the array
	for(int i=0;i<n-1;i++)
	{
	int MIN=i; //set the first position as minimum
	System.out.println("Sorting based on Number "+(i+1));
	//Find the smallest element by comparing with the element in MIN position
	for(int j=i+1;j<n;j++)
	{
	System.out.println("Comparing "+ arr[MIN] + " and " + arr[j]);
	if(arr[j]<arr[MIN])
	{
	System.out.println(arr[MIN] + " is greater than " + arr[j] );
	MIN=j;
	}
	}
	//Swap the smallest element with element in MIN position
	int temp=arr[i];
	arr[i]=arr[MIN];
	arr[MIN]=temp;
	}
	}
	public static void main(String[] args) {
	int[] arr= {15,21,6,3,19,20}; // input array
	System.out.println("Elements in the array before Sorting: "+ Arrays.toString(arr));
	selsort(arr);//calling the selection sort method
	System.out.println("Elements in the array after Sorting: "+Arrays.toString(arr));
	}
	}

view raw Selection Sort hosted with ❤ by GitHub

output:

Kelebihan Algoritma ini sangat rapat dan mudah untuk diimplementasikan, Operasi pertukarannya hanya dilakukan sekali saja . Waktu pengurutan dapat lebih ditekan .Mudah menggabungkannya kembali .Kompleksitas selection relative lebih kecil.

Kekurangannya adalah sulit dalam membagi masalah

3. INSERTION SORT

Fungsi Algoritma insertion sort adalah untuk mengurutkan sebuah array data yang tidak terurut agar menjadi sebuah array yang terurut. Algoritma insertion sort adalah algoritma pengurutan yang menggunakan dua buah list untuk proses pengurutannya. dua list tersebut yaitu yaitu sorted list dan unsorted list.

Source code: 

	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[]) {
	int len = arr.length;
	//simple for loop to print the elements of sorted array
	for (int i= 0; i<len; i++)
	System.out.print(arr[i] + " " );
	System.out.println();
	}
	public static void main(String args[]){
	int[] arr1 = {21,18,15,23,52,12,61};
	System.out.println("Array before insertion sort:");
	printArray(arr1);
	//calling the sort function which performs insertion sort
	insertionSort(arr1);
	//calling the printArray function which performs printing of array
	System.out.println("Array after insertion sort:");
	printArray(arr1);
	}
	}

view raw Insertion Sort hosted with ❤ by GitHub

output:

Kelebihan

1.Sederhana dalam penerapannya.
2.Mangkus dalam data yang kecil.
3.Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.
4.Mangkus dalam data yang sebagian sudah terurut.
5.Lebih mangkus dibanding Bubble Sort dan Selection Sort.
6.Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.
7.Stabil.

Kekurangan

1.Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
2.Untuk larik yang jumlahnya besar ini tidak praktis.
3.Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
4.Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.