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:

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

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

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

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

Run the build.


COMMENTS







keep exploring!

back to all projects