# Category Archives: Sorting Algorithms

Implementation of Sorting Algorithms in Java with Source code and Time Complexity

## Mergesort using ArrayList in Java with example

So here is another sorting algorithm, “Merge Sort” which I have implemented it using ArrayList.

MergeSort follows the Divide and Conquer paradigm.

Divide part divides an unsorted array into 2 unsorted arrays till further division is not possible i.e there is only 1 element per array. So we need to divide an array of N element into N arrays of size 1 (Virtually).

Conquer part join 2 divided arrays into one array which is sorted. So we need to merge element from N array to 1 array having all element in sorted order.

Diving the array will take O(log n) time and will create log n level of sub arrays.
Conquer part at each level will merge 2 sorted arrays which takes O(n) at each level.
So worst case time taken by merge sort is O(n log n).
Merge sort is not considered to be a memory efficient as we need an extra memory at each level of merging. As you can see in the implementation example that is given here it needs an extra temporary array called : mergedSortedArray to store the temp sorted element.

Here is the source code and project structure for the MergeSort.

Project Structure

MergeSort.java

```package daa;

import java.util.ArrayList;

public class MergeSort {
private ArrayList<Integer> inputArray;

public ArrayList<Integer> getSortedArray() {
return inputArray;
}

public MergeSort(ArrayList<Integer> inputArray){
this.inputArray = inputArray;
}

public void sortGivenArray(){
divide(0, this.inputArray.size()-1);
}

public void divide(int startIndex,int endIndex){

//Divide till you breakdown your list to single element
if(startIndex<endIndex && (endIndex-startIndex)>=1){
int mid = (endIndex + startIndex)/2;
divide(startIndex, mid);
divide(mid+1, endIndex);

//merging Sorted array produce above into one sorted array
merger(startIndex,mid,endIndex);
}
}

public void merger(int startIndex,int midIndex,int endIndex){

//Below is the mergedarray that will be sorted array Array[i-midIndex] , Array[(midIndex+1)-endIndex]
ArrayList<Integer> mergedSortedArray = new ArrayList<Integer>();

int leftIndex = startIndex;
int rightIndex = midIndex+1;

while(leftIndex<=midIndex && rightIndex<=endIndex){
if(inputArray.get(leftIndex)<=inputArray.get(rightIndex)){
leftIndex++;
}else{
rightIndex++;
}
}

//Either of below while loop will execute
while(leftIndex<=midIndex){
leftIndex++;
}

while(rightIndex<=endIndex){
rightIndex++;
}

int i = 0;
int j = startIndex;
//Setting sorted array to original one
while(i<mergedSortedArray.size()){
inputArray.set(j, mergedSortedArray.get(i++));
j++;
}
}
}
```

MainPractise.java

```import java.util.ArrayList;
import daa.MergeSort;

public class MainPractise implements Cloneable {

public static void main(String[] args) {

ArrayList<Integer> unsortedArray = new ArrayList<Integer>();

MergeSort ms = new MergeSort(unsortedArray);

System.out.println("---------Initial Unsorted Array---------");
for(int i:ms.getSortedArray()){
System.out.print(i+" ");
}

ms.sortGivenArray();

System.out.println("\n------------Sorted Array------------");
for(int i:ms.getSortedArray()){
System.out.print(i+" ");
}
}
}```

Output:

———Initial Unsorted Array———
8  7  6  5  4  0  2
————Sorted Array————
0  2  4  5  6  7  8

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Selection Sort using ArrayList (Inplace) in Java

One more simple form of sorting algorithm is Selection Sort.

For in-place implementation in java, starting from 1st index, find the smallest element (takes O(n) ) and put it at the first index of unsorted sub array. So there will be 2 parts of main array, left one will have sorted element and right one will have unsorted. We choose smallest from the right one and will put it at the beginning of the unsorted sub array. Now Sorted array will have one more element and unsorted array will have one less. Continue this process till we reach the end of element. ( takes O(n)).
So finding smallest for one loop will take O(n) and there will be at most n loop so it total time in worst case will be O(n^2)

SelectionSort.java

```package daa;

import java.util.ArrayList;

public class SelectionSort {

private ArrayList<Integer> inputArray = new ArrayList<Integer>();

//Just To fetch display purpose
public ArrayList<Integer> getSortedArray() {
return inputArray;
}

public SelectionSort(ArrayList<Integer> inputArray){
this.inputArray = inputArray;
}

public void sortGivenArray(){

int smallInt = 0;
int j=0;
int smallIntIndex = 0;

for(int i=1;i<inputArray.size();i++){

smallInt = inputArray.get(i-1);
smallIntIndex = i-1;

for(j=i;j<inputArray.size();j++){
if(inputArray.get(j)<smallInt){
smallInt = inputArray.get(j);
smallIntIndex = j;
}
}

//Swap the smallest element with the first element of unsorted subarray
swap(i-1, smallIntIndex);
}
}

public void swap(int sourceIndex,int destIndex){
int temp = inputArray.get(destIndex);
inputArray.set(destIndex, inputArray.get(sourceIndex));
inputArray.set(sourceIndex, temp);
}

}
```

MainPractise.java

```import java.util.ArrayList;
import daa.SelectionSort;

public class MainPractise implements Cloneable {

public static void main(String[] args) {

ArrayList<Integer> unsortedArray = new ArrayList<Integer>();

SelectionSort ss = new SelectionSort(unsortedArray);

System.out.println("---------Initial Unsorted Array---------");
for(int i:ss.getSortedArray()){
System.out.print(i+" ");
}

ss.sortGivenArray();

System.out.println("\n------------Sorted Array------------");
for(int i:ss.getSortedArray()){
System.out.print(i+" ");
}
}
}```

Output:

———Initial Unsorted Array———
8 7 6 5 4 0 2
————Sorted Array————
0 2 4 5 6 7 8

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## QuickSort implementation example using ArrayList in Java

So here is another sorting algorithm, “Quick Sort” which I have implemented it using ArrayList which is inplace sorting algorithm.
Worst case for quick sort to run is O (n^2).

Implementing Quick Sort using divide & conquer technique.
Our divide part will have partitioning of array into 2 array where each element from left side of array will be smaller then the each element from the right side of array. This partitioning will be based on one element that we choose in each iteration is called PIVOT element.

Our conquer part takes care of moving all element less than pivot at left and greater than pivot at right half of array and continue doing it recursively.

Below is the source code given with the project structure. And I have kept many System.out statement which is just for the understanding purpose. You may find it tedious but some time, for some people it might save time to understand the flow.

Project Structure:

QuickSort.java

```package daa;

import java.util.ArrayList;
import java.util.Random;

public class QuickSort {
private static ArrayList<Integer> inputArray = new ArrayList<Integer>();

public QuickSort(ArrayList<Integer> inputArray){
QuickSort.inputArray = inputArray;
}

public void startQuickStart(int start,int end){
int q;
if(start<end){
q = partition(start, end);
startQuickStart(start, q);
startQuickStart(q+1, end);
}
}

public ArrayList<Integer> getSortedArray(){
return QuickSort.inputArray;
}

int partition(int start,int end){
System.out.println("\n---------Iteration Starts----------");
System.out.println("\nSorting Window from index number:"+start+" to "+end);

int init = start;
int length = end;

Random r = new Random();
int pivotIndex = nextIntInRange(start,end,r);
int pivot = inputArray.get(pivotIndex);

System.out.println("Pivot Element "+pivot+" at index:"+pivotIndex);

while(true){
while(inputArray.get(length)>pivot && length>start){
length--;
}

while(inputArray.get(init)<pivot && init<end){
init++;
}

if(init<length){
int temp;
temp = inputArray.get(init);
inputArray.set(init,inputArray.get(length));
inputArray.set(length,temp);
length--;
init++;

System.out.println("\nAfter Swapping");
for(int i=start;i<=end;i++){
System.out.print(inputArray.get(i)+" ");
}
}else{
System.out.println("\n---------Iteration Ends---------");
return length;
}
}

}

// Below method is to just find random integer from given range
static int nextIntInRange(int min, int max, Random rng) {
if (min > max) {
throw new IllegalArgumentException("Cannot draw random int from invalid range [" + min + ", " + max + "].");
}
int diff = max - min;
if (diff >= 0 && diff != Integer.MAX_VALUE) {
return (min + rng.nextInt(diff + 1));
}
int i;
do {
i = rng.nextInt();
} while (i < min || i > max);
return i;
}
}
```

MainPractise.java

```import java.util.ArrayList;

import daa.QuickSort;

public class MainPractise implements Cloneable {

public static void main(String[] args) {

ArrayList<Integer> unsortedArray = new ArrayList<Integer>();

QuickSort qsu = new QuickSort(unsortedArray);
System.out.println("---------Initial Unsorted Array---------");
for(int i:qsu.getSortedArray()){
System.out.print(i+" ");
}

qsu.startQuickStart(0, unsortedArray.size()-1);

System.out.println("\n\n---------Processed sorted Array---------");
for(int i:qsu.getSortedArray()){
System.out.print(i+" ");
}
}
}```

Output:

———Initial Unsorted Array———
2 8 6 3 12 4 7
———Iteration Starts———-

Sorting Window from index number:0 to 6
Pivot Element 12 at index:4

After Swapping
2 8 6 3 7 4 12
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 5
Pivot Element 8 at index:1

After Swapping
2 4 6 3 7 8
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 4
Pivot Element 3 at index:3

After Swapping
2 3 6 4 7
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 1
Pivot Element 3 at index:1

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 1
Pivot Element 3 at index:1

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:0 to 1
Pivot Element 2 at index:0

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:2 to 4
Pivot Element 7 at index:4

———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:2 to 4
Pivot Element 4 at index:3

After Swapping
4 6 7
———Iteration Ends———

———Iteration Starts———-

Sorting Window from index number:3 to 4
Pivot Element 6 at index:3

———Iteration Ends———
———Processed sorted Array———
2 3 4 6 7 8 12

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Insertion Sort implementation in Java

One of the simplest (in terms of understanding :P) sorting technique is Insertion Sort.
You will find many sites giving example of cards. Like suppose left hand has already sorted cards where as right hand has unsorted. You can pick first card from right hand unsorted and try to put it in left hand so that the sorted order preserves in left hand.

Suppose you never played card in your life (means you wasted your childhood 😛 ).
You can also think of 2 queue of people ( A and B). In queue A, all the people are standing in incremental order of their height and in queue B, no one gives a shit about any order. Now suppose a person P from queue B is tired of those people and wants to join queue A. So when he join queue A, he has to start from the person who is standing last and find a position so that the order of height preserves. In this process all the people from queue A who are taller than P, has to shift their place one step back.

Now lets implement this in java using ArrayList.

My project Explorer:

InsertionSort.java

```package daa;

import java.util.ArrayList;

public class InsertionSort {

private static ArrayList<Integer> inputArray = new ArrayList<Integer>();

public static ArrayList<Integer> getInputArray() {
return inputArray;
}

//Just for the display purpose
public InsertionSort(ArrayList<Integer> inputArray){
InsertionSort.inputArray = inputArray;
}

public void sortGivenArray(){
for(int i=1;i<inputArray.size();i++){

int key = inputArray.get(i);

for(int j= i-1;j>=0;j--){
if(key<inputArray.get(j)){
// Shifting Each Element to its right as key is less than the existing element at current index
inputArray.set(j+1,inputArray.get(j));

// Special case scenario when all elements are less than key, so placing key value at 0th Position
if(j==0){
inputArray.set(0, key);
}
}else{
// Putting Key value after element at current index as Key value is no more less than the existing element at current index
inputArray.set(j+1,key);
break; // You need to break the loop to save un necessary iteration
}
}
}
}
}```

MainPractise.java

```import java.util.ArrayList;

import daa.InsertionSort;

public class MainPractise implements Cloneable {

public static void main(String[] args) {

ArrayList<Integer> unsortedArray = new ArrayList<Integer>();

InsertionSort is = new InsertionSort(unsortedArray);

System.out.println("---------Initial Unsorted Array---------");
for(int i:InsertionSort.getInputArray()){
System.out.print(i+" ");
}

is.sortGivenArray();

System.out.println("\n------------Sorted Array------------");
for(int i:InsertionSort.getInputArray()){
System.out.print(i+" ");
}
}
}```

Output:

———Initial Unsorted Array———
8 7 6 5 4 0 2
————Sorted Array————
0 2 4 5 6 7 8

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

If you have any question mail us on