10.1.2 Sorting Algorithms

What Are Sorting Algorithms?

Sorting algorithms are methods for organizing a list of elements (e.g., numbers, strings) into a specific order, such as ascending or descending. They are fundamental in computer science and mathematics. This note explains two key algorithms: Bubble Sort and Quick Sort.

Bubble Sort

Overview

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

Algorithm Steps

1. Start at the beginning of the list.
2. Compare the first pair of adjacent elements.
3. Swap them if the first element is larger than the second (for ascending order).
4. Move to the next pair and repeat until the end of the list.
5. Repeat steps $1–4$ for $n-1$ passes (where $n$ is the length of the list).

Pseudocode

FOR i = 1 TO n - 1:
    FOR j = 1 TO n - i:
        IF list[j] > list[j+1]:
            SWAP list[j] and list[j+1]

Complexity of Bubble Sort

• Time Complexity: $O(n^2)$ in the worst case (e.g., a reverse-ordered list).
• Space Complexity: $O(1)$ as sorting is performed in place.

Quick Sort

Overview

Quick Sort is a divide-and-conquer algorithm that selects a pivot and partitions the list into two sublists:

• Elements smaller than the pivot.
• Elements larger than the pivot. The process is recursively repeated on the sublists.

Algorithm Steps

1. Select a pivot (e.g., the middle element).
2. Partition the list into two sublists:

• Left sublist: Elements smaller than the pivot.
• Right sublist: Elements larger than the pivot.

3. Recursively apply Quick Sort to the left and right sublists.
4. Combine the sublists and pivot them into a sorted list.

Pseudocode

QuickSort(list):
    IF length of list ≤ 1:
        RETURN list
    ELSE:
        pivot = middle element of list
        left = elements < pivot
        right = elements > pivot
        RETURN QuickSort(left) + [pivot] + QuickSort(right)

Complexity of Quick Sort

• Best Case: $O(n \log n)$ when partitions are balanced.
• Worst Case: $O(n^2)$ when partitions are unbalanced (e.g., pivot is the smallest or largest element).
• Space Complexity: $O(\log n)$ for recursion.

Comparison: Bubble Sort vs. Quick Sort

Aspect	Bubble Sort	Quick Sort
Time Complexity	$O(n^2)$	Best: $O(n \log n)$, Worst: $O(n^2)$
Space Complexity	$O(1)$ (in place)	$O(\log n)$ (recursive calls)
Use Case	Small or nearly sorted lists	Large, random, or unsorted lists

Note Summary