Java implementation of all sorting algorithms
- Selection Sort
- Insertion Sort
- Bubble Sort
- Merge Sort
- Quick Sort
Quick sort is said to most important invention of the century in computer science .
SortUtils.java
package com.salpe.sort; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Random; public class SortUtils { // sorting types static enum SORT { SELECTION, INSERTION, BUBBLE, MERGE, QUICK; } /** * Class for collecting sorting stats * */ static class SortStat implements Comparable private SORT sortType; private long timeInNanos; public SortStat(SORT sortType, long timeInNanos) { super(); this.sortType = sortType; this.timeInNanos = timeInNanos; } @Override public int compareTo(SortStat o) { return Long.valueOf(timeInNanos).compareTo(Long.valueOf(o.timeInNanos)); } @Override public String toString() { return "Sorting Method : " + sortType.name() + ", timeInNanos =" + timeInNanos; } } public static void main(String[] args) { for (int i = 1; i < 6; i++) { int size = (int) (Math.pow(10, i)); int[] a = generateRandomArr(size); System.out.println("------------------------------------"); System.out.println("Data size = " + a.length); System.out.println("------------------------------------"); SORT[] sorts = SORT.values(); List for (int j = 0; j < sorts.length; j++) { int[] b = new int[a.length]; System.arraycopy(a, 0, b, 0, a.length); long t1 = System.nanoTime(); sort(b, sorts[j]); long t2 = System.nanoTime(); long t = t2 - t1; stats.add(new SortStat(sorts[j], t)); } Collections.sort(stats); stats.forEach(e -> System.out.println(e.toString())); } } private static int[] generateRandomArr(int size) { Random random = new Random(); int[] a = new int[size]; for (int i = 0; i < a.length; i++) { a[i] = random.nextInt(a.length); } return a; } public static void sort(int[] a, SORT sortType) { switch (sortType) { case SELECTION: selectionSort(a); break; case BUBBLE: bubbleSort(a); break; case INSERTION: insertionSort(a); break; case MERGE: mergeSort(a); break; case QUICK: quickSort(a); break; default: throw new IllegalArgumentException("Unsupported Sort Type"); } } public static void quickSort(int[] a) { quickSort0(a, 0, (a.length - 1)); } /** * Quick sort recursion * * @param a * @param start * @param end */ public static void quickSort0(int[] a, int start, int end) { // exit condition if (start >= end) { return; } int pIdx = partition(a, start, end); quickSort0(a, start, pIdx - 1); quickSort0(a, pIdx + 1, end); } /** * create parition for pivot * * @param a * @param start * @param end * @return */ public static int partition(int[] a, int start, int end) { // let pivot be last element int pivot = a[end]; int pIdx = start; for (int i = start; i < end; i++) { if (a[i] <= pivot) { swap(a, pIdx, i); pIdx++; } } // keep pivot at its position swap(a, pIdx, end); return pIdx; } /** * Merge sort method * * @param arr */ public static void mergeSort(int[] arr) { mergeSortO(arr, 0, arr.length - 1, new int[arr.length]); } /** * Recursive merge sort * * @param a * - orig array * @param lo * - low index * @param hi * - high index * @param aux * - auxiliary array */ public static void mergeSortO(int[] a, int lo, int hi, int[] aux) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; mergeSortO(a, lo, mid, aux); mergeSortO(a, mid + 1, hi, aux); mergeSortedArr(a, lo, mid, hi, aux); } /** * Merge two sorted array * * @param a * @param lo * @param mid * @param hi * @param aux */ public static void mergeSortedArr(int[] a, int lo, int mid, int hi, int[] aux) { // copy for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } int i = lo, j = mid + 1, k = lo; while (i <= mid && j <= hi) { if (aux[i] >= aux[j]) { a[k++] = aux[j++]; } else if (aux[i] < a[j]) { a[k++] = aux[i++]; } } while (i <= mid) { a[k++] = aux[i++]; } while (j <= hi) { a[k++] = aux[j++]; } } /** * Divide array in sorted right and unsorted on left * * @param arr */ public static void insertionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i; j > 0; j--) { if (arr[j] < arr[j - 1]) { swap(arr, j, j - 1); } } } } /** * Compare current to next entry * * @param arr */ public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { // optimization for already sorted array boolean sorted = true; for (int j = 0; j < arr.length - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); sorted = false; } } if (sorted) { break; } } } /** * select min or max from unseen part of array for current position * * @param arr */ public static void selectionSort(int[] arr) { for (int i = 0; i < (arr.length - 1); i++) { int minIdx = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[i]) { minIdx = j; } if (i != minIdx) { swap(arr, i, minIdx); } } } } /** * swap from i to j * * @param arr * @param i * @param j */ private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } |
Time analysis of sorting algorithms - time is in nano secs . results are sorted by algorithms which take minimum time .
Data set :
Data sample set is random .In practice there might be partially sorted collection .
Hardware :
Quad-core commodity machine
Quick sort wins for large data but it not stable so people go for merge sort for practical purposes .
Dual strategy could be used like for merge sort if sub array is of say size 10 then use insertion sort otherwise use merge sort .
Such combination could be efficient strategy .
------------------------------------
Data size = 10
------------------------------------
Sorting Method : BUBBLE, timeInNanos =9526
Sorting Method : INSERTION, timeInNanos =11876
Sorting Method : QUICK, timeInNanos =13032
Sorting Method : MERGE, timeInNanos =18974
Sorting Method : SELECTION, timeInNanos =44663
------------------------------------
Data size = 100
------------------------------------
Sorting Method : QUICK, timeInNanos =44607
Sorting Method : MERGE, timeInNanos =88421
Sorting Method : INSERTION, timeInNanos =266476
Sorting Method : BUBBLE, timeInNanos =361008
Sorting Method : SELECTION, timeInNanos =555962
------------------------------------
Data size = 1000
------------------------------------
Sorting Method : QUICK, timeInNanos =649487
Sorting Method : MERGE, timeInNanos =1117328
Sorting Method : INSERTION, timeInNanos =5601350
Sorting Method : BUBBLE, timeInNanos =11403826
Sorting Method : SELECTION, timeInNanos =11824134
------------------------------------
Data size = 10000
------------------------------------
Sorting Method : QUICK, timeInNanos =2644196
Sorting Method : MERGE, timeInNanos =3918558
Sorting Method : INSERTION, timeInNanos =41950004
Sorting Method : SELECTION, timeInNanos =215247099
Sorting Method : BUBBLE, timeInNanos =237130370
------------------------------------
Data size = 100000
------------------------------------
Sorting Method : QUICK, timeInNanos =9447849
Sorting Method : MERGE, timeInNanos =14451509
Sorting Method : INSERTION, timeInNanos =5228027442
Sorting Method : SELECTION, timeInNanos =20031340866
Sorting Method : BUBBLE, timeInNanos =20152200844
