✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-130

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.

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

NameDescription

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

QuestionAnswer

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