Created
October 11, 2018 20:19
-
-
Save JakeTrock/d0e78a3b86db0be633e0b76c783fc892 to your computer and use it in GitHub Desktop.
This is a comparison of 3 sort algorithms, which times their runtimes
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
Timer timer=new Timer(); | |
int numtrials=1; | |
int[] array; | |
int[] timings1; | |
int[] timings2; | |
int[] timings3; | |
void setup() { | |
for (int n = 100; n<= 2000; n+=100) { | |
timings1 = new int[numtrials]; | |
timings2 = new int[numtrials]; | |
timings3 = new int[numtrials];// loop over different array sizes | |
array = makeArray(n); // create a sorted array | |
for (int i = 0; i < numtrials; i++) { // loop over number of trials | |
shuffle(array); // shuffle the array | |
timer.start(); // start the timer | |
bubbleSort(array); // do the first sort | |
timings1[i] = timer.end(); // save the timing result | |
shuffle(array); // shuffle the array | |
timer.start(); // start the timer | |
selectionSort(array); // do the second sort | |
timings2[i] = timer.end(); // save the timing result | |
shuffle(array); // shuffle the array | |
timer.start(); // start the timer | |
mergeSort(array); // do the third sort | |
timings3[i] = timer.end(); // save the timing result | |
} | |
println(n, getMedian(timings1), getMedian(timings2), getMedian(timings3)); | |
} | |
} | |
int[] makeArray(int n) { | |
int[] c=new int[n]; | |
for (int i=0; i<n; i++)c[i]=i; | |
return c; | |
} | |
void shuffle(int[] x) { | |
for (int f=0; f<=x.length; f++) { | |
int copystore; | |
int vone = x[int(random(0, x.length))]; | |
int vtwo = x[int(random(0, x.length))]; | |
copystore = vone; | |
vtwo = vone; | |
vtwo=copystore; | |
} | |
} | |
int getMedian(int[] x) { | |
selectionSort(x); | |
return x[x.length / 2]; | |
} | |
void bubbleSort(int[] x) { | |
for (int i=0; i<x.length-1; i++) { | |
if (i==x.length) { | |
return; | |
} | |
if (x[i]>x[i+1]) { | |
int swp; | |
swp=x[i+1]; | |
x[i+1]=x[i]; | |
x[i]=swp; | |
} | |
} | |
} | |
void selectionSort(int[] x) { | |
for (int f = 0; f < x.length-1; f++) { | |
int iMin = f; | |
for (int i = f+1; i < x.length; i++) { | |
if (x[i] < x[iMin]) { | |
iMin = i; | |
} | |
} | |
if (iMin != f) { | |
int sw; | |
sw = x[f]; | |
x[f]=x[iMin]; | |
x[iMin]=sw; | |
} | |
} | |
} | |
int storage[]; | |
int n; | |
void mergeSort(int a[]) { | |
for (int w = 1; w < n; w = 2 * w) { | |
for (int i = 0; i < n; i = i + 2 * w) { | |
BottomUpMerge(a, i, min(i+w, n), min(i+2*w, n), storage); | |
} | |
CopyArray(storage, a, n); | |
} | |
} | |
void BottomUpMerge(int a[], int L, int R, int E, int storage[]) { | |
int i = L; | |
int j = R; | |
for (int k = L; k < E; k++) { | |
if (i < R && (j >= E ||a[i] <= a[j])) { | |
storage[k] = a[i]; | |
i = i + 1; | |
} else { | |
storage[k] = a[j]; | |
j = j + 1; | |
} | |
} | |
} | |
void CopyArray(int s[], int x[], int n) { | |
for (int i = 0; i < n; i++) { | |
s[i] = x[i]; | |
} | |
} | |
//Timer class | |
class Timer { | |
int startTime; | |
int endTime; | |
//Method to start the timer | |
void start() { | |
startTime = (int)System.nanoTime(); | |
} | |
//Method to end the timer; note it returns the elapsed time | |
int end() { | |
endTime = (int)System.nanoTime(); | |
return(endTime - startTime); | |
} | |
} | |
/*please keep this footer in here, You may use this code, but only if you keep this here, that said, this code was originally written by hokuco on github*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment