Created
August 8, 2019 13:47
-
-
Save parvinderandroid/2f186ad8df960aab934e6cb2bb029906 to your computer and use it in GitHub Desktop.
Trying to compare different sorts of sorting algorithms in Java
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Random; | |
import java.util.Arrays; | |
class SpeedTest { | |
public static void selectionSort(int arr[]) { | |
int i, j, t, minIndex, len = arr.length; | |
for(i=0; i<len-1; i++) { | |
minIndex = i; | |
for(j=i+1; j<len; j++) | |
if(arr[j] < arr[minIndex]) | |
minIndex = j; | |
t = arr[i]; | |
arr[i] = arr[minIndex]; | |
arr[minIndex] = t; | |
} | |
} | |
public static void bubbleSort(int arr[]) { | |
int i, j, len = arr.length, temp; | |
for(i=0; i<len-1; i++) { | |
for(j=0; j<len-1-i; j++) { | |
if(arr[j] > arr[j+1]) { | |
temp = arr[j]; | |
arr[j] = arr[j+1]; | |
arr[j+1] = temp; | |
} | |
} | |
} | |
} | |
public static void insertionSort(int arr[]) { | |
int i, j, len = arr.length, temp; | |
for(i=1; i<len; i++) { | |
for(j=0; j<i; j++) { | |
if(arr[i] < arr[j]) { | |
temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
} | |
} | |
} | |
public static void merge(int left[], int right[], int arr[]) { | |
int i = 0, j = 0, k = 0, leftlen = left.length, rightlen = right.length; | |
while(i<leftlen && j<rightlen) | |
if(left[i] < right[j]) | |
arr[k++] = left[i++]; | |
else | |
arr[k++] = right[j++]; | |
while(i<leftlen) | |
arr[k++] = left[i++]; | |
while(j<rightlen) | |
arr[k++] = right[j++]; | |
} | |
public static void mergeSort(int arr[]) { | |
if(arr.length > 1) { | |
int i = 0, j = 0, k = 0, len = arr.length, mid = len / 2, left[], right[]; | |
left = new int[mid]; | |
right = new int[len - mid]; | |
while(i<mid) | |
left[j++] = arr[i++]; | |
while(i<arr.length) | |
right[k++] = arr[i++]; | |
mergeSort(left); | |
mergeSort(right); | |
merge(left, right, arr); | |
} | |
} | |
public static int partition(int arr[], int start, int end) { | |
int pivot = arr[end], pIndex = start, i, temp; | |
for(i=start; i<end; i++) { | |
if(arr[i] <= pivot) { | |
temp = arr[i]; | |
arr[i] = arr[pIndex]; | |
arr[pIndex] = temp; | |
pIndex++; | |
} | |
} | |
temp = arr[end]; | |
arr[end] = arr[pIndex]; | |
arr[pIndex] = temp; | |
return pIndex; | |
} | |
public static void quickSort(int arr[], int start, int end) { | |
if(start < end) { | |
int pIndex = partition(arr, start, end); | |
quickSort(arr, start, pIndex-1); | |
quickSort(arr, pIndex+1, end); | |
} | |
} | |
public static void main(String[]args) { | |
Random rnd = new Random(); | |
int length = 100000; | |
int[] source = new int[length]; | |
for(int i=0; i<length; i++) | |
source[i] = rnd.nextInt(); | |
int[] copy; | |
long start, end; | |
double time; | |
//Starting Selection sort | |
start = System.nanoTime(); | |
copy = source; | |
selectionSort(copy); | |
end = System.nanoTime(); | |
time = (end - start) / 1000000000.0; | |
System.out.println("Selection Sort finished in " + time + " seconds"); | |
//Starting Bubble sort | |
start = System.nanoTime(); | |
copy = source; | |
bubbleSort(copy); | |
end = System.nanoTime(); | |
time = (end - start) / 1000000000.0; | |
System.out.println("Bubble Sort finished in " + time + " seconds"); | |
//Starting Insertion sort | |
start = System.nanoTime(); | |
copy = source; | |
insertionSort(copy); | |
end = System.nanoTime(); | |
time = (end - start) / 1000000000.0; | |
System.out.println("Insertion Sort finished in " + time + " seconds"); | |
//Starting Merge sort | |
start = System.nanoTime(); | |
copy = source; | |
mergeSort(copy); | |
end = System.nanoTime(); | |
time = (end - start) / 1000000000.0; | |
System.out.println("Merge Sort finished in " + time + " seconds"); | |
//Starting Quick sort | |
start = System.nanoTime(); | |
copy = source; | |
quickSort(copy, 0, length-1); | |
end = System.nanoTime(); | |
time = (end - start) / 1000000000.0; | |
System.out.println("Quick Sort finished in " + time + " seconds"); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment