# SORTING ALGORITHMS IN JAVA

###### INSERTION SORT, SELECTION SORT, MERGE SORT, QUICK SORT
0

JAVA

HARD

last hacked on Dec 28, 2018

According to Wikipedia, "an algorithm is a self-contained sequence of actions to be performed... algorithms can perform calculation, data processing, and automated reasoning tasks." Algorithms are awesome. They are a foundation to our lives as a function of modern mathematics, computer science & and statistics.

In this project we cover five popular sorting algorithms and their implementation in Java:

• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

We first create a project directory, then a Java interface, and finally a Java class for each algorithm as well as its respective test.

# Create Project Directory `Sorting`

Create a project called `Sorting` and include all your code in it.

``````\$ mkdir Sorting
\$ cd Sorting
``````

# Create Interface `Sort.java`

First, create an interface called `Sort.java`.

``````\$ touch Sort.java
``````

Input this code into `Sort.java`:

``````public interface Sort {
int[] sort(int[] arr);
}
``````

Notice that we specified a `sort()` method, which returns an integer array specified by `int[]`, and equally takes an integer array specified by `int[]` within the parenthesis.

Now it's time to create classes for each of the sorting algorithms.

# Selection Sort

## Create Class `SelectionSort.java`

Create a class called `SelectionSort.java`:

``````\$ touch SelectionSort.java
``````

Input this code into `SelectionSort.java`:

``````public class SelectionSort implements Sort {
public int[] sort(int[] arr) {
if (arr.length == 1) {
return arr;
}
for(int i = 0; i < arr.length; i++){
int z = i;
for(int m = i + 1; m < arr.length; m++){
if(arr[z] > arr[m]){
z = m;
}
}
swap(arr, i, z);
}
return arr;
}
public int[] swap(int[] arr, int firstPosition, int swapper){
//int buffer_firstPosition = firstPosition;
int buffer_firstValue = arr[firstPosition];
arr[firstPosition] = arr[swapper];
arr[swapper] = buffer_firstValue;
return arr;
}
}
``````

## Create Class `TestSelectionSort.java`

Create a class called `TestSelectionSort.java`:

``````\$ touch TestSelectionSort.java
``````

Input this code into `TestSelectionSort.java`:

``````import java.util.Arrays;
public class SelectionSortTest {
public static void main(String args[]){
Sort selectionsort = new SelectionSort();
int[] shuffledTestArray = {1,2,4,673,3534,345,234523,45,234523,432534,325};
int[] sortedTestArray = selectionsort.sort(shuffledTestArray);
System.out.println(Arrays.toString(sortedTestArray));
}
}
``````

## Compile the source code

Compile the source code.

Run the build.

# Insertion Sort

## Create Class `InsertionSort.java`

Create a class called `InsertionSort.java`:

``````\$ touch InsertionSort.java
``````

Input this code into `InsertionSort.java`:

``````public class InsertionSort implements Sort {
public int[] sort(int[] arr){
if (arr.length == 1) {
return arr;
}
for(int i = 1; i < arr.length; i++ ){
int swapperIndex = i;
int swapperValue = arr[i];
while(arr[swapperIndex] < arr[swapperIndex - 1]){
arr[swapperIndex] = arr[swapperIndex - 1];
arr[swapperIndex - 1] = swapperValue;
if(swapperIndex > 1){
swapperIndex--;
}
}
}
return arr;
}
}
``````

## Create Class `TestInsertionSort.java`

Create a class called `TestInsertionSort.java`:

``````\$ touch TestInsertionSort.java
``````

Input this code into `TestInsertionSort.java`:

``````import java.util.Arrays;
public class TestInsertionSort {
public static void main(String args[]){
Sort insertionsort = new InsertionSort();
int[] shuffledTestArray = {2,1,4,673,3534,345,234523,45,234523,432534,325};
int[] copyShuffle = Arrays.copyOf(shuffledTestArray, shuffledTestArray.length);
int[] sortedTestArray = insertionsort.sort(shuffledTestArray);
Arrays.sort(copyShuffle);
System.out.println(Arrays.toString(sortedTestArray));
System.out.println("Is array truly sorted?: " + Arrays.equals(sortedTestArray, copyShuffle));
}
}
``````

## Compile the source code

Compile the source code.

Run the build.

# Merge Sort

## Create Class `MergeSort.java`

Create a class called `MergeSort.java`:

``````\$ touch MergeSort.java
``````

Input this code into `MergeSort.java`:

``````public class MergeSort implements Sort {

public int[] sort(int[] arr) {
if (arr.length == 1) {
return arr;
}
int middle = arr.length / 2;
int[] firstHalf = sort(subArray(arr, 0, middle));
int[] secondHalf = sort(subArray(arr, middle, arr.length));
int[] mergedSortedArray = mergeArray(firstHalf, secondHalf);
return mergedSortedArray;
}

public static int[] subArray(int[] inputArray, int start, int end) {
int newArrayLength = end - start;
int[] newArray = new int[newArrayLength];
int iterator = start;
for (int i = 0; i < newArrayLength; i++) {
newArray[i] = inputArray[iterator];
iterator = iterator + 1;
}
return newArray;
}

public static int[] mergeArray(int[] first, int[] second) {
int mergedArrayLength = first.length + second.length;
int[] mergedArray = new int[mergedArrayLength];
int y = 0;
int z = 0;
for (int i = 0; i < mergedArrayLength; i++) {
int merger;
if(first.length == y) {
merger = second[z];
z++;
} else if (second.length == z) {
merger = first[y];
y++;
} else if (first[y] <= second[z]) {
merger = first[y];
y++;
} else {
merger = second[z];
z++;
}
mergedArray[i] = merger;
}
return mergedArray;
}
}
``````

## Create Class `TestMergeSort.java`

Create a class called `TestMergeSort.java`:

``````\$ touch TestMergeSort.java
``````

Input this code into `TestMergeSort.java`:

``````import java.util.Arrays;
public class TestMergeSort {
public static void main(String args[]){
Sort mergesort = new MergeSort();
int[] shuffledTestArray = {1,2,4,673,3534,345,234523,45,234523,432534,325};
int[] sortedTestArray = mergesort.sort(shuffledTestArray);
System.out.println(Arrays.toString(sortedTestArray));
}
}
``````

## Compile the source code

Compile the source code.

Run the build.

# Quick Sort

## Create Class `QuickSort.java`

Create a class called `QuickSort.java`:

``````\$ touch QuickSort.java
``````

Input this code into `QuickSort.java`:

``````public class QuickSort implements Sort {
public int[] sort(int[] arr){
fixPivotPlace(arr, 0, arr.length - 1);
return arr;
}
public void fixPivotPlace(int[] arr, int leftStart, int rightStart){
int leftHand = leftStart;
int rightHand = rightStart;
if(rightHand - leftHand <= 0){
return;
}
int pivot = (rightHand - leftHand) / 2 + leftStart;
while(leftHand < pivot || rightHand > pivot) {
while (arr[leftHand] < arr[pivot]) {
leftHand++;
}
//move your right hand down till you find the value smaller than the pivot
while (arr[rightHand] > arr[pivot]) {
rightHand--;
}
if(leftHand >= pivot || rightHand <= pivot){
break;
}
swapper(arr, leftHand, rightHand);
leftHand++;
rightHand--;
}
if(leftHand >= pivot){
pivot = rightHand;
}else if(rightHand <= pivot){
pivot= leftHand;
}
swapper(arr, leftHand, rightHand);

fixPivotPlace(arr, leftStart, pivot - 1);
fixPivotPlace(arr, pivot + 1, rightStart);
}
public void swapper(int[] arr, int rightHand, int leftHand){
int leftHandBuffer = arr[leftHand];
int rightHandBuffer = arr[rightHand];
arr[leftHand] = rightHandBuffer;
arr[rightHand] = leftHandBuffer;
}
}
``````

## Create Class `TestQuickSort.java`

Create a class called `TestQuickSort.java`:

``````\$ touch TestQuickSort.java
``````

Input this code into `TestQuickSort.java`:

``````import java.util.Arrays;
public class TestQuickSort {
public static void main(String args[]){
Sort quicksort = new QuickSort();
int[] shuffledTestArray = {1,2,4,673,3534,345,234523,45,234523,432534,325};
int[] sortedTestArray = quicksort.sort(shuffledTestArray);
System.out.println(Arrays.toString(shuffledTestArray));
}
}
``````

## Compile the source code

Compile the source code.

Run the build.