Сортировка одномерного массива

Сортировка одномерного массива — перераспределение значений элементов неупорядоченного одномерного массива в некотором заданном порядке для ускорения поиска элементов в нём.

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

Основные положения

Одномерный массив — это структура данных, содержащая фиксированное количество элементов одного и того же типа, объединённых одним именем, где каждый элемент имеет свой номер. Обращение к элементам такого массива в программировании осуществляется путём указания имени массива и номеров его элементов.

Правила упорядочивания элементов одномерного массива могут быть различными. В результате применения правила упорядочивания элементы массива перераспределяются в новый порядок. Для большинства задач выделяют три типа порядка:

Возрастающий порядок: Первый элемент массива имеет самое маленькое значение, а значения всех последующих элементов больше значения предыдущего элемента. Пример: $M_{inc}={0,1,2,4,7,9,15,29}$.

Неубывающий (невозрастающий) порядок: Элементы массива могут иметь равные значения, в этом случае говорят о порядке неубывания (невозрастания) элементов массива. Пример: $M_{ninc}={0,1,1,4,7,9,9,29}$.

Убывающий порядок: Первый элемент массива имеет самое большое значение, а значения всех последующих элементов меньше значения предыдущего элемента. Пример: $M_{dec}={29,15,9,7,5,4,2,0}$.

Существуют разные методы сортировки (сортировка выбором, сортировка обменом, сортировка данными, и др.). В каждый метод сортировки заложен алгоритм сортировки.

Алгоритм сортировки элементов массива — последовательность действий по упорядочиванию элементов массива. В более сложных массивах, где элемент массива имеет несколько полей (многомерный массив), поле, принимаемое за критерий порядка, называют ключом сортировки.

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

Примеры

Алгоритм сортировки по убыванию, как правило, состоит из следующих шагов:

Шаг 1. В одномерном массиве выбирается максимальный элемент методом сравнения всех составляющих массив элементов;

Шаг 2. Максимальный и первый элементы массива меняются местами (значение максимального элемента помещается в первый элемент массива, значение первого элемента — на место максимального);

Шаг 3. В неупорядоченной части массива (без максимального элемента, который считается уже отсортированным) методом сравнения выбирается максимальный элемент, значение которого записывается в первый элемент, а значение первого элемента — в элемент, в котором был расположен найденный максимальный;

Шаг 4. Процедуры, описанные в шаге 1 и 2 повторяются до тех пор, пока не останется один элемент, значение которого принимается за минимальное. Его значение будет последним элементом сортированного по убыванию одномерного массива.

Алгоритм сортировки по возрастанию аналогичен алгоритму по убыванию, только при сравнении элементов выделяются не максимальный, а минимальный элемент. Данные алгоритмы лежат в основе методов сортировки выбором.

Сортировка обменом осуществляется путём последовательного сравнения пар соседних элементов $x_{i}$ и $x_{i+1}$. В случае сортировки по возрастанию (убыванию) элементы пары сравнивают, и, в соответствии с условием сортировки либо меняют местами, либо оставляют в той же последовательности, в которой они стояли до сравнения. В результате прохождения всего массива на последнем месте окажется больший (меньший) элемент массива. Далее прохождение массива повторяется только в оставшейся части, без максимального (минимального) элемента. Осуществив $N-1$ проходов (это максимальное число проходов массива), где $N$ — число элементов массива, получим упорядоченный по возрастанию (убыванию) одномерный массив. Иногда этот метод сортировки одномерного массива называют методом пузырька.

При сортировке вставками происходят не перестановки элементов или пар, а внедрение в отсортированную часть массива следующего за ней элемента, если он удовлетворяет условиям сортировки. На первом шаге второй элемент массива сравнивается с первым, на втором — третий со вторым и первым, и так далее, до конца массива. Образуются $i-1$ отсортированных элементов, в которые вставляется i-элемент без нарушения порядка в отсортированных элементах, а элементы с индексами, большими j (где j — индекс элемента, который переставили в отсортированные элементы), но меньшими i, увеличивают свой номер на единицу. В этом алгоритме процесс сравнения элементов заканчивается тогда, когда вставляемый элемент удовлетворяет условию сортировки, поскольку он сразу вставляется в сортированную часть одномерного массива.

Существуют и гибридные алгоритмы сортировок, например, алгоритм Timsort, в котором сочетаются сортировка вставками и сортировка слиянием. Изобретён Тимом Петерсом в 2002 году, и с тех пор стал стандартным алгоритмом сортировки в языке программирования Python. Идея этого алгоритма состоит в том, что, как правило, в практических задачах сортируемые массивы данных часто уже содержат в себе упорядоченные подмассивы. Используя это свойство, алгоритм Timsort работает существенно быстрее многих известных ранее алгоритмов сортировки.

Литература

• Кнут Д. Э. Искусство программирования. Т. 3. Сортировка и поиск. — М. : ООО «И. Д. Вильямс», 2018.
• Липачёв Е. К. Технология программирования. Методы сортировки данных: учебное пособие. — Казань : Казанский ун-т, 2017.
• Монган Дж., Гижере Э., Киндлер Н. Работа мечты для программиста. Тестовые задачи и вопросы при собеседовании в ведущих IT-компаниях. — СПб. : Питер, 2014.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М. : ООО «И. Д. Вильямс», 2013.
• Динман М. И. C++. Освой на примерах. — СПб. : БХВ-Петербург, 2006.
• Weiss M. A. Data Structures and Problem Solving Using C++. — Pearson Education International Inc., 2014.
• Седжвик Р. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск. — Киев : «ДиаСофт», 2001.

Ссылки

• Исчерпывающее руководство по одномерным массивам

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Сортировка одномерного массива», расположенная по адресу: — «https://ru.ruwiki.ru/wiki/Сортировка_одномерного_массива» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».