Niezmienniki w sortowaniu bąbelkowym/przez wstawianie

Cześć!
Jakie są niezmienniki tych dwóch kodów i jak je udowodnić?

Sortowanie bąbelkowe:

void Sortowanie( int tab[], int size )
{
for( int i = 0; i < size; i++ )
{
for( int j = 0; j < size - 1; j++ )
{
if( tab[ j ] > tab[ j + 1 ] )
swap( tab[ j ], tab[ j + 1 ] );

    }
}

}

Sortowanie przez wstawianie:

void Sortowanie( int tab[], int size )
{
int k;
for( int i = 0; i < size; i++ )
{
k = i;
for( int j = i + 1; j < size; j++ )
if( tab[ j ] < tab[ k ] )
k = j;

    swap( tab[ k ], tab[ i ] );
}

}

Z góry dziękuję za pomoc i pozdrawiam!

Sortowanie bąbelkowe:

W i-tej iteracji podciąg tab[0:i] jest posortowany rosnąco (nie ściśle) i każdy element podciągu tab[i+1:size] jest większy lub równy od każdego elementu podciągu tab[0:i].

Oczywiście istnieje wiele niezmienników, wg definicji nawet zdanie "size" jest niezmiennikiem. Lecz masz na myśli zapewne taki niezmiennik, który pozwala dowodzić poprawności algorytmu. Musisz wtedy pokazać, że nizmiennik pozostaje prawdziwy podczas inicjalizacji, w trakcie przebiegu oraz po zakończeniu pętli.

Sortowanie przez wstawianie:

Bardzo podobnie :)