Д. М. Златопольский Санкт-Петербург «бхв-петербург» 2011 удк

Приложения 
278 
Указанные  недостатки  устраняются,  если  все  изменения  проводить  в  ис-
ходном массиве. Отсортировать его можно следующим образом: 
1.  Найти минимальный элемент среди всех элементов массива и поменять 
его местами с первым элементом. 
2.  Найти  минимальный  элемент  среди  второго,  третьего, ...,  последнего 
элементов массива и поменять его местами со вторым элементом. 
... 
На  последнем  этапе  находится  минимальный  элемент  среди  двух  по-
следних,  найденный  элемент  меняется  местами  с  предпоследним  эле-
ментом исходного массива. Поскольку после каждого просмотра упоря-
доченные элементы исключаются из дальней обработки, размер каждого 
последующего  обрабатываемого  участка  массива  на 1  меньше  размера 
предыдущего. 
Общая схема программы, основанной на сделанных рассуждениях, такая: 
нц для i от 1 до n — 1 
  1. Ищем минимальный элемент мин и его индекс индмин 
     среди элементов с индексами i, i + 1, i + 2, ..., n 
  2. Меняем местами минимальный и i-й элементы 
кц 
Итак,  мы  пришли  к  задаче  нахождения  минимального  элемента  и  его  ин-
декса среди элементов с индексами i, i + 1, i + 2, ..., n. Эта задача решается 
аналогично такой задаче применительно ко всему массиву 
|Начальные значения 
мин := a[i] 
индмин := i 
|Рассматриваем остальные элементы 
нц для j от i + 1 до n 
  если a[j] < a[индмин] 
    то 
     мин := a[j] 
     индмин := j 
  все 
кц 
С учетом сказанного фрагмент, реализующий сортировку, имеет вид: 
нц для i от 1 до n - 1 
  |Этап 1 
  мин := a[i] 
  индмин := i 
  нц для j от i + 1 до n 

Приложение 3. Работа с одномерными числовыми массивами 
279 
    если a[j] < a[индмин] 
      то 
       мин := a[j] 
       индмин := j 
    все 
  кц 
  |Этап 2 
  |Меняем местами минимальный и i-й элементы 
  a[индмин] := a[j] 
  a[j] := мин 
кц 

жүктеу/скачать 7,99 Mb.

Достарыңызбен бөлісу: