Задача:
{ a0, a1, ..an-1, расположенных в произвольном порядке, для элементов заданно отношение “>”, нет одинаковых элементов}
Сортировка (по возрастанию)
{элементы массива расположены в порядке a0 < a1 < … < an-1 }
Программирование по шагам (incremental approach) – парадигма программирования, при которой элементы по одному добавляются к множеству обработанных элементов
Рекуррентная форма
{ a0, a1, ..an-1}
расположить наименьший элемент на первой позиции
{ a0 < (a1, ..., an-2 , an-1)}
сортировка элементов a1, a2, ..an-1
{ элементы массива расположены в порядке a0 < a1 < … < an-1 }
Расположить наименьший элемент на первой позиции
• Найти наименьший элемент
• Поменять местами первый и наименьший элемент
Найти наименьший элемент
Условия внешнего цикла
Инвариант
{ a0 < a1 < …< at-1 ,… , an-1 , an-1}
Предусловие t=0;
Постусловие t=n-1;
Тело цикла
Расположить наименьший из элементов at, ..., an-1 на позиции at
t++;
