Lesson 16 • Advanced

Sorting Algorithms

40 minutes

Algorithms

📊 What is Sorting?

Sorting is the process of arranging data in a specific order (ascending or descending). It's one of the most fundamental operations in computer science and is used everywhere - from organizing contacts to ranking search results.

Why Sorting Matters

Sorted data enables:

Faster searching: Binary search works only on sorted data
Better organization: Easier to find and analyze data
Efficiency: Many algorithms work better with sorted input
User experience: Results in logical, expected order

Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. Larger values "bubble up" to the end.

Example: Bubble Sort

Algorithm BubbleSort

var arr = [64, 34, 25, 12, 22, 11, 90]
var n = Size(arr)

Print "Original array:"
For i = 0 To n - 1
    Print arr[i], " "
Endfor
Print ""
Print ""

# Bubble sort algorithm
For i = 0 To n - 2
    For j = 0 To n - i - 2
        # Compare adjacent elements
        If arr[j] > arr[j + 1] Then
            # Swap elements
            var temp = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = temp
        Endif
    Endfor
Endfor

Print "Sorted array:"
For i = 0 To n - 1
    Print arr[i], " "
Endfor
Print ""

Endalgorithm

Output

Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90

How Bubble Sort Works:

Pass 1: [64, 34, 25, 12, 22, 11, 90]
        → [34, 64, 25, 12, 22, 11, 90]  (swap 64, 34)
        → [34, 25, 64, 12, 22, 11, 90]  (swap 64, 25)
        → [34, 25, 12, 64, 22, 11, 90]  (swap 64, 12)
        ... 90 bubbles to end

Pass 2: [34, 25, 12, 22, 11, 64, 90]
        ... 64 bubbles to second-last position

... continues until fully sorted

Selection Sort

Selection Sort finds the minimum element and places it at the beginning, then repeats for the remaining unsorted portion.

Example: Selection Sort

Algorithm SelectionSort

var arr = [29, 10, 14, 37, 13]
var n = Size(arr)

Print "Original:"
For i = 0 To n - 1
    Print arr[i], " "
Endfor
Print ""
Print ""

# Selection sort algorithm
For i = 0 To n - 2
    # Find minimum in unsorted portion
    var minIndex = i
    
    For j = i + 1 To n - 1
        If arr[j] < arr[minIndex] Then
            minIndex = j
        Endif
    Endfor
    
    # Swap minimum with first unsorted element
    If minIndex != i Then
        var temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    Endif
Endfor

Print "Sorted:"
For i = 0 To n - 1
    Print arr[i], " "
Endfor
Print ""

Endalgorithm

📥 Insertion Sort

Insertion Sort builds the sorted array one item at a time by inserting each element into its correct position.

Example: Insertion Sort

Algorithm InsertionSort

var arr = [12, 11, 13, 5, 6]
var n = Size(arr)

Print "Original:"
For i = 0 To n - 1
    Print arr[i], " "
Endfor
Print ""
Print ""

# Insertion sort algorithm
For i = 1 To n - 1
    var key = arr[i]
    var j = i - 1
    
    # Move elements greater than key one position ahead
    While j >= 0 and arr[j] > key Do
        arr[j + 1] = arr[j]
        j = j - 1
    Endwhile
    
    # Insert key in correct position
    arr[j + 1] = key
Endfor

Print "Sorted:"
For i = 0 To n - 1
    Print arr[i], " "
Endfor
Print ""

Endalgorithm

⚖️ Algorithm Comparison

Algorithm	Concept	Best For	Difficulty
Bubble Sort	Compare adjacent, swap if wrong order	Small arrays, learning	Easy
Selection Sort	Find minimum, place at start	Small arrays, minimal swaps	Easy
Insertion Sort	Insert each element in correct position	Nearly sorted data	Medium

Real-World Application

Example: High Score Leaderboard

Algorithm Leaderboard

var players = ["Alice", "Bob", "Charlie", "Diana", "Eve"]
var scores = [850, 1200, 750, 950, 1100]
var n = 5

Print "=== ORIGINAL SCORES ==="
For i = 0 To n - 1
    Print players[i], ":", scores[i]
Endfor

# Sort by score (descending) using bubble sort
For i = 0 To n - 2
    For j = 0 To n - i - 2
        # Swap if current score is lower than next (descending)
        If scores[j] < scores[j + 1] Then
            # Swap scores
            var tempScore = scores[j]
            scores[j] = scores[j + 1]
            scores[j + 1] = tempScore
            
            # Swap corresponding player names
            var tempName = players[j]
            players[j] = players[j + 1]
            players[j + 1] = tempName
        Endif
    Endfor
Endfor

Print ""
Print "=== LEADERBOARD (Highest to Lowest) ==="
For i = 0 To n - 1
    Print "#", i + 1, "-", players[i], ":", scores[i]
Endfor

Endalgorithm

Output

=== ORIGINAL SCORES === Alice: 850 Bob: 1200 Charlie: 750 Diana: 950 Eve: 1100 === LEADERBOARD (Highest to Lowest) === #1 - Bob: 1200 #2 - Eve: 1100 #3 - Diana: 950 #4 - Alice: 850 #5 - Charlie: 750

Sorting Tips

Best Practices

Choose wisely: For small data, simple algorithms work fine
Test thoroughly: Try with various inputs (sorted, reverse, duplicates)
Understand trade-offs: Simple vs. fast algorithms
Consider stability: Should equal elements maintain original order?

Key Takeaways

✅ Sorting arranges data in a specific order
✅ Bubble Sort: Compare adjacent, swap if wrong order
✅ Selection Sort: Find minimum, place at start
✅ Insertion Sort: Insert each element in correct position
✅ All use nested loops and comparisons
✅ Can sort parallel arrays (e.g., names with scores)
✅ Choose algorithm based on data size and characteristics

💪 Practice Exercises

Try These Exercises

Exercise 1: Sort Names Alphabetically

Use bubble sort to sort an array of names in alphabetical order (compare strings).

Exercise 2: Descending Sort

Modify selection sort to sort numbers in descending order (largest to smallest).

Exercise 3: Student Sorter

Create a program that sorts students by their grades while keeping names matched with grades.

Exercise 4: Count Swaps

Modify bubble sort to count and display how many swaps were needed to sort the array.

Excellent Work!

You now understand fundamental sorting algorithms! In the next lesson, we'll explore searching algorithms to find data efficiently.