Сортировка одномерных массивов способы сортировки
Сортировка заключается в перестановке элементов массива в порядке возрастания или убывания их значений. Методы сортировки основаны на сравнении элементов массива в проверяемой части и перестановке наибольшего, либо наименьшего элемента в начало, либо в конец этой части массива. Процесс перестановок повторяется до полного упорядочения значений элементов массива. Известно несколько методов сортировки, обладающих различной эффективностью при решении конкретных задач. Пусть заданы значения элементов массива «X». Приведем алгоритмы и блоки операторов, выполняющие некоторые наиболее распространенные методы сортировки.
Сортировка выбором основана на определении наибольшего (наименьшего) элемента, который переносится в начало или конец массива в зависимости от вида сортировки ( по возрастанию или по убыванию). Затем эта процедура применяется ко всем оставшимся элементам, кроме уже перемещенных элементов, всего ( N — 1 ) раз. Приведем пример операторов для сортировки элементов массива “Х” по возрастанию:
for j: = 1 to N-1 do begin
k:= N-j+1;
m:= k;
for i:= 1 to N-j do
if x[i] > x[m] then m: = i;
b:= x[k]; x[k]:= x[m]; x[m]:= b
end;
Здесь полагается, что последний элемент, расположенный в сортируемой части массива, имеет наибольшее значение. Это условие проверяется для оставшейся части массива и запоминается номер (индекс) элемента с действительно наибольшим значением. Затем производится перестановка наибольшего элемента с последним элементом в проверяемой части массива. Далее процесс повторяется с уменьшением числа рассматриваемых элементов на единицу.
Сортировка обменом (метод пузырька) основана на последовательном сравнении пары соседних элементов x[i] и x[i+1]. Если пара расположена не в требуемом порядке, то элементы переставляются. Например, при сортировке по возрастанию после первого «прохода» массива от первого до последнего элемента на последнем месте окажется наибольший элемент массива. Далее сортируется оставшаяся часть массива. С каждым очередным «проходом» наибольший элемент массива в оставшейся части массива будет занимать последнее место в проверяемой части массива. Наибольшее число проходов j равно «N — 1», причем число проверок при очередном проходе уменьшается на единицу:
for j:= 1 to N-1 do
for i:= 1 to N-j do
if x[i] > x[i+1] then begin
b:=x[i]; x[i]:=x[i+1]; x[i+1]:=b end;
Поскольку при сортировке сравниваются каждые два соседних элемента массива, то для упорядочения данных общее число «проходов» может быть меньше, чем «N — 1». Избежать лишних проходов можно используя оператор цикла с условием:
j:= 0;
repeat j:= j+1; pr:= 0;
for i:= 1 to N-j do
if x[i] > x[i+1] then begin pr:= 1;
b:=x[i]; x[i]:=x[i+1]; x[i+1]:=b end;
until pr = 0;
Если при проходе проверяемой части массива не было перестановок, то pr=0 и процесс заканчивается. Оптимальным с математической точки зрения считается алгоритм с наименьшим числом перестановок. Однако при программировании необходимо учитывать также, что время выполнения логических операций, как правило, значительно превышает время выполнения арифметических операций. Таким образом, время выполнения программы определяется не только числом перестановок, но существенно зависит от количества выполнений логических операций.
Сортировка вставками основана на внедрении в отсортированную часть массива элемента следующего за этой частью, если он удовлетворяет условию сортировки. На первом шаге сортировки второй элемент сравнивается с первым, на втором шаге третий элемент сравнивается с двумя первыми и т. д. Среди уже отсортированных i — 1 элементов массива вставляют i — й элемент без нарушения порядка, т. е. при вставке i — го элемента на j — е место (j j и x[j] do j:= j+1;
for k:=i downto j+1 do x[k]:=x[k-1];
x[j]:= b
end;
В отличие от рассмотренных методов сортировки здесь процесс сравнения элементов заканчивается как только вставляемый элемент удовлетворяет условию сортировки, т. к. элемент вставляется в отсортированную часть массива.
Практическое задание N 2. 33
1. Определить массив из 100 целых случайных чисел в диапазоне от 10 до 1000. Отсортировать массив по убыванию значений элементов методом обмена с использованием оператора цикла с параметром и оператора цикла с условием.
2. Определить массив из 50 вещественных чисел: x[i] = Cos( i/10), i= 1, 2, . . . 50. Отсортировать массив по убыванию значений элементов методом выбора и вставки.
3. Определить массив из 70 вещественных чисел: x[i]= i * Sin( i/20), i= 1, 2, . . . 70. Отсортировать массив по возрастанию значений элементов методом вставки и обмена с использованием оператора цикла с условием.
Примечание:
составить процедуры сортировки. Подсчитать число перестановок элементов массива и число логических операций в каждом случае. Вывести на экран исходный и отсортированный массивы в виде таблиц чисел с точностью 5 знаков после запятой.
Рассмотрим задачу сортировки таблицы по некоторому ключу (колонке с упорядоченными данными). Например, исходная таблица содержит колонки: фамилия, имя, отчество, средний балл учащихся. Требуется провести сортировку таблицы по ключу (колонке) — «средний балл». При перестановке данных в одной колонке необходимо соответственно переставлять данные в других колонках, т. е. сохранять взаимное расположение данных в каждой строке таблицы. Для этого можно в программу сортировки включить операторы перестановки элементов всех массивов (колонок) параллельно с перестановкой элементов ключевого массива. Однако при этом программы сортировки теряют универсальность. Другой способ сортировки таблицы состоит в определении соответствия между новой и старой нумерацией элементов в ключе (сортируемом массиве «X»). Введем массив «Ne», элементы которого хранят значения индексов в исходном массиве числовых данных. Очевидно, что до сортировки массива «X» Ne[i]:=i; При перестановке элементов массива «X» параллельно необходимо переставлять элементы массива «Ne», например, при сортировке выбором: Nm:= Ne[k]; Ne[k]:= Ne[m]; Ne[m]:= Nm; Новое значения элемента Ne[m] показывает в какой строчке исходной таблицы находился элемент, имеющий в новой таблице индекс «m». Рассмотрим пример.
Таким образом, после сортировки по ключу «x» вывод другого массива «F» (колонки) таблицы нужно проводить в цикле: for i := 1 to N do Writeln( F [ Ne [ i ] ] ); После сортировки таблицы вместо массива «F» можно использовать новый массив, например «Fc», элементы которого равны: Fc[i]:=F[Ne[i]]; i=1, 2, . N.
Сортировка может производиться для символьных и строковых данных. Символы сравниваются по номеру ASCII кода, а при сортировке строковых данных сравниваются первые символы строк, затем вторые и т. д. Символы, отсортированные по возрастанию ASCII кода, располагаются в алфавитном порядке. Программы сортировки остаются в прежнем виде, но операторы работают с элементами символьного или строкового типа.
Источник
Основные виды сортировок и примеры их реализации
Памятка для тех, кто готовится к собеседованию на позицию разработчика
На собеседованиях будущим стажёрам-разработчикам дают задания на знание структур данных и алгоритмов — в том числе сортировок. Академия Яндекса и соавтор специализации «Искусство разработки на современном C++» Илья Шишков составили список для подготовки с методами сортировки, примерами их реализации и гифками, чтобы лучше понять, как они работают.
Пузырьковая сортировка и её улучшения
Сортировка пузырьком
Сортировка пузырьком — один из самых известных алгоритмов сортировки. Здесь нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.
Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.
Сортировка перемешиванием (шейкерная сортировка)
Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.
Сортировка расчёской
Сортировка расчёской — улучшение сортировки пузырьком. Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.
Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1,247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1,247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.
Простые сортировки
Сортировка вставками
При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.
Сортировка выбором
Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.
Быстрая сортировка
Этот алгоритм состоит из трёх шагов. Сначала из массива нужно выбрать один элемент — его обычно называют опорным. Затем другие элементы в массиве перераспределяют так, чтобы элементы меньше опорного оказались до него, а большие или равные — после. А дальше рекурсивно применяют первые два шага к подмассивам справа и слева от опорного значения.
Быструю сортировку изобрели в 1960 году для машинного перевода: тогда словари хранились на магнитных лентах, а сортировка слов обрабатываемого текста позволяла получить переводы за один прогон ленты, без перемотки назад.
Сортировка слиянием
Сортировка слиянием пригодится для таких структур данных, в которых доступ к элементам осуществляется последовательно (например, для потоков). Здесь массив разбивается на две примерно равные части и каждая из них сортируется по отдельности. Затем два отсортированных подмассива сливаются в один.
Пирамидальная сортировка
При этой сортировке сначала строится пирамида из элементов исходного массива. Пирамида (или двоичная куча) — это способ представления элементов, при котором от каждого узла может отходить не больше двух ответвлений. А значение в родительском узле должно быть больше значений в его двух дочерних узлах.
Пирамидальная сортировка похожа на сортировку выбором, где мы сначала ищем максимальный элемент, а затем помещаем его в конец. Дальше нужно рекурсивно повторять ту же операцию для оставшихся элементов.
Источник
Урок 28. Сортировка массива
Урок из серии: «Программирование на языке Паскаль»
Процесс обработки и поиска информации при решении многих задач проходит быстрее и эффективнее, если данные расположены в определенном порядке. Например, различные списки студентов, учащихся, сотрудников — в алфавитном порядке, числовые данные от большего значения к меньшему (или наоборот) и т.д.
Существует довольно много различных методов сортировки массивов, отличающихся друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки. Рассмотрим подробно некоторые из них.
Сортировка массива методом простого выбора
При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера.
Алгоритм сортировки массива методом выбора:
- Для исходного массива выбрать максимальный элемент.
- Поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своем месте).
- Повторить п.п. 1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в нем максимальный элемент и поменять его местамис предпоследним (n-1)- м элементом массива, затем с оставшиеся (n-2)-мя элементами и так далее, пока не останется один элемент, уже стоящий на своем месте.
Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.
При сортировке данных выполняется обмен содержимого переменных. Для обмена необходимо создавать временную переменную, в которой будет храниться содержимое одной из переменных. В противном случае ее содержимое окажется утерянным.
Задача 1. Массив из 10 элементов отсортировать по возрастанию методом простого перебора.
Напишем процедуру. Входным параметром для неё будет массив. Он же будет и выходным параметром. Поэтому описываем его как параметр-переменная (с ключевым словом var).
В процедуре внешний цикл по i — определяет длину рассматриваемой части массива. Она будет изменяться от n до 2.
Внутренний цикл по j используется для поиска максимального элемента и его номера. В качестве начального значения максимума разумно взять значение последнего элемента рассматриваемой части массива.
Программный код процедуры:
Программный код основной программы:
Процесс упорядочения элементов в массиве по возрастанию методом отбора:
| Номер элемента | 1 | 2 | 3 | 4 | 5 |
| Исходный массив | 8 | 7 | 5 | 4 | 2 |
| Первый просмотр | 2 | 7 | 5 | 4 | 8 |
| Второй просмотр | 2 | 4 | 5 | 7 | 8 |
| Третий просмотр | 2 | 4 | 5 | 7 | 8 |
| Четвертый просмотр | 2 | 4 | 5 | 7 | 8 |
При упорядочивании массива по убыванию необходимо перемещать минимальный элемент. Для чего в алгоритме нахождения максимального элемента достаточно знак «>» поменять на знак « » заменить на « Total 0
Источник
