2015-10-22
224
Построим внешний цикл программы сортировки.
На каждом шагу цикла мы будет находить один наименьший элемент и располагать его на нужной позиции. Обозначим t номер шага. После каждого шага мы будем иметь t отсортированных (расположенных на своих местах) элементов. Это можно обозначить так: { a 0 > a 1 > … > at – 1, at … an – 1}. В этой записи используются фигурные скобки. Такими скобками обычно отмечают условия выполнения (инвариант, предусловие, постусловие) в тексте программы.
Предусловие этого цикла: t = 0. При этом нет ни одного отсортированного элемента.
Если отсортированы все элементы кроме одного, то последний элемент автоматически располагается на последней позиции. Тогда условие окончания этого цикла таково: t = n – 1, при этом все элементы будут отсортированы, иначе цикл будет продолжаться, пока не будет достигнуто, что t < n – 1.
В теле цикла необходимо увеличить t на единицу, при этом должен сохраниться инвариант – элементы от 0 до t’ – 1 должны находиться на нужных местах. Поскольку до этого на нужных местах были расположены элементы от 0 до t – 1 = t’ – 2, то достаточно найти наименьший элемент среди элементов от t’ – 1 до n – 1 и поменять его местами с элементом t’ – 1 или найти наименьший элемент от t до n – 1 и поменять его с элементом t. Использование старого значения t удобнее, поскольку не требует дополнительных вычитаний 1 и позволяет вычислить новое значение t в конце тела (записать вычисление t в шаг цикла оператора for). Построим цикл, который находит наименьший среди элементов от t до n – 1.
|
|
|
На каждом шаге этого цикла будет добавляться по одному элементу к множеству элементов, для которых известен минимальный из них. Другими словами, инвариантом системы будет условие о том, что известен наименьший элемент среди элементов от t до j – 1, где j – переменная цикла. Обозначим mi индекс этого наименьшего элемента, а m – его значение.
На первом этапе работы цикла множество будет состоять из одного элемента, который, поскольку он один, будет наименьшим элементом этого множества, т. е. j = t + 1, mi = t, m = at. Это предусловие цикла, его выполнения необходимо достичь при инициализации.
Очевидно, что условием выполнения внутреннего цикла будет j < n.
В теле цикла j должно увеличиться на единицу. Для того чтобы сохранился инвариант, достаточно проверить, меньше ли элемент 
переменной m, и если меньше, то изменить m и m – i.
Осталось уточнить, как поменять элементы в конце внешнего цикла. С этим предлагается разобраться самостоятельно по приведенному ниже коду.
void print_mas(int* m, int n)
{
int i;
for(i=0;i<n;i++)
printf("%i ", m[i]);
printf("\n");
}
int main()
{
int a[8]={1,2,4,3,8,7,5,6};
int j, t, m, mi, n=8;
print_mas(a, n);
for(t=0; t<n-1; t++)
{
// Найти наименьший элемент
m=a[t];
mi=t;
for(j=t; j<n; j++)
if(a[j]<m) { m=a[j]; mi=j; };
// Поместить наименьший элемент на первую позицию
a[mi]=a[t]; a[t]=m;
}
print_mas(a, 8);
}
