Bubble the larger value to the top on each iteration.

  1. Loop through the array
  2. At each index, if current index is larger than next index, then swap them
  3. After looping through the array, the largest value should have bubbled to the end (dont have loop over that again)
  4. Repeat the above steps until sorted

Efficiency notes:

  • After each iteration the highest value has bubbled up into its place and therefore do not have to iterate over it again. ie keep a pointer of where the last iteration ended and reduce it by one each time
  • If you have passed through the enitre set of data without swapping once then the data is sorted and you do not have to continue.

Let's sort an array of ints as an example: [ 5, 2, 1, 4, 3 ]

Iteration 1:

pointer = 4 (last index)

  • i = 0 [ 5, 2, 1, 4, 3 ] (swap 5 Á 2)
  • i = 1 [ 2, 5, 1, 4, 3 ] (swap 5 Á 1)
  • i = 2 [ 2, 1, 5, 4, 3 ] (swap 5 Á 4)
  • i = 3 [ 2, 1, 4, 5, 3 ] (swap 5 Á 3)
  • i = 4 [ 2, 1, 4, 3, 5 ] (bubbled to top)

Iteration 2:

pointer = 3 (-1 from previous)

  • i = 0 [ 2, 1, 4, 3, 5 ] (swap 2 Á 1)
  • i = 1 [ 1, 2, 4, 3, 5 ] (do nothing)
  • i = 2 [ 1, 2, 4, 3, 5 ] (swap 4 Á 3)
  • i = 3 [ 1, 2, 3, 4, 5 ] (bubbled to top)

Iteration 3:

pointer = 2 (-1 from previous)

  • i = 0 [ 1, 2, 3, 4, 5 ] (do nothing)
  • i = 1 [ 1, 2, 3, 4, 5 ] (do nothing)
  • i = 2 [ 1, 2, 3, 4, 5 ] (do nothing)

no swap happened this iteration therefore complete algorithm

Big O notation: O(n2) because the outer loop runs n times & the inner loop runs n timesat worst case

Is Data sensitive: the erlier the data is ordered then the earlier completes eg if data is already order then it wil only iteration once O(n) Worst case: reverse ordered list

High data movement: requires many data swaps per iteration

In-place sort: the sorted items occupy the same storage as the original ones

Stable sort: Duplicates remain in their original order

Created unsorted Set

Explanations: Off

Toggle Explanations

Sort Speed:

Check out these links for more info:

My Bubble Sort Code