Why is my bubble sort algorithm faster than my selection and insertion sort algorithms in my program?

Question

This program is a program that contains a grid and in the grid, the columns contain a different # of numbers that have to be sorted, and the rows have different sorting algorithms, that are used to sort the amount of numbers clicked in the grid, then the amount of time it took for the algorithm to sort the randomly generated #'s is printed out.

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
int n = 99;
int min, tmp, i, j, min_id, data, k, temp;
int[] array = new int [n];

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void setup() {

  size(661, 500);
  background(255);

  initArr();
  bubbleSort();
  selectionSort(array, n);
  insertionSort(array);
  quickSort(0, n - 1);
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void draw() {

  drawGrid();
  labels();
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void initArr() {

  for (i = 0; i < n; i ++) {
    array[i] = (int)random(1, 10);
  }
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void mouseReleased() {
  for (int j = 1; j < 5; j ++) {

    for (int i = 1; i < 6; i ++) {

      if (mouseX > i * 110 && mouseX < i * 110 + 110 && mouseY > j * 80 && mouseY < j * 80 + 80) {
        println("X:" + " " + i + " " + "Y:" + " " + j);

        if (i == 1 && j == 1) {
          initArr();
          int start = millis();
          bubbleSort();
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 2 && j == 1) {
          int n = 999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          bubbleSort();
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 3 && j == 1) {
          int n = 9999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          bubbleSort();
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 4 && j == 1) {
          int n = 99999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          bubbleSort();
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 5 && j == 1) {
          int n = 999999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          bubbleSort();
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 1 && j == 2) {
          initArr();
          int start = millis();
          selectionSort(array, n);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 2 && j == 2) {
          int n = 999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          selectionSort(array, n);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 3 && j == 2) {
          int n = 9999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          selectionSort(array, n);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 4 && j == 2) {
          int n = 99999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          selectionSort(array, n);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 5 && j == 2) {
          int n = 999999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          selectionSort(array, n);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 1 && j == 3) {
          initArr();
          int start = millis();
          insertionSort(array);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 2 && j == 3) {
          int n = 999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          insertionSort(array);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 3 && j == 3) {
          int n = 9999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          insertionSort(array);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 4 && j == 3) {
          int n = 99999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          insertionSort(array);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 5 && j == 3) {
          int n = 999999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          insertionSort(array);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 1 && j == 4) {
          initArr();
          int start = millis();
          quickSort(0, n - 1);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 2 && j == 4) {
          int n = 999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          quickSort(0, n - 1);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 3 && j == 4) {
          int n = 9999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          quickSort(0, n - 1);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 4 && j == 4) {
          int n = 99999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          quickSort(0, n - 1);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        } else if (i == 5 && j == 4) {
          int n = 999999;
          array = new int[n]; // Brand new array.
          initArr();
          int start = millis();
          quickSort(0, n - 1);
          int ellapsed = millis() - start;
          println("Time:" + " " + (float)ellapsed/1000);
        }
      }
    }
  }
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void labels() {

  for (k = 0; k < 5; k ++) {
    rect(0, k * 80, 110, 80);
    rect(k * 110 + 110, 0, 110, 80);
  }

  for (k = 0; k < 3; k ++) {
    rect(k * 183.5 + 110, 400, 183.5, 80);
  } 

  fill(0);
  text("ALGORITHM", 20, 45);
  text("BUBBLE", 20, 125);
  text("SELECTION", 20, 205);
  text("INSERTION", 20, 285);
  text("QUICK", 20, 365);

  text("100", 150, 45);
  text("1000", 260, 45);
  text("10000", 365, 45);
  text("100000", 470, 45);
  text("1000000", 575, 45);
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void drawGrid() {

  //----Grid----
  for (j = 1; j < 5; j ++) { //columns
    for (i = 1; i < 6; i ++) { // rows

      fill(255);
      if (i != 0 && j != 0 && j <= 4 && i <= 5) {
        if (mouseX > i * 110 && mouseX < i * 110 + 110 && mouseY > j * 80 && mouseY < j * 80 + 80)
          fill(255, 200, 200);
      } else
        fill(255);

      rect(i * 110, j * 80, 110, 80);
    }
  }
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void bubbleSort() {

  for (i = 0; i < n - 1; i++) { 
    for (j = 0; j < n - i - 1; j++)
      if (array[j] > array[j+1]) { 
        temp = array[j]; 
        array[j] = array[j + 1]; 
        array[j + 1] = temp;
      }
  }
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void selectionSort (int array[], int n) { 

  for (i = 0; i < n - 1; i ++) { 
    min = array[i]; 
    for (j = i + 1; j < n; j ++) {
      if (array[j] < min) { 
        min = array[j]; 
        min_id = j;
      }
    }
    tmp = array[i]; 
    array[i] = array[min_id]; 
    array[min_id] = tmp;
  }
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void insertionSort(int[] array) {

  for (int i = 1; i < array.length; i++)
  {
    // a temporary copy of the current element
    temp = array[i]; 

    // find the position for insertion
    for (j = i; j > 0; j--)
    {
      if (array[j - 1] < temp)
        break; 
      // shift the sorted part to right
      array[j] = array[j - 1];
    }

    // insert the current element
    array[j] = temp;
  }
}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void quickSort(int low, int high) { 
  i = low; 
  j = high; 
  // calculate pivot number, I am taking pivot as middle index number
  int pivot = array[low+(high-low)/2]; // Divide into two arrays
  while (i <= j) {
    /**
     * In each iteration, we will identify a number from left side which
     * is greater then the pivot value, and also we will identify a number
     * from right side which is less then the pivot value. Once the search
     * is done, then we exchange both numbers.
     */
    while (array[i] < pivot) { 
      i++;
    }
    while (array[j] > pivot) {
      j--;
    }
    if (i <= j) { 
      temp = array[i]; 
      array[i] = array[j]; 
      array[j] = temp; 
      //move index to next position on both sides
      i++; 
      j--;
    }
  }
  // call quickSort() method recursively
  if (low < j) 
    quickSort(low, j); 
  if (i < high) 
    quickSort(i, high);
}

score 3 · Accepted Answer · answered Oct 06 '17 at 02:46

You missed a few things out:

Writing benchmarks for java is an art on its own due to the fact that amongst other things the JVM itself is a pretty complex piece of software that does quite a lot of optimization with your code, recompiles it, etc..
The fact that quicksort has an asymptotically better runtime (see the math-addenda of this answer) means that there will be a certain break-even-point after which it will be faster. For smaller inputs an asymptotically worse algorithm might actually be the better choice.
You measure the time in micro-seconds, which is a way too low resolution for inputs as small as yours. The measured time won't be much more than random noise most likely
The state of the input passed to the sorting-functions. Your input may be more or less random, but all values lie in a range from 1 to 10. If you want really test your implementations for their runtime, give them input with a greater range of values and make sure that all functions receive the same input. Most sorting-algorithms behave in a special way, if fed with input that matches certain criteria. E.g. a properly implemented bubblesort should run in O(n) on a sorted array.
Last but not least: the input-size is way too small to make the benchmark meaningful. The most important factor in the timing in your implementation is thread-scheduling (and other noise introduced by the OS), not performance. Let your algorithms seriously work, if you want to compare them.

How would I implement a "Simulate All" Button when if pressed every algorithm sort the different amount of #'s? — J Tyrone, Oct 06 '17 at 15:19
@JTyrone I've rolled your question back to its original state, as this answer discusses the original problem. Please ask a separate question instead. — , Oct 06 '17 at 19:22

Why is my bubble sort algorithm faster than my selection and insertion sort algorithms in my program?

1 Answers1