Sorting Algorithms | AI Pathshala

Definition

How would you arrange a pile of answer sheets by marks, by hand?

A sorting algorithm puts items in order. Selection sort repeatedly finds the smallest remaining item and moves it to the front. Bubble sort repeatedly swaps neighbouring items that are in the wrong order. Insertion sort takes items one at a time and inserts each into its correct place among those already sorted.

In simple words

Selection sort: find the lowest mark, put it first; find the next lowest, put it second. Bubble sort: walk along the line, swapping any neighbours in the wrong order; big numbers 'bubble' to the end. Insertion sort: like sorting playing cards in your hand, slide each new card into place.

Why it matters

Sorting comes before binary search, before finding medians, and before ranking search results. Writing simple sorts by hand teaches comparisons, swaps and loops inside loops, and shows why Python's built-in sorted() is so much faster.

How it works

Algorithm	Idea	Worst-case work
Selection sort	Pick the smallest, move it to the front	n²
Bubble sort	Swap wrong-order neighbours, pass after pass	n²
Insertion sort	Insert each item into the sorted part	n², but fast on nearly sorted lists
Python's sorted()	Timsort, a refined merge and insertion sort	n log n

In code

Three hand-written sorts, each checked against sorted(). Bubble sort prints the list after every pass.

sorting.py

def selection_sort(items):
    items = items.copy()
    for i in range(len(items)):
        smallest = min(range(i, len(items)), key=lambda j: items[j])
        items[i], items[smallest] = items[smallest], items[i]
    return items

def bubble_sort(items):
    items = items.copy()
    for done in range(len(items) - 1):
        for j in range(len(items) - 1 - done):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
        print("  after pass", done + 1, items)
    return items

def insertion_sort(items):
    items = items.copy()
    for i in range(1, len(items)):
        current, j = items[i], i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current
    return items

scores = [64, 25, 91, 12, 47]
print("Selection:", selection_sort(scores))
print("Bubble:")
result = bubble_sort(scores)
print("Insertion:", insertion_sort(scores))
print("All match sorted():", selection_sort(scores) == result == insertion_sort(scores) == sorted(scores))

Output

Selection: [12, 25, 47, 64, 91]
Bubble:
  after pass 1 [25, 64, 12, 47, 91]
  after pass 2 [25, 12, 47, 64, 91]
  after pass 3 [12, 25, 47, 64, 91]
  after pass 4 [12, 25, 47, 64, 91]
Insertion: [12, 25, 47, 64, 91]
All match sorted(): True

Try it yourself

Predict the list after one pass

Start from [5, 1, 4, 2]. What does each algorithm give after its first pass?

Bubble sort, first pass
Selection sort, first pass
Insertion sort, after placing the third item

Common mistakes

Forgetting that the inner loop of bubble sort can stop earlier each pass.
Sorting the original list by accident when you wanted a copy.
Writing your own sort in real projects. Use sorted() unless you are learning.

Check yourself

1. Which sort repeatedly swaps neighbouring items?

2. After the first pass of bubble sort, where is the largest item?

3. Why use sorted() in real code?

Summary

Selection, bubble and insertion sort are simple n² algorithms.
They teach comparisons, swaps and nested loops.
Python's sorted() uses Timsort, n log n, and is the one to use.

Finished reading?

Sources: W3Schools DSA: Bubble Sort · W3Schools DSA with Python