Сортировка методом простого выбора (код)
Полезная статья? Пожалуйста, поставьте "+"
Алгоритмизация и программирование - Содержание
Этот метод сортировки обычно применяется для массивов, не содержащих
повторяющихся элементов. Для достижения поставленной цели можно
действовать следующим образом: 1. выбрать максимальный элемент массива; 2. поменять его местами с последним элементом ( после этого наибольший элемент будет стоять на своем месте ); 3.
повторить пп.1-2 с оставшимися n-1 элементами, то есть рассмотреть
часть массива, начиная с первого элемента до предпоследнего, найти в ней
максимальный элемент и поменять его местами с предпоследним (n-1) -
м элементом массива и так далее, пока не останется один элемент, уже
стоящий на своем месте. Всего потребуется n-1 раз выполнить эту
последовательность действий. В процессе сортировки будет увеличиваться
отсортированная часть массива, а не отсортированная, соответственно,
уменьшаться.
Для программной реализации этого процесса необходимо
организовать цикл по длине рассматриваемой части массива, которая
изменяется от n до 2. В качестве начального значения максимума разумно
взять значение последнего элемента рассматриваемой части. Теперь можем записать алгоритм сортировки: For i: = n Downto 2 Do Begin найти максимальный элемент из a[1], ..., a[i]; запомнить его индекс в переменной k; если ik поменять местами a[i] и a[k] End;
Опишем этот алгоритм подробно:
program n1; type ar=array [1..10] of integer; var i:integer; a:ar;
Procedure sorting1(var a:ar); {поскольку в процессе работы процедуры массив изменится, формальный параметр а описывается как параметр-переменная} var i,j,k:integer; m:integer; {значение максимального элемента рассматриваемой части массива} begin for i:=10 downto 2 do {цикл по длине рассматриваемой части массива} begin {поиск максимального элемента и его номера в текущей части массива} k:=i; m:=a[i]; {начальные значения максимального элемента и его индекса в рассматриваемой части массива} for j:=2 to i-1 do if a[j]>m then begin k:=j; m:=a[k] end; if ki then begin {перестановка элементов} a[k]:=a[i]; a[i]:=m; end; end; end; begin writeln('Введите исходный массив:'); for i:=1 to 10 do read(a[i]); sorting1(a); writeln('Отсортированный массив:'); for i:=1 to 10 do write(a[i],' '); writeln; end.
При
решении практических задач упорядочивание x1,...xn как правило
сопровождается некоторыми дополнительными действиями. Например, если
x1, y1, x2, y2, ..., xn, yn - это значения аргумента x и некоторой
функций y=f(x), то перестановка x1, ..., xn должна сопровождаться
перестановкой y1, ..., yn. Элементы y1, ..., yn переставляются так же,
как x1, ..., xn вне зависимости от значений самих y1, ..., yn. Рассмотрим эту задачу; переставленные значения x1, y1, x2, y2, ..., xn будут выведены в два столбца: x1 y1 x2 y2 ..... xn yn program tab; const n=5; type u=array[1..n] of real; var x,y:u; v:real; i,j,k:integer; begin for i:=1 to n do read(x[i],y[i]); for i:=1 to n do begin k:=i; for j:=i+1 to n do if x[j] v:=x[i]; x[i]:=x[k]; x[k]:=v; v:=y[i]; y[i]:=y[k]; y[k]:=v; writeln(x[i],y[i]); end; end.
|
Категория: Алгоритмизация и программирование | Добавил: Ni-Cd (10 Декабря 2011)
|
Просмотров: 1581
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ]
|
|
Онлайн |
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
|
|