![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Простые методы сортировки массивов: перестановкой, обменом, вставками
Сортировка - это процесс упорядочивания информации по определенному признаку. Цель сортировки - облегчение последующего поиска элементов. Это почти универсальный вид обработки информации, с которым мы встречаемся в жизни повсеместно. Пример. Разработать программу сортировки элементов массива А(n), где n < 20, используя метод выбора, метод вставки и метод обменов. Метод выбора. Сортировка посредством выбора представляет собой один из самых простых методов сортировки. Он предполагает такую последовательность действий. Сначала находим минимальный элемент массива. Найденный элемент меняем местами с первым элементом. Затем повторяем процесс с п-1 элементами, начиная со второго, потом с п-2 элементами, начиная с третьего и т.д. до тех пор, пока не останется один, самый большой элемент массива. Приведем текст программы, реализующий данный алгоритм. Program sortl; Var a: array [1..20] of real; j, i, n, imin: integer; min: real; Begin WritelnCВведите количество чисел п< =20: '); Readln(n); Writeln('Введите массив: '); for i: =l to n do Read(a[i]); Readln; for j: =l to n-1 do {цикл поиска минимальных элементов массива} begin min: =a[j]; {начальное значение для поиска минимума} imin: =j; {начальное значение индекса минимального элемента} for i: =j+l to n do {цикл поиска минимума и его индекса} if a[i]< min then {если элемент меньше уже найденного минимального} begin min: =a[i]; {запоминаем элемент} imin: =i {запоминаем его индекс} end; {меняем местами найденный минимум и первый элемент текущего массива} a[imm]: =a[j]; a[j]: =min; end; for i: =l to n do Write(a[i]: 6: 2); Writeln; End.
Метод вставки. Сортировку вставками можно описать следующим образом. В исходном состоянии считают, что сортируемая последовательность состоит из двух последовательностей: уже сортированной (она на первом шаге состоит из единственного - первого элемента) и последовательности элементов, которые еще необходимо сортировать. На каждом шаге из сортируемой последовательности извлекается элемент и вставляется в первую последовательность так, чтобы она оставалась сортированной. Поиск места вставки осуществляют с конца, сравнивая вставляемый элемент ai с очередным элементом сортированной последовательности аj. Если элемент ai больше аj, его вставляют вместо aj+1, иначе сдвигают аj вправо и уменьшают j на единицу. Поиск места вставки завершают, если элемент вставлен или достигнут левый конец массива. В последнем случае элемент ai вставляют на первое место. Разрабатывая алгоритм, избавимся от проверки достижения начала массива. Прием, позволяющий отменить эту проверку, называется «проверка с барьером». С использованием этого приема проверка организуется так, чтобы из цикла поиска места вставки в любом случае происходил выход по первому условию. Для этого достаточно поместить вставляемый элемент перед первым элементом массива, как элемент с индексом 0. Этот элемент и станет естественным барьером для ограничения выхода за левую границу массива. Приведем текст программы, реализующей данный алгоритм. Program sort2; Vara: array[0..20] of real; B: real; i, j, n: integer; Begin WriteLn('Введите количество чисел п< =20.'); ReadLn(n); WriteLn('Введите массив.'); for i: =l to n do Read(a[i]); ReadLn; for i: -2 to n do {начиная со второго элемента до конца массива} begin B: =a[i]; {запоминаем i-й элемент} а[0]: =В; {этот же элемент записываем в а[0] - это барьер} j: =i-l; {индекс i запоминаем в j} while B< a[j] do {пока очередной рассматриваемый элемент больше 1-го элемента} begin a[j+1]: =a[j]; {сдвигаем элемент} j: =j-l; {уменьшаем j на 1} end; a[j+1]: =B; {как только найдено место, туда записывается В} end; WriteLh('Отсортированный массив: '); for i: =l to n do Write(a[i]: 6: 2); WriteLn; End.
Метод обменов. Алгоритм прямого обмена основывается на сравнении пары соседних элементов. Если расположение элементов не удовлетворяет условиям сортировки, то их меняют местами. Сравнения и перестановки продолжают до тех пор, пока не будут упорядочены все элементы. Определить, что элементы упорядочены, можно, считая количество выполненных перестановок: если количество перестановок равно нулю, то массив отсортирован. Приведем программу, реализующая данный алгоритм. Program ex; Var a: array [1..20] of Real; i, j, n, l, k: integer; b: real; Begin WriteLn(" Введите размер массива N< =20 '); ReadLn(n); for i: = 1 ton do Read(a[i]); ReadLn; WriteLn('Исходный массив: '); for i: = 1 to n do Write(a[i]: 7: 2); WriteLn; k: =l; {количество перестановок, начальное значение не равно 0 } i: =l; {номер очередного просмотра, в начале равен 1 } while k< > 0 do {пока есть перестановки} begin k: =0; {обнуляем количество перестановок} for j: =l to n-l do {цикл сравнения соседних элементов} if a[j]> a[j+l] then {если предыдущий элемент больше последующего, то} begin {осуществляем перестановку} b: =a[j]; a[j]: =a[j+1]; a[j+1]: =b; k: =k+l; {счетчик перестановок увеличиваем на 1} end; i: =i+l; {увеличиваем номер просмотра на 1 } end; WriteLn(' Отсортированный массив '); for i: = 1 to n do Write (a[ij: 7: 2); WriteLn; WriteLn(' Количество проходов ', i: 3); End
|