Computer Science: Class 12 — Chapter 5: Sorting

• Numerical Sorting : Arranging a list of numbers in ascending (increasing) or descending (decreasing) order.
• Lexicographical Sorting : Arranging strings in alphabetical order (a-z or z-a) or according to string length (e.g., words in a dictionary).
• Physical/Logistical Sorting : Assigning examination hall seats based on candidate roll numbers, or sorting students by height or weight.

Searching through an unsorted collection requires a linear scan, which is highly inefficient ($O(n)$ complexity). Sorting the collection beforehand introduces an initial computational overhead but drastically reduces subsequent search \times (e.g., enabling Binary Search with $O(\log n)$ complexity).

• Pass : A single complete iteration through the unsorted portion of the list.
• For a list of size $n$, Bubble Sort requires a maximum of $n - 1$ passes to guarantee a sorted state.
• In each pass, the largest unsorted element "bubbles up" to its correct terminal position. Consequently, the unsorted sublist size decreases by 1 in each successive pass.

  
    BUBBLESORT(numList, n)
    Step 1: SET i = 0
    Step 2: WHILE i < n REPEAT STEPS 3 to 8
    Step 3:   SET j = 0
    Step 4:   WHILE j < n - i - 1 REPEAT STEPS 5 to 7
    Step 5:     IF numList[j] > numList[j+1] THEN
    Step 6:       swap(numList[j], numList[j+1])
    Step 7:     SET j = j + 1
    Step 8:   SET i = i + 1
  

  
    def bubble_Sort(list1):
    n = len(list1)
    for i in range(n):
    # Last i elements are already sorted, so we skip them
    for j in range(0, n - i - 1):
    if list1[j] > list1[j+1]:
    # Swap adjacent elements
    list1[j], list1[j+1] = list1[j+1], list1[j]
    numList = [8, 7, 13, 1, -9, 4]
    bubble_Sort(numList)
    print("The sorted list is :", numList)
  

In standard Bubble Sort, even if the list becomes sorted before completing $n-1$ passes, the algorithm continues executing redundant passes. We can optimize this by introducing a boolean flag to track whether any swaps occurred during a pass. If no swaps occur, the list is already sorted, and we can break early.

  
    def optimized_bubble_sort(list1):
    n = len(list1)
    for i in range(n):
    swapped = False
    for j in range(0, n - i - 1):
    if list1[j] > list1[j+1]:
    list1[j], list1[j+1] = list1[j+1], list1[j]
    swapped = True
    if not swapped:
    break # Exit early if no elements were swapped
  

1. Initially, the sorted sublist is empty, and the unsorted sublist contains all elements.
2. In each pass, the algorithm scans the unsorted sublist to find the minimum element.
3. The found minimum element is then swapped with the leftmost element of the unsorted sublist, making it part of the sorted sublist.
4. This process repeats for $n - 1$ passes, reducing the unsorted sublist size by 1 in each pass.

  
    SELECTIONSORT(numList, n)
    Step 1: SET i = 0
    Step 2: WHILE i < n REPEAT STEPS 3 to 11
    Step 3:   SET min = i, flag = 0
    Step 4:   SET j = i + 1
    Step 5:   WHILE j < n REPEAT STEPS 6 to 10
    Step 6:     IF numList[j] < numList[min] THEN
    Step 7:       min = j
    Step 8:       flag = 1
    Step 9:     IF flag = 1 THEN
    Step 10:      swap(numList[i], numList[min])
    Step 11:  SET i = i + 1
  

  
    def selection_Sort(list2):
    n = len(list2)
    for i in range(n):
    min_idx = i
    flag = 0
    for j in range(i + 1, n):
    if list2[j] < list2[min_idx]:
    min_idx = j
    flag = 1
    if flag == 1:
    # Swap the found minimum element with the first element of unsorted part
    list2[i], list2[min_idx] = list2[min_idx], list2[i]
    numList = [8, 7, 13, 1, -9, 4]
    selection_Sort(numList)
    print("The sorted list is :", numList)
  

• The list is conceptually split into a sorted and an unsorted region.
• In each pass, the first element of the unsorted region (the key/temp) is selected.
• The algorithm traverses the sorted region backward, shifting all elements larger than the key one position to the right to make space.
• The key is then inserted into its correct relative position.

  
    INSERTIONSORT(numList, n)
    Step 1: SET i = 1
    Step 2: WHILE i < n REPEAT STEPS 3 to 9
    Step 3:   temp = numList[i]
    Step 4:   SET j = i - 1
    Step 5:   WHILE j >= 0 and numList[j] > temp REPEAT STEPS 6 to 7
    Step 6:     numList[j+1] = numList[j]
    Step 7:     SET j = j - 1
    Step 8:   numList[j+1] = temp
    Step 9:   SET i = i + 1
  

  
    def insertion_Sort(list3):
    n = len(list3)
    for i in range(1, n):
    temp = list3[i]
    j = i - 1
    # Shift elements of list3[0..i-1] that are greater than temp
    while j >= 0 and temp < list3[j]:
    list3[j+1] = list3[j]
    j = j - 1
    list3[j+1] = temp
    numList = [8, 7, 13, 1, -9, 4]
    insertion_Sort(numList)
    print("The sorted list is :", numList)
  

• Constant Time ($O(1)$) : Algorithms without loops. The number of execution steps remains constant regardless of data size.
• Linear Time ($O(n)$) : Algorithms containing a single loop running from $1$ to $n$. Execution steps grow proportionally with input size.
• Quadratic Time ($O(n^2)$) : Algorithms containing nested loops (a loop within a loop). Execution steps grow quadratically with input size.

All three sorting algorithms discussed in this chapter (Bubble Sort, Selection Sort, and Insertion Sort) utilize nested loops to perform comparisons and swaps. Consequently, they all exhibit a worst-case time complexity of $O(n^2)$.