Skip to main content

Selection sort with trace

Short answer

Selection sort finds the smallest element in the unsorted part and swaps it to the front. Sorting 40, 90, 20, -10, 30, 5, 60, 100, 80: after each pass, the array becomes -10, 5, 20, 30, 40, 60, 80, 90, 100. The final sorted sequence is -10, 5, 20, 30, 40, 60, 80, 90, 100.

Explain selection sort. Sort data sequence 40 90 20 -10 30 5 60 100 80 using selection sort method.

Selection sort repeatedly selects the smallest element from the unsorted part and exchanges it with the first element of that part. After pass i, the first i positions hold the i smallest elements in their final places.

Algorithm

SelectionSort(a[0..n-1])
for i = 0 to n-2
    min = i
    for j = i+1 to n-1
        if a[j] < a[min]: min = j
    swap a[i], a[min]

void selection_sort(int a[], int n) {
    int i, j, min, t;
    for (i = 0; i < n - 1; i++) {
        min = i;                              /* index of smallest so far */
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min]) min = j;
        t = a[i]; a[i] = a[min]; a[min] = t;  /* exchange */
    }
}

Trace for 40 90 20 −10 30 5 60 100 80 (n = 9, 8 passes)

PassSmallest foundSwapArray after pass
0––40 90 20 −10 30 5 60 100 80
1−10a[0] ↔ a[3]−10 90 20 40 30 5 60 100 80
25a[1] ↔ a[5]−10 5 20 40 30 90 60 100 80
320already in place−10 5 20 40 30 90 60 100 80
430a[3] ↔ a[4]−10 5 20 30 40 90 60 100 80
540already in place−10 5 20 30 40 90 60 100 80
660a[5] ↔ a[6]−10 5 20 30 40 60 90 100 80
780a[6] ↔ a[8]−10 5 20 30 40 60 80 100 90
890a[7] ↔ a[8]−10 5 20 30 40 60 80 90 100

Sorted: −10, 5, 20, 30, 40, 60, 80, 90, 100

Complexity

  • Comparisons: (n−1) + (n−2) + ... + 1 = n(n−1)/2 in every case, so time is O(n²) (best, average and worst).
  • At most n − 1 swaps, which is good when writes are costly.
  • In-place (O(1) space) and not stable.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 7 questions →