InstanceOfJava: java sorting algorithms

Merge sort algorithm in java with example program

Posted by: Instanceofjava Posted date: August 20, 2016 / comment : 0 java programming interview questions , java sorting algorithms

Merge sort one of the recursive sorting algorithm.
First divide the list of unsorted elements in two two parts. left half and right half.

Divide the left part elements in to sub lists until it become single element.
Divide right half of array or list of elements in to sub lists until it becomes one element in list.
After dividing all elements in two parts in to single entity.
Merge the elements into two by comparing lesser element will be first. apply same at right half
Merge all the elements in the left part until it become single sorted list
Now we have two sorted parts.
Means two parts sorted in ascending order and smaller element will be in first position.
Compare fist elements of two parts , lesser one should be takes first place in new sorted list
New sorted list or array having only one element now.
Compare two lists elements and place in sorting order and merge it.
Finally we have all elements sorted.
Compared to remaining algorithms like selection sort, insertion sort and bubble sort merge sort works faster.
Lets see what will be the time complexity of merge sort algorithm.

Time complexity of merge sort algorithm:

1.Best case time complexity: O(n log (n))
2.Average case time complexity: O(n log (n))
3.Worst case time complexity: O(n log (n))
4.Worst case space complexity: O(n)

Merge sort in java with explanation diagram

Program#1: Java program to implement merge sort algorithm data structure

package com.instanceofjava.mergesortalgorithm;
public class MergeSortAlgorithm {
private int[] resarray;
private int[] tempMergArray;
private int length;
public static void main(String a[]){
int[] inputArr ={6,42,2,32,15,8,23,4};
System.out.println("Before sorting");
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
MergeSortAlgorithm mergesortalg = new MergeSortAlgorithm();
mergesortalg.sort(inputArr);
System.out.println();
System.out.println("After sorting");
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
}
public void sort(int inputArray[]) {
this.resarray = inputArray;
this.length = inputArray.length;
this.tempMergArray = new int[length];
doMergeSort(0, length - 1);
}
private void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
//to sort left half of the array
doMergeSort(lowerIndex, middle);
// to sort right half of the array
doMergeSort(middle + 1, higherIndex);
//merge two halfs
mergehalfs(lowerIndex, middle, higherIndex);
}
}
private void mergehalfs(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArray[i] = resarray[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArray[i] <= tempMergArray[j]) {
resarray[k] = tempMergArray[i];
i++;
} else {
resarray[k] = tempMergArray[j];
j++;
}
k++;
}
while (i <= middle) {
resarray[k] = tempMergArray[i];
k++;
i++;
}
}
}

Output:

Before sorting
6 42 2 32 15 8 23 4
After sorting
2 4 6 8 15 23 32 42

Insertion sort algorithm in java programming

Posted by: Instanceofjava Posted date: August 20, 2016 / comment : 0 java programming interview questions , java sorting algorithms

Sorting means arranging elements of a array or list in ascending or descending order.
We have various sorting algorithms in java.

Iterative and recursive algorithms.
Insertion sort is iterative type of algorithm.
Insertion sort algorithm is in place algorithm
The basic idea behind insertion sort is to divide our list in to two parts , sorted and un sorted.
At each step of algorithm a number is moved from un sorted part to sorted part.
Initially take 1st element as sorted element.
Noe take second element and compare with first element if it less than the 1st element then swap two numbers means place lesser value in first position.
So now have two elements in sorted part. Take third element and compare with second element if it is less than the second element then we need to compare it with 1st element if is less than first element we need keep that in first place. Take an element from unsorted portion and compare with sorted portion and place it in correct position in order to make sorted.
This will be repeated until entire list will be sorted.

Time complexity of Insertion sort:

1.Best case time complexity: O(n²)
2.Average case time complexity: O(n²)
3.Worst case time complexity: O (n²)
4.Worst case space complexity: O(1)

Implementation of Insertion sort algorithm in java

Program #1: Write a java example program on insertion sort algorithm.

package com.instanceofjava.insertionsortalgorithm;
public class InsertionSort {
/**
* @website: www.instanceofjava.com
* @category: insertion sort algorithm in java
*/
public static int[] doInsertionSort(int[] array){
int temp;
for (int i = 1; i < array.length; i++) {
for(int j = i ; j > 0 ; j--){
if(array[j] < array[j-1]){
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
return array;
}
static void printArray(int[] inputarray){
for(int i:inputarray){
System.out.print(i);
System.out.print(", ");
}
System.out.println();
}
public static void main(String a[]){
int[] array = {16,12,3,11,9,21,5,6};
System.out.println("Before sorting elements");
printArray(array);
int[] resarray = doInsertionSort(array);
System.out.println("After sorting elements");
printArray(array);
}
}

Output:

Before sorting elements
16, 12, 3, 11, 9, 21, 5, 6,
After sorting elements
3, 5, 6, 9, 11, 12, 16, 21,

Implementation of selection sort algorithm in java with Example program

Posted by: Instanceofjava Posted date: August 17, 2016 / comment : 0 java programming interview questions , java sorting algorithms

Selection sort algorithm is to arrange unsorted elements in to sorting order with increasing or decreasing order.
To sort list of unsorted list of elements first it will search for minimum value in the list and place it in first index.

Now first place is fixed with smallest value in the list now it starts from second element and compare next element and if it is big it compares next element if it is small it picks that element and compares with next element.
So again it picks smallest element in the list and place it in second place. This procedure will repeat until it reaches n-1 position.

Time complexity of selection sort algorithm:

1.Best case time complexity: O(n²)
2.Average case time complexity: O (n²)
3.Worst case time complexity: O (n²)

Program #1: Write a Java example program to sort unsorted elements in ascending order using selection sort algorithm

package com.java.sortingalgorithms;
public class SelectionSortInJava {
public static int[] selectionSortArray(int[] array){
for (int i = 0; i < array.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < array.length; j++)
if (array[j] < array[index])
index = j;
int minimumNumber = array[index];
array[index] = array[i];
array[i] = minimumNumber;
}
return array;
}
public static void main(String a[]){
int[] array = {12,24,6,56,3,9,15,41};
System.out.println("Before sorting");
for(int i:array){
System.out.print(i);
System.out.print(", ");
}
int[] resultarr = selectionSortArray(array);
System.out.println("\nAfter sorting");
for(int i:resultarr){
System.out.print(i);
System.out.print(", ");
}
}
}

Output:

Before sorting
12, 24, 6, 56, 3, 9, 15, 41,
After sorting
3, 6, 9, 12, 15, 24, 41, 56,

Implementation of Selection Sort algorithm

Quicksort algorithm in java with example program

Posted by: Instanceofjava Posted date: August 16, 2016 / comment : 1 Core java Interview Questions , java programming interview questions , java sorting algorithms

Quick sort uses divide and conquer algorithm.
First will be divided in to two parts based on some pivot element. All elements which are less than pivot element will be placed left and and all elements which are greater than pivot will be in right part.

So now pivot element is exactly in middle. if we sort left and right side elements all elements will be sorted. Here recursive quick sort will take place in order to sort all elements.
Quick sort will be sorting these elements without using extra space that is the reason it is called in place sorting algorithm.
Using the first or middle elements as an pivot element. it splits the arrays by re arranging the elements like every thing that is less than pivot will come left side and all elements greater than or equal to pivot will come right side.
Now pivot is in middle and correct place it left and right arrays sorted then entire array will be sorted.
Quick sort exactly will do the same it will sort left and right recursively.
If size of input is very less merge sort will be time consuming.
For smaller inputs quick sort is faster than merge sort.
Time complexity of Quicksort default case is O(n log n).
Worst case Time complexity of Quicksort is O(n²).

Steps to implement quick sort algorithm:

Create a array with some elements. Choose pivot element as middle element. we can choose first or last also.
After choosing pivot element arrange the elements like all elements which are less than pivot value comes left side and elements greater than equal to pivot come right side of pivot.
And then apply same to both sides. until it becomes one. then all elements in array will be sorted.

Program #1: Java Example program to sort elements of array using quick sort algorithm:

package quicksortjava;
public class QuickSort {
private int array[];
private int length;
public void sortElements(int[] arrayvalues) {
if (arrayvalues == null || arrayvalues.length == 0) {
return;
}
this.array = arrayvalues;
length = arrayvalues.length;
doQuickSort(0, length - 1);
}
private void doQuickSort(int lowIndex, int highIndex) {
int i = lowIndex;
int j = highIndex;
int pivot = array[lowIndex+(highIndex-lowIndex)/2];
// now Divide the array into two arrays(actually we are maintaining single array only)
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapElements(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowIndex < j){
doQuickSort(lowIndex, j);
}
if (i < highIndex){
doQuickSort(i, highIndex);
}
}
private void swapElements(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
QuickSort quicksort = new QuickSort();
int[] inputarray = {32,1,23,14,43,7,6,65};
System.out.println("Before sorting");
for(int i:inputarray){
System.out.print(i);
System.out.print(" ");
}
quicksort.sortElements(inputarray);
System.out.println("After sorting");
for(int i:inputarray){
System.out.print(i);
System.out.print(" ");
}
}
}

Output:

Before sorting
32 1 23 14 43 7 6 65
After sorting
1 6 7 14 23 32 43 65

Execution flow explanation of quick sort algorithm

quick sort program in java using recursion program

Subscribe to: Comments ( Atom )