rag/knowledge_base/selection_sort.txt

TOPIC: Selection Sort

DEFINITION: 
Selection sort is a simple comparison-based sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and swapping it with the first unsorted element. This process continues until the entire list is sorted, solving the problem of arranging elements in ascending or descending order.

TIME_COMPLEXITY: 
The time complexity of selection sort is O(n^2) in all cases (best, average, and worst), because it involves two nested loops that iterate over the list, resulting in quadratic time complexity.

SPACE_COMPLEXITY: 
The space complexity of selection sort is O(1), as it only uses a constant amount of additional space to store temporary variables, regardless of the size of the input list.

USE_WHEN: 
Selection sort is suitable when the list is small or when memory writes are expensive, as it minimizes the number of swaps. It's also a good choice for educational purposes, as its simplicity makes it easy to understand and implement.

AVOID_WHEN: 
Selection sort is not suitable for large lists, as its quadratic time complexity makes it inefficient compared to other sorting algorithms like quicksort or mergesort, which have average-case time complexities of O(n log n).

EXAMPLE: 
Suppose we have the list [5, 2, 8, 3, 1]. The selection sort algorithm works as follows:
  Initial list: [5, 2, 8, 3, 1]
  Find minimum (1) and swap with first element: [1, 2, 8, 3, 5]
  Find minimum in remaining list (2) and swap with first unsorted element: [1, 2, 8, 3, 5]
  Find minimum in remaining list (3) and swap with first unsorted element: [1, 2, 3, 8, 5]
  Find minimum in remaining list (5) and swap with first unsorted element: [1, 2, 3, 5, 8]
  Find minimum in remaining list (8) and swap with first unsorted element: [1, 2, 3, 5, 8] 
  Result: [1, 2, 3, 5, 8] 

REAL_WORLD_ANALOGY: 
Selection sort is similar to how you might organize a set of books on a shelf, where you repeatedly find the book that belongs in the next spot and move it there, until the entire shelf is organized.

SOURCE_NOTE: