Sorting (Section B1)

Sorting

SORTING TECHNIQUES IN DATA STRUCTURES: COMPLETE STUDY NOTES

1. Introduction to Sorting

Sorting is the systematic process of ordering or arranging a given collection of elements in a specific order. This order can be:

• Numeric: Ascending (increasing) or descending (decreasing).

• Lexicographical (Strings): Alphabetical order (A-Z or Z-A) or based on string length.

Importance of Sorting: In computer science, sorting is crucial because it significantly enhances the efficiency of searching. 

For example, finding a word in a dictionary is easy because it is sorted alphabetically; if it were unordered, you would have to check every single page. 

While sorting a large number of items involves "overhead" (extra processing time), it is considered worth it compared to the time saved during retrieval.

2. Bubble Sort

Bubble Sort is the simplest sorting algorithm. It works by repeatedly comparing adjacent elements in a list and swapping them if they are in the wrong order.

2.1 Logic and Procedure

• The "Bubbling" Effect: In each iteration (called a pass), the largest unordered element "bubbles up" to its correct position at the end of the list.

• Passes: For a list with n elements, Bubble Sort requires a total of n−1 passes to guarantee the list is sorted.

• Reduction: After each pass, the list of elements to be compared is reduced by one, as the end of the list becomes progressively sorted.

2.2 Python Implementation

def bubble_Sort(list1):

  n = len(list1)

    for i in range(n):     # Number of passes

        # Range is n-i-1 because the last i elements are already sorted

        for j in range(0, n-i-1):

            if list1[j] > list1[j+1]:

                # Swap elements if they are in the wrong order

                list1[j], list1[j+1] = list1[j+1], list1[j]

# Example Usage

numList = [8, 7, 13, 1, -9, 4]

bubble_Sort(numList)

print("Sorted list:", numList)

2.3 Dry Run (Example: [8, 7, 13, 1, -9, 4])

• Pass 1:

  • Compare 8 and 7: Swap → [7, 8, 13, 1, -9, 4]

  • Compare 8 and 13: No change.

  • Compare 13 and 1: Swap → [7, 8, 1, 13, -9, 4]

  • Compare 13 and -9: Swap → [7, 8, 1, -9, 13, 4]

  • Compare 13 and 4: Swap → [7, 8, 1, -9, 4, 13] (13 is now sorted).

• Passes 2–5: The process continues, identifying the next largest elements (8, 7, 4, etc.) and moving them to the end until the entire list is sorted.

2.4 Complexity Analysis

• Best Case: The list is already sorted. However, the standard algorithm still performs n2 comparisons unless a "flag" is used to detect if any swaps occurred.

Worst Case: The list is sorted in reverse order. This requires the maximum number of swaps and comparisons (O(n2)).

Average Case: O(n2).

3. Selection Sort

Selection Sort improves on bubble sort by reducing the number of swaps. In each pass, it "selects" the smallest element from the unsorted part and places it at the beginning.

3.1 Logic and Procedure

• Divided List: The list is conceptually divided into a Sorted part (on the left) and an Unsorted part (on the right).

• Process:

  1. Search the entire unsorted part to find the minimum element.

  2. Swap that minimum element with the leftmost element of the unsorted part.

  3. Move the boundary of the sorted part one position to the right.

• Passes: For n elements, it makes n−1 passes.

3.2 Python Implementation

def selection_Sort(list2):

    n = len(list2)

    for i in range(n):

        min_idx = i  # Assume the first unsorted element is the minimum

        for j in range(i + 1, n):

            if list2[j] < list2[min_idx]:

                min_idx = j  # Found a new minimum

        # Swap the found minimum element with the first unsorted element

        list2[i], list2[min_idx] = list2[min_idx], list2[i]

# Example Usage

numList = [8, 7, 13, 1, -9, 4]

selection_Sort(numList)

3.3 Dry Run (Example: [8, 7, 13, 1, -9, 4])

• Pass 1: Unsorted part is index 0–5. Smallest is -9. Swap -9 with 8 → [-9, 7, 13, 1, 8, 4].

• Pass 2: Unsorted part is index 1–5. Smallest is 1. Swap 1 with 7 → [-9, 1, 13, 7, 8, 4].

• Pass 3: Unsorted part is index 2–5. Smallest is 4. Swap 4 with 13 → [-9, 1, 4, 7, 8, 13].

• Conclusion: In this specific example, the list is actually sorted after Pass 3, but the algorithm continues its passes to confirm.

3.4 Complexity Analysis

All Cases (Best, Worst, Average): O(n2). Selection sort is unique because it always performs the same number of comparisons regardless of how sorted the initial list is, as it must always scan the entire unsorted part to find the minimum.

4. Insertion Sort

Insertion Sort is an intuitive algorithm, similar to the way people sort a hand of playing cards.

4.1 Logic and Procedure

• Mechanism: It picks one element at a time from the unsorted part and inserts it into its correct relative position within the already sorted part.

• Shifting: To make room for the new element, the algorithm shifts all larger elements in the sorted part one position to the right.

• Passes: It begins with the second element (index 1), assuming the first element (index 0) is a "sorted list" of size one.

4.2 Python Implementation

def insertion_Sort(list3):

    n = len(list3)

    for i in range(1, n):  # Start from the second element

        temp = list3[i]    # The element to be inserted

        j = i - 1

        # Shift elements of the sorted part that are greater than temp

        while j >= 0 and temp < list3[j]:

            list3[j + 1] = list3[j]

            j = j - 1

        # Insert temp at its correct position

        list3[j + 1] = temp

# Example Usage

numList = [8, 7, 13, 1, -9, 4]

insertion_Sort(numList)

4.3 Dry Run (Example: [8, 7, 13, 1, -9, 4])

• Pass 1 (temp=7): 7 < 8. Shift 8 right. Insert 7 → [7, 8, 13, 1, -9, 4].

• Pass 2 (temp=13): 13 > 8. No change → [7, 8, 13, 1, -9, 4].

• Pass 3 (temp=1): 1 < 13, 1 < 8, 1 < 7. Shift 13, 8, 7 right. Insert 1 → [1, 7, 8, 13, -9, 4].

• Pass 4 (temp=-9): -9 is smaller than all. Shift all right. Insert -9 → [-9, 1, 7, 8, 13, 4].

• Pass 5 (temp=4): 4 is inserted between 1 and 7 → [-9, 1, 4, 7, 8, 13].

4.4 Complexity Analysis

• Best Case: The list is already sorted. The inner loop never runs. Complexity is Linear (O(n)).

• Worst Case: The list is in reverse order. Every element must be compared and shifted across the entire sorted part. Complexity is Quadratic (O(n2)).

• Average Case: O(n2).

5. Summary and Comparison Table

Feature	Bubble Sort	Selection Sort	Insertion Sort
Core Idea	Compare adjacent and swap	Select minimum and swap	Insert into sorted part
Best Case Time	O(n2) (or O(n) if optimized)	O(n2)	O(n)
Worst Case Time	O(n2)	O(n2)	O(n2)
Average Case Time	O(n2)	O(n2)	O(n2)
Swaps	High (in every pass)	Low (one swap per pass)	Moderate (shifts)
Stability	Generally Stable	Unstable	Stable
Real-world Analogy	Bubbles rising in water	Choosing players for a team	Sorting playing cards

6. Estimating Time Complexity: Key Rules

Computer scientists use these general rules to evaluate algorithms:

1. Constant Time (1): Algorithms without loops.

2. Linear Time (n): A single loop that runs from 1 to n.

3. Quadratic Time (n2): A loop within a loop (nested loops).

Since all three sorting techniques (Bubble, Selection, and Insertion) rely on nested loops in their Python implementation, they are all categorized as Quadratic Time Algorithms (n2) for their general/worst cases.