Сортировка пузырьком

Инвариант

{ a₀ < a₁ < …< a_t-1 ,… , a_n-1 , a_n-1}

Предусловие t=0;

Постусловие t=n-1;

Тело цикла

для всех i, если a_i>a_i+1 поменять элементы местами;

передвинуть t на позицию, в которой произошел последний обмен;

Пример программы:

#include "stdio.h"

void sort(char* str, int n)

{

int t=0, p, f;

char m;

while(t<n-1)

{

f=n-1;

for(p=n-1; p>t; p--)

if(str[p]<str[p-1])

{

m=str[p];

str[p]=str[p-1];

str[p-1]=m;

f=p;

}

#ifdef DEBUG_SORT

printf("massive - %s, f=%i\n", str, f);

#endif

t=f;

}

}

int check_sort(char* str, int n)

{

int i, f=1;

for(i=0; i<n-1; i++)

if(str[i]>str[i+1]) f=0;

return f;

}

int main()

{

char a[4][9] = {"87654321",

"12345678",

"21436587",

"16273845"};

int i;

for(i=0; i<4; i++)

{

printf("test %i\n", i);

printf("massive - %s\n", a[i]);

sort(a[i], 8);

printf("sort - %s\n", a[i]);

if(check_sort(a[i], 8)) printf("test passed\n\n");

else printf("test failed\n\n");

}

}