Sorting and bubble sort

Sorting arranges elements in a particular order: ascending (smallest first) or descending (largest first). Sorted data is much easier to search: think of words in a dictionary, or students listed by roll number.

Bubble sort is the simplest method. It goes through the list comparing adjacent (neighbouring) elements, and swaps them if they are in the wrong order. One complete trip through the list is a pass.

After the first pass, the largest element has been carried, swap by swap, to the end of the list, like a bubble rising to the top of water. After the second pass, the second-largest is in place, and so on. So for n elements, bubble sort needs n − 1 passes.

Example: in pass 1 on [8, 7, 13, 1, -9, 4]: 8 and 7 are swapped; 8 and 13 are in order; then 13 is swapped with 1, with -9 and with 4. The result is [7, 8, 1, -9, 4, 13]: the largest element is at the end.

The elements already sorted at the end need not be compared again, so in pass i, the inner loop runs only n − i − 1 times.

If a pass makes no swaps at all, the list is already sorted, and the remaining passes are not needed. A flag variable can record whether any swap happened, and stop the sort early.