Sorting

Written and reviewed by Rohit Singh, Computer Science & Commerce faculty at UniDrill (MCA, Osmania University · 6 years teaching). Based on NCERT Computer Science Class XII, Chapter 5.

Why sort at all?

Suppose a list holds 1,00,000 names. If it is jumbled, finding one name may mean checking every single entry, up to 1,00,000 checks. If the same list is sorted, a method called binary search needs at most 17 checks. Sorting costs effort once, and every search afterwards gets dramatically cheaper. That upfront cost is worth paying when a collection is big and searched often.

Sorting means arranging the elements of a collection in a particular order: ascending (small to large), descending (large to small) or alphabetical. A dictionary is sorted alphabetically, an exam hall by roll number, a line of students by height. This chapter covers three simple algorithms and then asks how fast they are.

Throughout, the example list is numList = [8, 7, 13, 1, -9, 4], sorted into ascending order. A pass is one full sweep through the list (or the part of it still being worked on), and a swap exchanges the positions of two elements.

Bubble sort

The idea. Compare neighbours and swap them if they are in the wrong order. After one pass, the largest element has been carried all the way to the end, like a bubble rising. That element is now in its final place and is left alone in later passes. A list of n elements needs n − 1 passes.

Here is pass 1 in detail. Each row compares one neighbouring pair.

The 13 is picked up at the third comparison and carried to the end. Every later pass works on a shorter list, because the sorted end is excluded. The full run looks like this.

The comparisons shrink from 5 to 1, which is why the inner loop stops at n - i - 1. There are 5 + 4 + 3 + 2 + 1 = 15 comparisons in all, and the same count appears for any list of 6 elements.

The outer loop counts passes. The inner loop makes the comparisons, and list1[j], list1[j + 1] = list1[j + 1], list1[j] swaps two elements in one line. Writing range(n) for the outer loop also works, because the extra last pass has an empty inner loop and does nothing. The common wrong step is an inner loop bound of n - 1 instead of n - i - 1: it keeps comparing elements that are already in their final place.

Worked example: bubble sort of [5, 1, 4, 2, 8]. What does the list look like after each pass?

After pass 2 the last two elements are 5 and 8. Passes 3 and 4 find nothing to swap, because the list became sorted early. The plain algorithm still carries out all n − 1 passes.

Pause and predict: how many swaps does bubble sort make on the reversed list [4, 3, 2, 1]?

Check your answer: 6. Pass 1 makes 3 swaps, pass 2 makes 2 and pass 3 makes 1. A reversed list is the worst case, and every comparison leads to a swap: 3 + 2 + 1 = 6.

Selection sort

The idea. Split the list into a sorted part on the left (empty at first) and an unsorted part on the right. In every pass, scan the whole unsorted part to find its smallest element, and swap that element with the leftmost element of the unsorted part. The sorted part grows by one each pass, and a list of n elements needs n − 1 passes. At most one swap happens per pass, and it comes after the scan, not during it.

Passes 4 and 5 found the smallest element already sitting at the start of the unsorted part, so nothing moved.

The variable min_idx remembers the position of the smallest value seen so far, and flag records whether a smaller element was found. The swap line runs only when flag is 1, once per pass at most.

Worked example: selection sort of [29, 10, 14, 37, 13]. Four passes are needed.

Pass 3 changes nothing because 14 is already in place. The whole sort used 3 swaps.

Pause and predict: how many swaps does selection sort make on an already sorted list?

Check your answer: None. In every pass the smallest unsorted element is already at the left of the unsorted part, so flag stays 0 and no swap is executed. The scanning still happens in full.

Insertion sort

The idea. Again the list has a sorted part on the left, but now it starts with just the first element. In each pass, take the first element of the unsorted part and call it temp. Compare temp with the sorted elements from right to left. Each sorted element bigger than temp is shifted one place to the right to open a gap, and temp drops into the gap. This is how most people sort playing cards in hand.

In pass 2 the element 13 is already bigger than everything on its left, so nothing shifts. Pass 4 is the costliest: -9 is smaller than all four sorted elements, so all four shift.

The condition j >= 0 stops the loop at the left edge. The line list3[j + 1] = list3[j] is the shift, and the last line places temp in the gap. Notice that elements are shifted, not swapped. temp is written once per pass, at the end.

Worked example: insertion sort of [12, 11, 13, 5, 6].

After pass 3 the list is [5, 11, 12, 13, 6]: the first four elements are sorted and 6 is still waiting.

The three sorts side by side

All three give exactly the same sorted output. They differ only in the route they take.

Worked example: the same list, three routes. For [8, 7, 13, 1, -9, 4], bubble sort made 4 + 3 + 3 + 1 + 0 = 11 swaps, selection sort made 3 swaps, and insertion sort made 1 + 0 + 3 + 4 + 3 = 11 shifts. Selection sort moves data the least. Bubble swaps and insertion shifts match here because both count how many pairs of elements are in the wrong order.

Time complexity

Time complexity tells you how the running time of an algorithm grows as the amount of data grows. For small lists every algorithm feels instant, but for millions of records the choice of algorithm decides whether a program takes seconds or hours. Instead of measuring seconds, which depend on the computer, we look at the structure of the loops.

Bubble, selection and insertion sort each contain a loop inside a loop, so all three are quadratic. This is why "which of these three has the best time complexity?" has the answer "all the same, n²".

Worked example: counting comparisons. How does the work grow with n? The nested loops of bubble sort run this many comparisons:

For n elements the count is n(n − 1)/2.

Doubling the size of the list makes a quadratic algorithm do roughly four times the work. That is the real meaning of n².

Beyond the textbook. For the exam: all three sorts have time complexity n². In reality: n² is the worst case. Insertion sort on an already sorted list makes only n − 1 comparisons, since every element is compared once with its left neighbour and no shifting happens. Bubble sort can also stop early if a whole pass makes no swap. Still, never answer "insertion sort is faster" in a CUET question unless the data is described as nearly sorted.

Beyond the textbook. For the exam: sorting is done by writing algorithms like those above. In reality: Python already has fast sorting built in. sorted(data) returns a new sorted list and leaves data unchanged, while data.sort() sorts the list in place and returns None. So print(data.sort()) prints None. Both use an algorithm called Timsort, far faster than the quadratic ones for large lists. Pass reverse=True for descending order.

Exam traps

60-second revision

Where this chapter connects

A sorted list is what makes fast lookup possible, which is the subject of Searching. The list operations that sorting relies on, indexing, swapping and shifting, are the same ones used to build Stack and Queue in Python.