Skip to content

Instantly share code, notes, and snippets.

@parvinderandroid
Created August 8, 2019 13:47
Show Gist options
  • Save parvinderandroid/2f186ad8df960aab934e6cb2bb029906 to your computer and use it in GitHub Desktop.
Save parvinderandroid/2f186ad8df960aab934e6cb2bb029906 to your computer and use it in GitHub Desktop.
Trying to compare different sorts of sorting algorithms in Java
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