Bubble Sort

Definition

Bubble sort is a simple sort with a runtime of O(n2). It works by repeatedly "bubbling" the largest element to the end of the array.

Algorithm

  1. Compare first two elements in the array.
  2. Only if the first is larger then the second, swap the two.
  3. Go on to next element in the array.
  4. Repeats steps 1-3 until array is sorted.
  5. Repeat steps 1-4 for all elements in the array

Code (which we are currently trying to improve)

public static int[] bubbleSort(int[] x) { 
  boolean swappedOnPrevRun = true; 
 
  for (int i = 0; i < x.length-1 && swappedOnPrevRun;i++) { 
    swappedOnPrevRun = false; 
 
    for(int j = 0; j < x.length-i-1; j++) { 
      if(x[j] > x[j + 1]) { 
        swap(x,j,j+1);  
        swappedOnPrevRun = true; 
      } 
    } 
  } 
  return x; 
}

Visual

screen-capture-3.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License