Алгоритмы сортировки Алгоритмы сортировки отличаются друг от друга: - степенью эффективности ( кол-во сравнений); - кол-вом обменов, производимых в процессе сортировки. Оценивать эффективность будем кол-вом операций сравнений( порядком этого значения).

Процесс упорядочивания данных по определенному признаку называется сортировкой Элементы массива можно сортировать: - по возрастанию - каждый следующий элемент больше предыдущего A[1]

Элементы массива можно сортировать: - по убыванию - каждый следующий элемент меньше предыдущего A[1]>A[2]> … >A[n] - по невозрастанию - каждый следующий элемент не больше предыдущего A[1] A[2] … A[n]

Методы сортировки: - выбор min / max; кол-во сравнений c=n*(n-1)/2 - «пузырька»; кол-во сравнений c=n*(n-1)/2 - простые вставки кол-во сравнений c=n-1

Сортировка выбором минимального Этапы работы: 1. Определить минимальный элемент 2. Запомнить индекс минимального 3. Осуществить обмен минимального и текущего элемента 4. пп.1-3 повторить для следующих элементов массива !!! Левая часть массива отсортирована

Сортировка выбором минимального Исх мас. А ( min) индексы этап этап этап этап этап

Задача 1. Задан массив А(6), целые. Отсортировать массив методом выбора минимального Program Sort_min; Uses crt; Const n=6; var A: array [1..n] of integer; J : integer; { рабочий индекс} ind: integer; { индекс мин. элем. в правой части мас.} i : integer; {индекс разделителя отсор. и неотсор. } temp : integer; { временная ячейка для обмена} min: integer; { минимальный элемент массива} begin clrscr; … {заполнение массива, ввод с клавиатуры} … {вывод исходного массива} … {сортировка массива методом выбора минимального}

for i:=1 to n-1 do { текущий индекс } begin min:=A[ i ]; { текущий элемент минимальный } ind:= i; {индекс минимального элемента } { поиск минимального и его индекса на неотсортиров части} for j:=i to n do if A[ j ]

Сортировка методом «пузырька» Исх мас. А индексы этап этап этап этап этап этап !!! Процесс повторить n-1 раз

Задача 2. Задан массив А(6), целые. Отсортировать массив используя метод «пузырька» Program Sort_bubble; Uses crt; Const n=6; var A: array [1..n] of integer; k : integer; { количество проходов} i : integer; {индекс текущего элемента} temp : integer; { временная ячейка для обмена} begin clrscr; … {заполнение массива, ввод с клавиатуры} … {вывод исходного массива} … {сортировка массива методом «пузырька»}

for k:=1 to n-1 do { количество проходов} {сортировка за один проход} for i:=1 to n-k do if A[ i ]> A[ i+1 ] then begin { обмен значений } temp:=A[ i ]; { дубликат текущего элемента } A[ i ]:=a[ i+1 ]; { в текущий элемент заносим следующий} A[ i+1 ]:=temp; { на место следующего текущий} End; { вывод отсортированного массива} end.

1. Задан массив В(10) натуральных элементов, введенных с клавиатуры. Выполнить сортировку элементов в порядке возрастания, используя метод «выбор максимального». 2. Задан массив С(5,5) целых чисел. Упорядочить элементы каждой строки в порядке убывания. Метод выбрать самостоятельно.