Selection Sort Algorithm

Master the simplest sorting algorithm step by step

🔍 What is Selection Sort?

Selection Sort is like organizing your bookshelf by repeatedly finding the smallest book and placing it at the beginning. It's simple to understand and implement, making it perfect for learning sorting concepts! 


# Selection Sort in action!
def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Example
numbers = [64, 34, 25, 12, 22, 11, 90]
print("Sorted:", selection_sort(numbers))
O(n²)
Time Complexity
O(1)
Space Complexity
Simple
To Understand

Selection Sort Characteristics

🎯

In-Place Sorting

Uses only O(1) extra memory space

Memory Efficient No Extra Arrays
🔄

Not Stable

May change relative order of equal elements

Order Changes Simple Logic
📊

Consistent Performance

Always O(n²) regardless of input

Predictable No Best Case
🎓

Educational Value

Perfect for learning sorting concepts

Easy to Code Clear Logic

Lesson 1: Understanding the Selection Process

Selection Sort works by finding the minimum element and placing it at the beginning, then repeating for the remaining elements:

Selection Sort Steps: [64, 34, 25, 12, 22, 11, 90]

64
34
25
12
22
11
90
0
1
2
3
4
5
6
Step-by-Step Selection Sort 
def selection_sort_detailed(arr):
    """Selection Sort with detailed steps"""
    n = len(arr)
    print(f"Starting array: {arr}")
    
    for i in range(n):
        # Find minimum element in remaining array
        min_idx = i
        print(f"\nStep {i+1}: Looking for minimum from index {i}")
        
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                print(f"  New minimum found: {arr[min_idx]} at index {min_idx}")
        
        # Swap the found minimum with first element
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            print(f"  Swapped {arr[min_idx]} with {arr[i]}")
        
        print(f"  Array after step {i+1}: {arr}")
    
    return arr

# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = selection_sort_detailed(numbers.copy())

Lesson 2: Basic Implementation

Let's implement Selection Sort step by step:

Simple Selection Sort 
def selection_sort(arr):
    """
    Simple Selection Sort implementation
    Time Complexity: O(n²)
    Space Complexity: O(1)
    """
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap the found minimum element with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# Test the function
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", test_array)
sorted_array = selection_sort(test_array.copy())
print("Sorted array:", sorted_array)

Lesson 3: Selection Sort Variations

Here are different ways to implement and optimize Selection Sort:

Selection Sort Variations

🔹Descending Order Selection Sort 

def selection_sort_descending(arr):
    """Selection Sort in descending order"""
    n = len(arr)
    for i in range(n):
        # Find maximum element instead of minimum
        max_idx = i
        for j in range(i+1, n):
            if arr[j] > arr[max_idx]:  # Changed < to >
                max_idx = j
        arr[i], arr[max_idx] = arr[max_idx], arr[i]
    return arr

🔹Optimized Selection Sort (Early Termination) 

def optimized_selection_sort(arr):
    """Selection Sort with early termination"""
    n = len(arr)
    for i in range(n-1):  # Only need n-1 passes
        min_idx = i
        swapped = False
        
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            swapped = True
        
        # If no swapping occurred, array is sorted
        if not swapped:
            break
    
    return arr

🔹Selection Sort with Custom Comparison 

def selection_sort_custom(arr, key=None, reverse=False):
    """Selection Sort with custom comparison function"""
    n = len(arr)
    
    for i in range(n):
        selected_idx = i
        
        for j in range(i+1, n):
            # Use custom key function if provided
            val_j = key(arr[j]) if key else arr[j]
            val_selected = key(arr[selected_idx]) if key else arr[selected_idx]
            
            if reverse:
                condition = val_j > val_selected
            else:
                condition = val_j < val_selected
            
            if condition:
                selected_idx = j
        
        arr[i], arr[selected_idx] = arr[selected_idx], arr[i]
    
    return arr

# Examples
numbers = [64, 34, 25, 12, 22, 11, 90]
words = ["banana", "apple", "cherry", "date"]

print("Numbers ascending:", selection_sort_custom(numbers.copy()))
print("Numbers descending:", selection_sort_custom(numbers.copy(), reverse=True))
print("Words by length:", selection_sort_custom(words.copy(), key=len))

Lesson 4: Performance Analysis

Understanding when and why to use Selection Sort:

Performance Comparison 
import time
import random

def measure_performance():
    """Compare Selection Sort performance on different inputs"""
    
    sizes = [100, 500, 1000]
    
    for size in sizes:
        print(f"\n=== Array Size: {size} ===")
        
        # Test on different types of arrays
        test_cases = {
            "Random": [random.randint(1, 1000) for _ in range(size)],
            "Sorted": list(range(size)),
            "Reverse Sorted": list(range(size, 0, -1)),
            "Nearly Sorted": list(range(size))
        }
        
        # Make nearly sorted array
        nearly_sorted = test_cases["Nearly Sorted"]
        for _ in range(size // 10):  # Swap 10% of elements
            i, j = random.randint(0, size-1), random.randint(0, size-1)
            nearly_sorted[i], nearly_sorted[j] = nearly_sorted[j], nearly_sorted[i]
        
        for case_name, arr in test_cases.items():
            start_time = time.time()
            selection_sort(arr.copy())
            end_time = time.time()
            
            print(f"{case_name:15}: {(end_time - start_time)*1000:.2f} ms")

# Run performance test
measure_performance()

Practical Applications

Small Datasets

  • Arrays with < 50 elements
  • Simple sorting needs
  • Educational purposes
  • Memory-constrained systems

When Memory Matters

  • Embedded systems
  • In-place sorting required
  • No extra memory available
  • Simple implementation needed

Learning & Teaching

  • Algorithm education
  • Understanding sorting concepts
  • Comparison with other sorts
  • Code interview practice

Avoid When

  • Large datasets (n > 1000)
  • Performance is critical
  • Stability is required
  • Better algorithms available

Practice Project: Student Grade Sorter

Let's create a program that sorts student grades using Selection Sort:

Student Grade Sorter 
class Student:
    def __init__(self, name, grade):
        self.name = name
        self.grade = grade
    
    def __str__(self):
        return f"{self.name}: {self.grade}%"
    
    def __repr__(self):
        return self.__str__()

def selection_sort_students(students, by_grade=True, ascending=True):
    """Sort students using Selection Sort"""
    n = len(students)
    
    for i in range(n):
        selected_idx = i
        
        for j in range(i+1, n):
            if by_grade:
                # Sort by grade
                val_j = students[j].grade
                val_selected = students[selected_idx].grade
            else:
                # Sort by name
                val_j = students[j].name.lower()
                val_selected = students[selected_idx].name.lower()
            
            if ascending:
                condition = val_j < val_selected
            else:
                condition = val_j > val_selected
            
            if condition:
                selected_idx = j
        
        # Swap students
        students[i], students[selected_idx] = students[selected_idx], students[i]
    
    return students

def main():
    # Create student data
    students = [
        Student("Alice", 85),
        Student("Bob", 92),
        Student("Charlie", 78),
        Student("Diana", 96),
        Student("Eve", 88),
        Student("Frank", 73)
    ]
    
    print("Original student list:")
    for student in students:
        print(f"  {student}")
    
    # Sort by grade (ascending)
    print("\n📈 Sorted by grade (lowest to highest):")
    grade_sorted = selection_sort_students(students.copy(), by_grade=True, ascending=True)
    for student in grade_sorted:
        print(f"  {student}")
    
    # Sort by grade (descending)
    print("\n📉 Sorted by grade (highest to lowest):")
    grade_sorted_desc = selection_sort_students(students.copy(), by_grade=True, ascending=False)
    for student in grade_sorted_desc:
        print(f"  {student}")
    
    # Sort by name
    print("\n🔤 Sorted by name (alphabetical):")
    name_sorted = selection_sort_students(students.copy(), by_grade=False, ascending=True)
    for student in name_sorted:
        print(f"  {student}")
    
    # Find top 3 students
    top_students = selection_sort_students(students.copy(), by_grade=True, ascending=False)[:3]
    print("\n🏆 Top 3 students:")
    for i, student in enumerate(top_students, 1):
        print(f"  {i}. {student}")

# Run the program
main()

🧠 Test Your Knowledge

What is the time complexity of Selection Sort?

Selection Sort is a _____ sorting algorithm.

How many swaps does Selection Sort make in the worst case for n elements?