Answer: Invariants

Question: Write invariants at the indicated space in the following functions.

void
selectionSort(int *arr, int n) {
    for(int i = 0; i < n; i++) {
        // INVARIANT: ???
        int min_pos = i;
        for(int j = i + 1; j < n; j++) {
            if(arr[j] < arr[min_pos]) min_pos = j;
        }
        int temp = arr[min_pos];
        arr[min_pos] = arr[i];
        arr[i] = temp;
    }
}

Answer: The least i elements of the initial array are in sorted order in the first i elements of the current array.