Selection Sort

Selection sort repeatedly moves the smallest remaining value into the next output position.
minimum index The inner loop tracks the position of the smallest remaining value.
swap After the scan, a swap places that value into the current sorted position.
                            first
                            first = 3 (default)first = 1first = 9
                        

                            selection_sort.c
                        
Replay: real traced execution (multi-file project)

                            #include <stdio.h>

int main(void) {
    int first = 3;
    int values[4] = {first, 1, 4, 2};

    for (int i = 0; i < 3; i++) {
        int minIndex = i;
        for (int j = i + 1; j < 4; j++) {
            if (values[j] < values[minIndex]) {
                minIndex = j;
            }
        }
        int temp = values[i];
        values[i] = values[minIndex];
        values[minIndex] = temp;
    }

    printf("first=%d last=%d\n", values[0], values[3]);
    return 0;
}
#include <stdio.h>

int main(void) {
    int first = 1;
    int values[4] = {first, 1, 4, 2};

    for (int i = 0; i < 3; i++) {
        int minIndex = i;
        for (int j = i + 1; j < 4; j++) {
            if (values[j] < values[minIndex]) {
                minIndex = j;
            }
        }
        int temp = values[i];
        values[i] = values[minIndex];
        values[minIndex] = temp;
    }

    printf("first=%d last=%d\n", values[0], values[3]);
    return 0;
}
#include <stdio.h>

int main(void) {
    int first = 9;
    int values[4] = {first, 1, 4, 2};

    for (int i = 0; i < 3; i++) {
        int minIndex = i;
        for (int j = i + 1; j < 4; j++) {
            if (values[j] < values[minIndex]) {
                minIndex = j;
            }
        }
        int temp = values[i];
        values[i] = values[minIndex];
        values[minIndex] = temp;
    }

    printf("first=%d last=%d\n", values[0], values[3]);
    return 0;
}

                        
1first ← 3, values ← ⟨addr A⟩⋯3int main(void) {4    int first→ 3 = 3; //@first=9, 15    int values→ ⟨addr A⟩[4] = {first3, 1, 4, 2};⋯
2minIndex ← 0pass 1 of 3⋯7for (int i0 = 0; i < 3; i++) {8    int minIndex→ 0 = i0;9    for (int j = i + 1; j < 4; j++) {⋯All 3 passes — pass 1 is the card abovepassiminIndex
100
211
322
3for (int j = i + 1; j < 4; j++)pass 1 of 6⋯8int minIndex = i;9for (int j1 = i0 + 1; j < 4; j++) {10    if (values[j] < values[minIndex]) {⋯All 6 passes — pass 1 is the card abovepassji
110
220
330
421
531
632
4minIndex ← 1pass 1 of 3⋯9for (int j = i + 1; j < 4; j++) {10    if (values[j]1 < values[minIndex]3) {11        minIndex→ 1 = j1;12    }⋯All 3 passes — pass 1 is the card abovepassvalues[j]values[minIndex]jminIndex
11310 → 1
22331 → 3
33432 → 3
5temp ← 3, values[i] ← 1, values[minIndex] ← 3⋯13    }14    int temp→ 3 = values[i]3;15    values[i]→ 1 = values[minIndex]1;16    values[minIndex]→ 3 = temp3;17}⋯
6temp ← 3, values[i] ← 2, values[minIndex] ← 3⋯13    }14    int temp→ 3 = values[i]3;15    values[i]→ 2 = values[minIndex]2;16    values[minIndex]→ 3 = temp3;17}⋯
7temp ← 4, values[i] ← 3, values[minIndex] ← 4⋯13    }14    int temp→ 4 = values[i]4;15    values[i]→ 3 = values[minIndex]3;16    values[minIndex]→ 4 = temp4;17}⋯
8printf("first=%d last=%d ", values[0], values[3]);⋯19    printf("first=%d last=%d\n", values[0]1, values[3]4);20    return 0;21}⋯outputfirst=1 last=4
1first ← 1, values ← ⟨addr A⟩⋯3int main(void) {4    int first→ 1 = 1;5    int values→ ⟨addr A⟩[4] = {first1, 1, 4, 2};⋯
2minIndex ← 0pass 1 of 3⋯7for (int i0 = 0; i < 3; i++) {8    int minIndex→ 0 = i0;9    for (int j = i + 1; j < 4; j++) {⋯All 3 passes — pass 1 is the card abovepassivalues[j]values[minIndex]jminIndex
10———0
21———1
322432
3for (int j = i + 1; j < 4; j++)pass 1 of 6⋯8int minIndex = i;9for (int j1 = i0 + 1; j < 4; j++) {10    if (values[j] < values[minIndex]) {⋯All 6 passes — pass 1 is the card abovepassjivalues[j]values[minIndex]minIndex
110———
220———
330———
421———
531———
632242 → 3
4temp ← 1⋯13    }14    int temp→ 1 = values[i]1;15    values[i]1 = values[minIndex]1;16    values[minIndex]1 = temp1;17}⋯
5temp ← 1⋯13    }14    int temp→ 1 = values[i]1;15    values[i]1 = values[minIndex]1;16    values[minIndex]1 = temp1;17}⋯
6minIndex ← 3⋯9for (int j = i + 1; j < 4; j++) {10    if (values[j]2 < values[minIndex]4) {11        minIndex→ 3 = j3;12    }⋯
7temp ← 4, values[i] ← 2, values[minIndex] ← 4⋯13    }14    int temp→ 4 = values[i]4;15    values[i]→ 2 = values[minIndex]2;16    values[minIndex]→ 4 = temp4;17}⋯
8printf("first=%d last=%d ", values[0], values[3]);⋯19    printf("first=%d last=%d\n", values[0]1, values[3]4);20    return 0;21}⋯outputfirst=1 last=4
1first ← 9, values ← ⟨addr A⟩⋯3int main(void) {4    int first→ 9 = 9;5    int values→ ⟨addr A⟩[4] = {first9, 1, 4, 2};⋯
2minIndex ← 0pass 1 of 3⋯7for (int i0 = 0; i < 3; i++) {8    int minIndex→ 0 = i0;9    for (int j = i + 1; j < 4; j++) {⋯All 3 passes — pass 1 is the card abovepassiminIndex
100
211
322
3for (int j = i + 1; j < 4; j++)pass 1 of 6⋯8int minIndex = i;9for (int j1 = i0 + 1; j < 4; j++) {10    if (values[j] < values[minIndex]) {⋯All 6 passes — pass 1 is the card abovepassji
110
220
330
421
531
632
4minIndex ← 1pass 1 of 3⋯9for (int j = i + 1; j < 4; j++) {10    if (values[j]1 < values[minIndex]9) {11        minIndex→ 1 = j1;12    }⋯All 3 passes — pass 1 is the card abovepassvalues[j]values[minIndex]jminIndex
11910 → 1
24921 → 2
32432 → 3
5temp ← 9, values[i] ← 1, values[minIndex] ← 9⋯13    }14    int temp→ 9 = values[i]9;15    values[i]→ 1 = values[minIndex]1;16    values[minIndex]→ 9 = temp9;17}⋯
6temp ← 9, values[i] ← 2, values[minIndex] ← 9⋯13    }14    int temp→ 9 = values[i]9;15    values[i]→ 2 = values[minIndex]2;16    values[minIndex]→ 9 = temp9;17}⋯
7temp ← 4⋯13    }14    int temp→ 4 = values[i]4;15    values[i]4 = values[minIndex]4;16    values[minIndex]4 = temp4;17}⋯
8printf("first=%d last=%d ", values[0], values[3]);⋯19    printf("first=%d last=%d\n", values[0]1, values[3]9);20    return 0;21}⋯outputfirst=1 last=9
pass	`j`	`i`	`values[j]`	`values[minIndex]`	`minIndex`
1	1	0	—	—	—
2	2	0	—	—	—
3	3	0	—	—	—
4	2	1	—	—	—
5	3	1	—	—	—
6	3	2	2	4	2 → 3