BubbleSort is the cannonical example of an inefficient sorting Algorithm. It works by moving through the array comparing each element with the next element and swapping them if they're in the wrong order. In each iteration, it moves the next largest element into the next last position, stopping one position earlier than previously. An example:
||After Iteration||||Element Nr. |Outer|Inner|0|1|2|3 ||^Initial state | D | B | C | A | 1 | 1 | [B? | [D? | C | A | 1 | 2 | B | [C? | [D? | A | 1 | 3 | B | C | [A? | [__D__? | 2 | 1 | [B? | [C? | A | D | 2 | 2 | B | [A? | [__C__? | D | 3 | 1 | [A? | [__B__? | C | D
The brackets denote the elements which were compared (and possibly swapped) during an iteration. Bold elements have reached their final position. As you can see, the next largest element falls into the next last position after each iteration.
A sample implementation might be
It is obvious that, with n being the array's length, the inner loop will total (n / 2) * (n - 1) iterations - which is (n^2 - n) / 2. Therefor, in BigONotation, the complexity of BubbleSort is O(n^2). Clearly, its performance will degrade quickly as the array grows.
lib/main.php:944: Notice: PageInfo: Cannot find action page