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



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

Сортировка обменом 
П3.55.  Выполнить сортировку заданного массива методом обмена
Сортировка обменом — метод, при котором все соседние элементы масси-
ва попарно сравниваются друг с другом и меняются местами в том случае, 
если  предшествующий  элемент  больше  последующего.  Этот  процесс  по-
вторяется (– 1) раз. 
Например, требуется провести сортировку массива: 
30, 17, 73, 47, 22, 11, 65, 54. 
Методика  сортировки  отражена  на  рис. П3.4  (представлены  первые  два 
прохода обработки). 
 
Сравниваемые элементы 
Обмен 
Первый проход по массиву: 
 
1) 
30 и 17 
Проводится 
2) 
30 и 73 
Нет 
3) 
73 и 47 
Проводится 
4) 
73 и 22 
Проводится 
5) 
73 и 11 
Проводится 
6) 
73 и 65 
Проводится 
7) 
73 и 54 
Проводится 
Полученный массив: 17, 30, 47, 22, 11, 65, 54, 73 
Второй проход по массиву: 
 
1)  
17 и 30 
Нет 
2)  
30 и 47 
Нет 
3)  
47 и 22 
Проводится 
4)  
47 и 11 
Проводится 
5)  
47 и 65 
Нет 
6)  
65 и 54 
Проводится 
7) 
65 и 73 
Нет 
Полученный массив: 17, 30, 22, 11, 47, 54, 65, 73 
Рис. П3.4 
Если индексы "левых" элементов в паре сравниваемых обозначить 
лев
, то 
фрагмент  программы  на  школьном  алгоритмическом  языке,  реализующий 
описанные действия на одном проходе, выглядит так: 
нц для лев от 1 до n — 1 
  |Если "левый" элемент в паре сравниваемых 


Приложения 
274 
  |больше "правого" 
  если a[лев] > a[лев + 1] 
    то |Проводим их обмен 
     всп := a[лев] 
     a[лев] := a[лев + 1] 
     a[лев + 1] := всп 
  все 
кц 
а вся процедура сортировки оформляется следующим образом: 
|Проходим по массиву n — 1 раз, 
нц для номер_прохода от 1 до n - 1 
  |Сравнивая пары элементов 
  нц для лев от 1 до n — 1 
    если a[лев] > a[лев + 1] 
      то |Проводим обмен 
       всп := a[лев] 
       a[лев] := a[лев + 1] 
       a[лев + 1] := всп 
    все 
  кц 
кц 


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




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

    Басты бет