Sorting Algorithms

1. Introduction to Sorting

Sorting refers to arranging data in a particular order — usually ascending (smallest to largest) or descending (largest to smallest).

Python has built-in sorting: list.sort() (in-place) and sorted() (returns new list). However, understanding how sorting algorithms work is important for logic building and problem-solving.

2. Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process repeats until no swaps are needed.

Algorithm:

1. Compare adjacent elements. If the first is greater than the second, swap them.
2. After each pass, the largest element "bubbles up" to its correct position at the end.
3. Repeat for the remaining unsorted elements.

Python Implementation:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # Already sorted
    return arr

# Example
nums = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(nums))  # [11, 12, 22, 25, 34, 64, 90]

Complexity Analysis:

• Time: O(n²) worst case, O(n) best case (when already sorted, with optimization)
• Space: O(1) — in-place sorting

3. Selection Sort

Selection Sort repeatedly finds the smallest element from the unsorted part and puts it at the beginning.

Algorithm:

1. Find the minimum element in the unsorted portion.
2. Swap it with the first element of the unsorted portion.
3. Move the boundary between sorted and unsorted portions one step to the right.

Python Implementation:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Example
nums = [64, 25, 12, 22, 11]
print(selection_sort(nums))  # [11, 12, 22, 25, 64]

Complexity Analysis:

• Time: O(n²) in all cases
• Space: O(1) — in-place sorting

4. Insertion Sort

Insertion Sort builds the final sorted array one element at a time. It picks elements from the unsorted part and inserts them into their correct position in the sorted part.

Algorithm:

1. Start with the second element (first element is considered sorted).
2. Pick the current element and compare it with elements in sorted portion.
3. Shift all larger elements one position to the right.
4. Insert the current element at its correct position.

Python Implementation:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example
nums = [12, 11, 13, 5, 6]
print(insertion_sort(nums))  # [5, 6, 11, 12, 13]

Complexity Analysis:

• Time: O(n²) worst case, O(n) best case (already sorted)
• Space: O(1) — in-place sorting

5. Comparison of Sorting Algorithms

Note: For CBSE Class 11, focus on understanding the logic and being able to trace through each algorithm step-by-step with small arrays.