Selection Sort
Selection sort
Why introduce selection sort when bubble sort already exists? Bubble sort can exchange items far too often.
Imagine a PE teacher arranging children from shortest to tallest. Repeatedly exchanging adjacent children is a cumbersome way to form the line.
Computers do not become frustrated, but frequent array exchanges mean additional memory reads and writes that affect efficiency.
A simple alternative finds the shortest child each time and exchanges that child with the first remaining position.
For example, sort this eight-item sequence in ascending order:
Selection sort: scan, then exchange the minimum
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Algorithm analysis
Finding a minimum and placing it on the left takes per pass. There are n−1 passes, giving overall.
The algorithm works in place without another data structure, so extra space is .
| Time | Extra space | Stability | Design idea |
|---|---|---|---|
| Unstable | Decrease and conquer |
Selection sort
#include <stdio.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Selection Sort (original v1.0)
*/
T *selection_sort(T *arr, int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Selection-sort optimization
Ordinary selection sort finds the minimum remaining item and exchanges it with the first remaining position, then repeats. An optimization finds both the minimum and maximum in one scan and places them at the two ends.
Optimized selection sort
Optimized selection: select both minimum and maximum
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
#include <stdio.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Selection Sort (original v1.0)
*/
T *selection_sort(T *arr, int n) {
for (int i = 0; i < n / 2; i++) {
int minIndex = i;
int maxIndex = n - i - 1;
for (int j = i; j < n - i; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
swap(arr[i], arr[minIndex]);
// In case of i == maxIndex before swap(arr[i], arr[minIndex]), it's now at minIndex.
if (i == maxIndex) {
maxIndex = minIndex;
}
swap(arr[n - i - 1], arr[maxIndex]);
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Distinguish updating min from swapping
Run ordinary selection sort on [7,2,5,1]. Record min-index changes and the array after each completed scan. Count comparisons and exchanges excluding self-swaps.