Java Sorting Algorithms

1) Bubble Sort

	/**
	*
	*/
	package com.algorithms.sorting;
	import java.util.ArrayList;
	import java.util.List;
	/**
	* @author Kiran Kanaparthi
	*
	* This class sorts the input using BubbleSort
	* We start the beginning of the array, and swap the
	* first two elements, if the first is greater than the
	* second, Then We go the next pair, and make swaps as needed
	* until the Array is sorted.
	*
	*/
	public class BubbleSort {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	BubbleSort bubbleSort = new BubbleSort();
	int[] input = new int[]{3,5,7,2,8,9,1};
	System.out.println(" Before Sorting the Elements are ");
	if(input!=null) {
	for(int inputElemenet : input) {
	System.out.print(" "+ inputElemenet);
	}
	}
	input = bubbleSort.bubbleSortElements(input);
	System.out.println("\n\n\n After Sorting the Elements are ");
	if(input!=null) {
	for(int inputElemenet : input) {
	System.out.print(" "+ inputElemenet);
	}
	}
	String in ="abc";
	List<String> allPermutations = bubbleSort.
	printAllPermutations("",in,new ArrayList<String>());
	System.out.println("\n=====================================\n");
	if(allPermutations!=null) {
	allPermutations.forEach(elem->System.out.println(" "+elem));
	}
	}
	private List<String> printAllPermutations(String prefix,String suffix,
	List<String> allStrings) {
	if(suffix==null || suffix.length()==0) {
	allStrings.add(prefix+suffix);
	} else {
	for(int i=0;i<suffix.length();i++) {
	String s = suffix.substring(0, i)+
	suffix.substring(i+1,suffix.length());
	printAllPermutations(prefix+suffix.charAt(i),
	s,allStrings);
	}
	}
	return allStrings;
	}
	/**
	*
	* @param input
	* @return
	*/
	private int[] bubbleSortElements(int input[]) {
	if(input!=null) {
	for(int i=0;i<input.length-1;i++) {
	for(int j=0;j<input.length-1-i;j++) {
	// System.out.println("\n input[j] "+ input[j]
	// +" input[j+1] "+input[j+1]+" j "+j);
	if(input[j]>input[j+1]) {
	int temp = input[j+1];
	input[j+1] = input[j];
	input[j] = temp;
	}
	}
	System.out.println("\n After Each Iteration, the Elements are ");
	if(input!=null) {
	for(int inputElemenet : input) {
	System.out.print(" "+ inputElemenet);
	}
	}
	}
	}
	return input;
	}
	}

view raw BubbleSort.java hosted with ❤ by GitHub

2) Selection Sort

	/**
	*
	*/
	package com.algorithms.sorting;
	import java.util.Arrays;
	/**
	* @author Kiran Kanaparthi
	*
	* This class performs Selection Sort.
	* It starts with the one element in the
	* outer loop is chosen as a current Minimum.
	* Then in the Inner loop compare the currentMinimum
	* with every other element, if there is a lesser element
	* that the current minimum, mark that as the element
	* as the current minimum.
	* For each iteration of the outer loop,
	* After the inner loop is completed, compare if the updated
	* current minimum is the same as the initially chosen currentMinimum
	* , if they are not the same swap the two elements.
	*
	*/
	public class SelectionSort {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	SelectionSort selectionSort = new SelectionSort();
	int[] input = new int[]{3,4,1,5,10,9,8};
	// input = selectionSort.selectionSort(input);
	//
	// System.out.println(" After Sorting of the Elements is ");
	//
	// if(input!=null) {
	// for(int elem : input) {
	// System.out.print(" "+ elem);
	// }
	// }
	System.out.println(" After Sorting of the Elements Again is ");
	input = selectionSort.makeSelectionSort(input);
	System.out.println("Array Elements "+ Arrays.toString(input));
	}
	/**
	* This method makes the selection sort
	* of the elements
	*
	* @param input
	* @return
	*/
	private int[] makeSelectionSort(int input[]) {
	if(input!=null) {
	System.out.println(" input.length "+input.length);
	for(int i=0;i<input.length;i++) {
	int minIndex = i;
	int minValue = input[minIndex];
	// 3 4 1 5 10 9 8
	for(int j=i;j<input.length;j++) {
	if(input[j]<input[minIndex]) {
	minValue = input[j];
	minIndex = j;
	}
	}
	//After each iteration of the loop, if the minValue is not the
	//same as first minElement, swap the elements.
	if(minValue<input[i]) {
	int temp = input[i];
	input[i] = input[minIndex];
	input[minIndex] = temp;
	}
	}
	}
	return input;
	}
	}

view raw SelectionSort.java hosted with ❤ by GitHub

3) Insertion Sort

Insertion sort is inserting the element at the right place, such that all the elements to the left are less than the element, and all the elements to the right are after the element, the same technique used to play card game.

	/**
	*
	*/
	package com.algorithms.sorting;
	/**
	* @author Kiran Kanaparthi
	*
	* This class Does the Insertion Sorting on the
	* Given Array.
	*
	* The Array is traversed from left to right, at each step
	* one Key Value is chosen in the outer loop.
	*
	* In the Inner Loop, Start Iterating from the Element at the
	* Key Index, and compare the Key with Every Element in the
	* Array up to index 0, If they are not in order, the consecutive
	* elements are swapped(key values does not change, and is used
	* for comparisons only)
	*
	*/
	public class InsertionSort {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	InsertionSort insertionSort = new InsertionSort();
	System.out.println(" Before calling insertion sort");
	int[] elements = new int[]{5,4,1,3,2,7,0,5};
	insertionSort.insertionSort(elements);
	System.out.println(" The insertion sort elements are as follows ");
	if(elements!=null && elements.length>0) {
	for(int element: elements) {
	System.out.print(" "+element);
	}
	}
	}
	//5 4 1 3 2 7
	/**
	*
	* @param input
	* @return
	*/
	private int[] insertionSort(int[] input) {
	int temp=0,key=0;
	if(input!=null && input.length>0) {
	for(int i=1;i<input.length;i++) {
	int j = i-1;
	key = input[i];
	while(j>=0 && key<input[j]) {
	temp = input[j];
	input[j] = input[j+1];
	input[j+1] = temp;
	j--;
	}
	}
	}
	return input;
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub

4) Merge Sort

	/**
	*
	*/
	package com.algorithms.sorting;
	/**
	* @author kkanaparthi
	*
	* This class sorts the input data using
	* mergeSort of the Input Data
	* Merge sort uses Divide and Conquer strategy to
	* divide the Initial Array into one element of each, sorts them
	* before merging them back to the array
	*
	*/
	public class MergeSort {
	/**
	* This method performs the mergeSort
	* of the input data recursively
	*
	* @param input
	* @return
	*/
	private int[] mergeSort(int[] input,int low,int high) {
	int middle = (low+high)/2;
	if(low<high) {
	mergeSort(input, low, middle);
	mergeSort(input, middle+1, high);
	merge(input, low,middle,high);
	}
	return input;
	}
	/**
	* This method does the merge Step of merging
	* the sub arrays
	*/
	private void merge(int array[], int low,int middle,int high) {
	//find size of two arrays to be merged
	int n1 = middle-low+1;
	int n2 = high-middle;
	//create temp arrays with the size
	int leftArray[] = new int[n1];
	int rightArray[] = new int[n2];
	//Copy the Data to the Temp Arrays
	for(int i=0;i<n1;++i) {
	leftArray[i] = array[low+i];
	}
	for(int j=0;j<n2;++j) {
	rightArray[j] = array[middle+1+j];
	}
	//Merge the Temp Arrays
	//Initial Index of the first and second sub Arrays
	int i=0,j=0;
	//Initial Index of the merged SubArray
	int k = low;
	while(i<n1 && j<n2) {
	if(leftArray[i]<=rightArray[j]) {
	array[k] = leftArray[i];
	i++;
	} else {
	array[k] = rightArray[j];
	j++;
	}
	//either case increase the index of k, as the element gets copied any way
	k++;
	}
	//copy the remaining elements of leftArray
	while(i<n1) {
	array[k] = leftArray[i];
	i++;
	k++;
	}
	//copy the remaining elements of rightArray
	while(j<n2) {
	array[k] = rightArray[j];
	j++;
	k++;
	}
	}
	/**
	* @param args
	*/
	public static void main(String[] args) {
	MergeSort mergeSort = new MergeSort();
	int[] input = new int[]{3,4,5,1,2,7,6,8};
	int[] result = mergeSort.mergeSort(input,0,input.length-1);
	if(result!=null && result.length>0) {
	for(int elem : result) {
	System.out.print(" "+elem);
	}
	}
	}
	}

view raw MergeSort.java hosted with ❤ by GitHub

5) Quick Sort

	/**
	*
	*/
	package com.algorithms.sorting;
	/**
	* @author kkanaparthi
	*
	* This class performs the sorting of the elements
	* using QuickSort
	*
	* QuickSort chooses a Pivot Element, and sorts the
	* elements on both sides of the Pivot such that the
	* elements less than the pivot are on the left side, and
	* the elements greater than the pivot are to the right side
	*
	*/
	public class QuickSort {
	/**
	* This method does the quick sort recursively
	*
	* @return
	*/
	private int[] quickSort(int input[],int left,int right) {
	int index = partition(input,left,right);
	if(left<index-1) {
	//Sort left half of the Array
	quickSort(input, left, index-1);
	}
	if(index<right) {
	//Sort right half of the Array
	quickSort(input, index, right);
	}
	return input;
	}
	/**
	* This method performs the Partition
	* @return
	*/
	private int partition(int []array,int left,int right) {
	//pick a pivot element
	int pivot = array[(left+right)/2];
	while(left<=right) {
	//find element on left side that should be on the right side
	while(array[left]<pivot) {
	left++;
	}
	while(array[right]>pivot) {
	right--;
	}
	//swap the elements, and move the left and right indices
	if(left<=right) {
	swap(array,left,right);
	left++;
	right--;
	}
	}
	return left;
	}
	/**
	* This method performs the swapping of the elements
	*
	* @param array
	* @param left
	* @param right
	*/
	private void swap(int[] array,int left,int right) {
	int temp = array[left];
	array[left] = array[right];
	array[right] = temp;
	}
	/**
	* @param args
	*/
	public static void main(String[] args) {
	QuickSort quickSort = new QuickSort();
	int[] input = new int[]{3,4,5,1,25,7,6,9};
	int [] results = quickSort.quickSort(input,0,input.length-1);
	if(results!=null && results.length>0) {
	for(int i : results) {
	System.out.print(" "+i);
	}
	}
	}
	}

view raw QuickSort.java hosted with ❤ by GitHub

6) Bucket Sort


7) Radix Sort