Skip to content

Instantly share code, notes, and snippets.

@JakeTrock
Created October 11, 2018 20:19
Show Gist options
  • Save JakeTrock/d0e78a3b86db0be633e0b76c783fc892 to your computer and use it in GitHub Desktop.
Save JakeTrock/d0e78a3b86db0be633e0b76c783fc892 to your computer and use it in GitHub Desktop.
This is a comparison of 3 sort algorithms, which times their runtimes
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