Algorithms

Running Minimum

A running minimum keeps the smallest value seen so far while scanning an array.

current best The current best starts with the first value.
update rule When the loop sees a smaller value, it replaces the current best.

Running Minimum

last
running_min.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int main(void) {
    int last = 1;
    int values[4] = {6, 3, 8, last};
    int minimum = values[0];

    for (int i = 1; i < 4; i++) {
        if (values[i] < minimum) {
            minimum = values[i];
        }
    }

    printf("min=%d\n", minimum);
    return 0;
}

#include <stdio.h>

int main(void) {
    int last = 0;
    int values[4] = {6, 3, 8, last};
    int minimum = values[0];

    for (int i = 1; i < 4; i++) {
        if (values[i] < minimum) {
            minimum = values[i];
        }
    }

    printf("min=%d\n", minimum);
    return 0;
}

#include <stdio.h>

int main(void) {
    int last = 5;
    int values[4] = {6, 3, 8, last};
    int minimum = values[0];

    for (int i = 1; i < 4; i++) {
        if (values[i] < minimum) {
            minimum = values[i];
        }
    }

    printf("min=%d\n", minimum);
    return 0;
}

  1. last ← 1, values ← ⟨addr A⟩, minimum ← 6

    3int main(void) {4    int last→ 1 = 1; //@last=0, 55    int values→ ⟨addr A⟩[4] = {6, 3, 8, last1};6    int minimum→ 6 = values[0]6;

  2. for (int i = 1; i < 4; i++)

    pass 1 of 3
    8for (int i1 = 1; i < 4; i++) {9    if (values[i] < minimum) {
    All 3 passes — pass 1 is the card above
    passivalues[i]minimum
    1136 → 3
    22——
    3313 → 1

  3. minimum ← 3

    pass 1 of 2
    8for (int i = 1; i < 4; i++) {9    if (values[i]3 < minimum6) {10        minimum→ 3 = values[i]3;11    }

  4. minimum ← 1

    pass 2 of 2
    8for (int i = 1; i < 4; i++) {9    if (values[i]1 < minimum3) {10        minimum→ 1 = values[i]1;11    }

  5. printf("min=%d ", minimum);

    14    printf("min=%d\n", minimum1);15    return 0;16}
    outputmin=1

  1. last ← 0, values ← ⟨addr A⟩, minimum ← 6

    3int main(void) {4    int last→ 0 = 0;5    int values→ ⟨addr A⟩[4] = {6, 3, 8, last0};6    int minimum→ 6 = values[0]6;

  2. for (int i = 1; i < 4; i++)

    pass 1 of 3
    8for (int i1 = 1; i < 4; i++) {9    if (values[i] < minimum) {
    All 3 passes — pass 1 is the card above
    passivalues[i]minimum
    1136 → 3
    22——
    3303 → 0

  3. minimum ← 3

    pass 1 of 2
    8for (int i = 1; i < 4; i++) {9    if (values[i]3 < minimum6) {10        minimum→ 3 = values[i]3;11    }

  4. minimum ← 0

    pass 2 of 2
    8for (int i = 1; i < 4; i++) {9    if (values[i]0 < minimum3) {10        minimum→ 0 = values[i]0;11    }

  5. printf("min=%d ", minimum);

    14    printf("min=%d\n", minimum0);15    return 0;16}
    outputmin=0

  1. last ← 5, values ← ⟨addr A⟩, minimum ← 6

    3int main(void) {4    int last→ 5 = 5;5    int values→ ⟨addr A⟩[4] = {6, 3, 8, last5};6    int minimum→ 6 = values[0]6;

  2. for (int i = 1; i < 4; i++)

    pass 1 of 3
    8for (int i1 = 1; i < 4; i++) {9    if (values[i] < minimum) {
    All 3 passes — pass 1 is the card above
    passivalues[i]minimum
    1136 → 3
    22——
    33——

  3. minimum ← 3

    8for (int i = 1; i < 4; i++) {9    if (values[i]3 < minimum6) {10        minimum→ 3 = values[i]3;11    }

  4. printf("min=%d ", minimum);

    14    printf("min=%d\n", minimum3);15    return 0;16}
    outputmin=3