Сортировка массива

Вопросы:

·     Сортировка массива.

·     Сортировка методом выбора.

·     Сортировка методом пузырька.

Есть множество ситуаций, когда нужно переставить элементы массива определённым образом, например по возрастанию или по убыванию, такое изменение порядка следования называется сортировкой. Примером сортировки может расположение по весу гирь для весов или расположение в алфавитном порядке книг на полках.

Сортировка больших объёмов информации не самая лёгкая задача. Но в отсортированном массиве поиск вести легко. А потому для её решения существует множество различных алгоритмов. Сейчас мы рассмотрим два простых метода сортировки: сортировку методом выбора и сортировку методом пузырька.

Поставим задачу: написать программу, которая генерирует последовательность целых случайных чисел из n элементов от 0 до 50, а затем сортирует её по неубыванию.

Сортировка по неубыванию означает, что в массиве могут быть и равные элементы.

Последовательность чисел будет храниться в массиве a. Обозначим длину последовательности через n, индексы рассматриваемых элементов - через i и j, а также нам необходима ещё одна промежуточная переменная p.

Рассмотрим сначала алгоритм сортировки методом выбора и составим его блок-схему. Вначале, нам необходимо считать n, а затем сгенерировать n случайных чисел в массиве a. Далее мы запишем цикл for i:=1 to n-1 do, внутри которого будет ещё один цикл for j:=i+1 to n do. Внутри этого цикла будет условный оператор, который будет проверять условие a[j] < a[i], и если это условие будет выполняться, данные элементы мы будем менять местами через переменную p. После выполнения данных действий элементы массива будут отсортированы по неубыванию. И нам будет достаточно вывести их на экран.

Блок-схема алгоритма сортировки методом выбора

Рассмотрим подробно, как работает данный алгоритм. На первом витке внешнего цикла мы сравниваем все элементы массива с первым, и если текущий элемент меньше первого – мы меняем их местами через промежуточную переменную p. Таким образом, по завершении первого витка внешнего цикла на первом месте массива будет его минимальный элемент. На втором витке мы так же, как и на первом, находим минимальный элемент из оставшихся, и помещаем его на вторую позицию, на третьем витке мы находим минимальный элемент из оставшихся, и помещаем его на третью позицию. То есть на каждом витке цикла мы выбираем минимальный элемент из определённого количества и помещаем его на нужную позицию массива, отсюда и название данного метода сортировки – метод выбора.

Запишем данный алгоритм в виде программы. Назовём её «Сорт». В разделе описания переменных будут записаны массив из ста элементов типа integer, а также переменные n, i, j и p. Запишем тело программы. Считаем длину последовательности чисел и запишем цикл for i:=1 to n do, в котором будем генерировать случайные числа для последовательности и сразу же, через пробел, выводить их на экран. Так как элементы мы выводили через пробел, то после цикла должна быть команда перехода на следующую строку, то есть команда writeln без параметров. Теперь приступим непосредственно к сортировке массива. Запишем цикл for i:=1 to n-1 do, а внутри него ещё один цикл for j:=i+1 to n do. Внутри двух этих циклов будет условный оператор, который будет проверять a[j] < a[i], и в случае, если условие будет выполнятся, запишем последовательность команд для того, чтобы поменять местами i-тый и j-тый элементы массива через переменную p. Запишем цикл для вывода элементов массива на экран в одну строку, через пробел.

Исходный код программы

Запустим программу на выполнение, и введём длину последовательности, равную семи. Теперь мы получили начальную последовательность, а строкой ниже –эту же последовательность уже отсортированной. Все элементы отсортированной последовательности расположены по неубыванию, значит задача решена верно.

Результат работы программы

Обратим внимание: чтобы превратить сортировку по неубыванию в сортировку по невозрастанию, достаточно внутри цикла, в условном операторе изменить знак меньше, на больше.

Изменённый цикл сортировки

Снова запустим программу на выполнение. Введём длину последовательности, равную пяти, и получим последовательность случайных чисел, а затем эту же последовательность, отсортированную уже поне возрастанию.

Результат работы программы

Теперь отсортируем этот же массив по невозрастанию, используя сортировку методом пузырька. Но для начала разберёмся, как работает данный метод. Будем просматривать массив, и искать в нём элементы, которые находятся рядом, но при этом расположены не по невозрастанию, найдя такие элементы, будем менять их местами. Таким образом, массив мы будем просматривать необходимое количество раз, пока, просматривая его, мы не совершим ни одной перестановки элементов, следовательно, все элементы массива будут расположены по невозрастанию.

Изменим, уже имеющуюся у нас программу. Для сортировки пузырьком нам понадобится ещё одна логическая переменная m типа boolean, переменные данного типа принимают одно значение из двух, истина или ложь, true или false, она будет отвечать на вопрос: «Все ли элементы массива расположены по невозрастанию?». А переменная j нам больше не нужна. Изменим тело программы. В начале программы будут одинаковыми, отличаться они начнут только в момент сортировки массива. Удалим из программы участок кода, отвечающий за сортировку массива, и запишем на его месте последовательность команд для сортировки массива методом пузырька. Вначале нам нужно установить начальное значение m, так, как массив ещё не отсортирован, зададим его равным false. Теперь запишем цикл while m<>true do, прежде чем начать проверку массива, будем полагать что перестановка элементов не потребуется, то есть элементы массива уже расположены по невозрастанию. То есть m:=true. Далее запишем цикл for i:=1 to n-1 do, внутри которого будет условный оператор, условием которого будет что a[i] < a[i+1]. Теперь запишем последовательность команд в случае, если условие выполняется, в этом случае нам нужно поменять местами элементы массива с индексами i и i+1. А так как мы нашли элементы, которые были расположены не по невозрастанию.

Участок программы, сортирующий массив методом пузырька

Запустим программу на выполнение и зададим длину последовательности чисел, равную 5. Мы получим последовательности до сортировки и после. Обратим внимание, что в нижней строке элементы действительно отсортированы по невозрастанию.

Результат работы программы

Как и в случае с сортировкой методом выбора, чтобы изменить сортировку по невозрастанию на сортировку по неубыванию, в программе достаточно изменить знак «меньше» в условном операторе на «больше».

Изменённый код сортировки

Снова запустим программу на выполнение. Зададим длину последовательности цифр, равную шести и получим последовательность до сортировки и после, после сортировки элементы действительно расположены по неубыванию.

Результат работы программы

Важно запомнить:

·      Изменение порядка следования элементов в массиве в соответствии с определённым признаком называется сортировкой.

·      При сортировке методом выбора на каждом шаге выбирается максимальный или минимальный элемент и устанавливается на нужную позицию.

·      При сортировке методом пузырька, рассматриваются стоящие на соседних позициях элементы массива, и при необходимости они меняются местами.

Мы научились применять данные алгоритмы при решении задач.