SORTING ALGORITHMS IN JAVA

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

JAVA

HARD

last hacked on Jul 22, 2017

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 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