concept · INFO-CS-ADS-130Selection Sort
Selection Sort repeatedly finds the smallest element in the unsorted portion of an array and places it at the beginning of that portion. It performs relatively few swaps but requires quadratic comparisons.
Explanation
Overview
Selection Sort is an in-place comparison-based sorting algorithm that divides an array into sorted and unsorted sections. During each pass, it selects the smallest remaining element and exchanges it with the first element of the unsorted section.
Purpose
Its purpose is to organize elements using a straightforward minimum-selection process. It is also useful for understanding how sorting algorithms maintain a sorted prefix.
Working principle
The algorithm scans the unsorted portion to identify its minimum element. It then places that element at the current starting position of the unsorted section.
Key concepts
name: Core idea; description: The central focus of selection sort is the capability described here: Selection Sort repeatedly finds the smallest element in the unsorted portion of an array and places it at the beginning of that portion. It performs relatively few swaps but requires quadratic comparisons.; name: Problem context; description: Selection Sort is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using selection sort, check its assumptions, input requirements, expected output, and resource constraints.
Space complexity
O(1) auxiliary space for the standard iterative implementation.
Example
For [29, 10, 14, 37, 13], the first pass finds 10 and places it at index 0. The next pass finds 13 and places it at index 1. The process continues until the array becomes [10, 13, 14, 29, 37].
Pseudocode
SELECTION_SORT(A):
n = length(A)
for i = 0 to n - 2:
minIndex = i
for j = i + 1 to n - 1:
if A[j] < A[minIndex]:
minIndex = j
if minIndex != i:
swap(A[i], A[minIndex])
return A
Example or application
For [29, 10, 14, 37, 13], the first pass finds 10 and places it at index 0. The next pass finds 13 and places it at index 1. The process continues until the array becomes [10, 13, 14, 29, 37].
Definition
Selection Sort is an in-place comparison-based sorting algorithm that divides an array into sorted and unsorted sections. During each pass, it selects the smallest remaining element and exchanges it with the first element of the unsorted section.
Purpose
Its purpose is to organize elements using a straightforward minimum-selection process. It is also useful for understanding how sorting algorithms maintain a sorted prefix.
Working Principle
The algorithm scans the unsorted portion to identify its minimum element. It then places that element at the current starting position of the unsorted section.
Algorithm Steps
Begin with the entire array considered unsorted.
Assume the first unsorted element is the minimum.
Compare the remaining unsorted elements with the current minimum.
Update the minimum position whenever a smaller element is found.
Swap the minimum element with the first unsorted element.
Extend the sorted section by one position.
Repeat until all elements are sorted.
Pseudocode
SELECTION_SORT(A):
n = length(A)
for i = 0 to n - 2:
minIndex = i
for j = i + 1 to n - 1:
if A[j] < A[minIndex]:
minIndex = j
if minIndex != i:
swap(A[i], A[minIndex])
return A
Best Case
O(n²) time because the algorithm still scans the remaining unsorted section during every pass, even if the input is already sorted.
Average Case
O(n²) time because approximately n(n - 1) / 2 comparisons are performed regardless of the initial arrangement.
Worst Case
O(n²) time because the algorithm performs the same general sequence of minimum-selection scans even when the input is in reverse order.
Space Complexity
O(1) auxiliary space for the standard iterative implementation.
Stability
Standard Selection Sort is unstable. A swap between the current position and a distant minimum element can change the relative order of equal-key records.
In Place Property
Selection Sort is in-place because it rearranges elements directly inside the original collection without requiring another full-size array.
Swap Count
The standard implementation performs at most n - 1 swaps, which can be useful when writing to memory is relatively expensive.
Comparison Count
The standard algorithm performs approximately n(n - 1) / 2 comparisons for n elements. This count remains quadratic even when the input is already sorted.
Advantages
Simple to understand and implement.
Uses constant auxiliary space.
Performs relatively few swaps.
Does not require additional storage proportional to the input size.
Useful for teaching selection-based sorting.
Limitations
O(n²) time complexity in all common input arrangements.
Standard implementation is unstable.
Does not adapt effectively to nearly sorted data.
Not suitable for large collections.
Comparison With Bubble Sort
Selection Sort usually performs fewer swaps than Bubble Sort, but both have O(n²) comparison complexity. Bubble Sort moves large elements through adjacent swaps, whereas Selection Sort locates a minimum and places it directly.
Practical Applications
Sorting very small collections.
Teaching minimum selection and sorted-prefix construction.
Situations where the number of writes or swaps should be limited.
Demonstrating in-place sorting.
Common Errors
Resetting the minimum index incorrectly.
Swapping before the complete unsorted section has been examined.
Using the wrong comparison direction for descending order.
Assuming the algorithm is stable because it uses few swaps.
Implementation Considerations
The minimum position should be updated during the inner scan, and the swap should occur only after the entire unsorted section has been examined. A check for minIndex != i avoids unnecessary self-swaps.
Key Takeaway
Selection Sort repeatedly selects the smallest unsorted element and places it in its final position. Its small number of swaps can be useful in specific situations, but its quadratic comparisons limit scalability.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of selection sort is the capability described here: Selection Sort repeatedly finds the smallest element in the unsorted portion of an array and places it at the beginning of that portion. It performs relatively few swaps but requires quadratic comparisons. |
Problem context | Selection Sort is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using selection sort, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of selection sort? | Selection Sort repeatedly finds the smallest element in the unsorted portion of an array and places it at the beginning of that portion. It performs relatively few swaps but requires quadratic comparisons. |
What should be checked before applying selection sort? | For selection sort, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of selection sort be validated? | Trace a representative selection sort case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of selection sort.
Identify the assumptions, inputs, and conditions relevant to selection sort.
Evaluate an application of selection sort for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures