Конспект лекций по программированию для начинающих. Гладков В.П. - 174 стр.

                                        176

       номера элементов: 1 2 3 4 5 6;
       начало отсортированной части - 1, конец отсортированной части - n;
       неотсортированной части в массиве нет.
   Программа, реализующая описанный алгоритм, приведена ниже:
   for i:=2 to n do {перебираем все элементы неотсортированной части}
   begin      j:=i-1; {номер последнего элемента отсортированной части}
              y:=a[i]; {выбрали первый элемент неотсортированной части}
              f:=false; {пока не нашли для него подходящего места}
              while (j>0) and not f do { пока есть элементы в отсортированной части
и не найдено в ней место для выбранного элемента выполняем }
                      if a[j]>y    then { сдвигаем a[j] на одно место вправо }
                                   begin a[j+1]:=a[j]; j:=j-1 end
                                   else f:=true;
                      a[j+1]:=y {записываем элемент на найденное место в массив}
   end.
   Упражнения:
   1. Измените алгоритм, используя для поиска места в отсортированной части
просмотр от ее начала к концу.
   2. Измените алгоритм, используя для поиска места в отсортированной части
двоичный поиск.
   3. Сравните предложенный алгоритм и алгоритмы, полученные при
выполнении упражнений 1 и 2.
   4. Примените любой из этих алгоритмов для сортировки части массива между
элементами с индексами p и q.
   5. Измените предложенный алгоритм так, чтобы сортировка шла в обратном
порядке.

                           11.7.2. Сортировка выбором
    Вначале находим в массиве элемент с минимальным значением среди
элементов с индексами от 1-го до n-го и меняем найденный элемент с первым.
После этого первый элемент из обработки можно исключить. На втором шаге
находим минимальный элемент среди элементов с индексами от 2-го до n-го и
меняем его местами со вторым элементом. Продолжаем повторять поиск
минимального элемента и его обмен со всем элементами с 3-го до n-1-го.
    Отсортируем с помощью этого метода массив a={ 3, 1, 9, 2, 5, 7}. Вначале
найдем минимальный элемент во всем массиве и поставим его на первое место.
Получим a={ 1, | 3, 9, 2, 5, 7 }. Сейчас первый элемент стоит на своем месте,
поэтому его не трогаем, а отыскиваем минимальный элемент, начиная со второго
до последнего. Ставим найденный элемент на второе место. Получим a={ 1, 2, | 9,
3, 5, 7 }. Сейчас два элемента стоят на своих местах, поэтому следующий шаг
поиска проводим для элементов с третьего до последнего. Получим a = { 1, 2, 3, | 9,
5, 7 }. По окончании четвертого шага получим a={ 1, 2, 3, 5, | 9, 7 }. Наконец, после
пятого шага получим a = { 1, 2, 3, 5, 7, 9 }.
    Таким образом, алгоритм этого метода сортировки сводится к следующему.
Организуем цикл, который позволит изменять границы просматриваемой части