Sorting Arrays: Bubble, Selection and Insertion Sort

Hello students, welcome to Kwickprep. Your teacher wants the marks list arranged from lowest to highest. How does a computer put numbers in order? Today we learn bubble sort, selection sort and insertion sort, pass by pass, and compare all three.

Let us begin with a few words. Sorting means arranging values in a fixed order. Ascending order goes from smallest to largest, like one, two, three. Descending order goes from largest to smallest, like a ranking list. A pass means one full round through the array, and a sort needs several passes.

Every sort needs to swap two values, which means exchange them. You cannot just write P equals Q, because the old value of P would be lost. So we use a third variable T, short for temporary, like an empty glass. T keeps P, then P takes Q, and then Q takes T. Now P is nine and Q is five.

Bubble sort works by comparing neighbours. It compares each element with the one just after it. If the left one is bigger, the two are swapped. After one pass, the largest value has moved to the end, like a bubble rising to the top. So for N values, at most N minus one passes are needed.

Let us sort five, one, four, two. At the start, nothing is in its final place. In pass one, five is swapped with one, then with four, then with two, so five reaches the end. In pass two, one and four stay, four and two swap, so four is now fixed too. In pass three, no swaps happen, and the array is fully sorted.

Here is the core of bubble sort, where A is the array and N is its length. The outer loop counts the passes, which is N minus one passes. The inner loop compares neighbours, J and J plus one. Each pass can stop one place earlier, because the end is already sorted. If the left value is bigger, the three lines swap them using T. To sort in descending order, just change greater than to less than.

Pause and predict. For an array of five values, how many comparisons does bubble sort make in total? Pass one makes four comparisons, pass two makes three, then two, then one. So the total is ten comparisons, even if the array was already sorted.

Selection sort is like picking the shortest student first for a class photo line. In each pass, it finds the smallest value in the unsorted part. Then it swaps that value into the first unsorted position. So the sorted part at the front grows by one after every pass. Unlike bubble sort, it does at most one swap in each pass.

Let us sort twenty nine, ten, fourteen, thirty seven and thirteen. This is the starting array. In pass one, the smallest is ten, so it swaps with twenty nine at the front. In pass two, the smallest of the rest is thirteen, so it swaps with twenty nine. In pass three, fourteen is already in the right place, so nothing moves. In pass four, twenty nine swaps with thirty seven, and the array is sorted.

Here is the core of selection sort. The outer loop picks the position to fill, starting from index zero. M stores the index of the smallest value found so far. The inner loop checks the rest of the array, and updates M when it finds a smaller value. After the inner loop, one swap puts the smallest value into its place.

Insertion sort is taught in the higher classes of some boards, and it is easy to picture. Think of arranging playing cards in your hand, one card at a time. We take the next value and call it the key. Every bigger value in the sorted part moves one step to the right. Then the key drops into the gap that is left.

Let us sort five, two, four, one. At the start, the first value five is treated as a sorted part of one. In pass one, the key is two. Five shifts right, and two goes in front. In pass two, the key is four. Five shifts right, and four sits between two and five. In pass three, the key is one. Five, four and two all shift right, and one goes to the front.

Here is the core of insertion sort. The outer loop starts at index one, because one value alone is already sorted. Key is the value to insert, and J starts just before it. The while loop shifts each bigger value one step right, and moves J to the left. It stops at the start of the array, or at a value that is not bigger. Finally, the key goes into position J plus one.

Now let us compare the three sorts. Bubble sort swaps neighbours again and again, so it can make many swaps. Selection sort picks the smallest value and makes only one swap in each pass. Insertion sort shifts values and inserts the key, and it is very fast when the array is almost sorted. For large arrays, all three become slow, because the work grows with N times N.

Some exams ask for bubble sort in pseudocode. This shows one pass over an array of five values, where the first index is one. If a value is bigger than the next one, the three lines swap them using Temp. The loop closes with next J, and an outer loop repeats this pass four times.

Let us revise. To swap two values, use a temporary variable. Bubble sort swaps neighbours, and the largest value reaches the end in each pass. Selection sort finds the smallest value and makes one swap per pass. Insertion sort shifts bigger values right and inserts the key. And N values need N minus one passes. Trace each sort on paper with your own numbers.