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



Pdf көрінісі
бет269/271
Дата04.02.2022
өлшемі7,99 Mb.
#24830
1   ...   263   264   265   266   267   268   269   270   271
Байланысты:
Златопольский Сборник задач по прогр

Примечание  
Величину 
мин
 
можно  не  использовать —  значение  минимального  элемента  массива 
можно  получить,  зная  величину 
индмин
 
(см. разд. "Типовые  задачи  обработки 
одномерных числовых массивов" ранее в этом приложении)
Рассмотренный  вариант  сортировки  массива  методом  выбора  обладает 
двумя недостатками: 
 
для его реализации требуется дополнительный массив; 
 
при нахождении минимального элемента и его индекса на каждом про-
ходе приходится рассматривать все элементы массива. 


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


Достарыңызбен бөлісу:
1   ...   263   264   265   266   267   268   269   270   271




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет