Методы сортировки массивов в спортивном программировании для начинающих

Размещено на http://www.allbest.ru/

Тюм ГНГУ

Методы сортировки массивов в спортивном программировании для начинающих

Азанов М.А.

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

Многие задачи в спортивном программировании требуют от программиста знания массивов, умения работать с ними и сортировать их. Информация о том что такое массивы и как с ними начать работать представлена на сайте для изучения языка программирования с++ «массивы с++» [1]

Есть несколько способов сортировки массивов:

-Сортировка обменом (пузырьковый метод)

-Сортировка Шелла

-Сортировка Хоара (быстрая сортировка)

-Сортировка выбором

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

-Пирамидальная сортировка

-Поразрядная сортировка

-Сортировка подсчетом

1. Сортировка выбором.

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

2. Сортировка обменом (прием пузырька)

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

Дополнительная память не нужна.

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

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

Сортировка вставками является простым и достаточно эффективным методом сортировки, в нем элементы данных используются как ключи для сравнения.

Сначала упорядочиваются элементы X [0] и Х [1], вставив X [1] перед X [0], если X [0] больше чем X [1]. Затем элементы данных которые остались по очереди вставляются в упорядоченный набор. После i-й итерации элемент X [I] занимает свое правильное положение и элементы X [0] и X [I] уже отсортированы.

После каждой итерации, только один элемент занимает свое правильное положение.

При сортировке вставками происходит меньше перестановок, чем при пузырьковой сортировке.

4. Шейкер-сортировка.

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

5. Пирамидальная сортировка

Пирамидальная сортировка является первой из всех рассматриваемых методов, их быстродействие оценивается как O (n log n). Строительство пирамиды занимает O (n log n) операций, причем более точную оценку дает даже O (n) за счет того что фактическое время работы зависит от высоты части пирамиды которая уже создалась. Второй этап занимает O (n log n) времени: O (n) раз берётся максимальное значение и осуществляется просеивание бывшего последнего элемента. Преимуществом является стабильность метода: среднее число пересылок (n log n) / 2, и отклонение от этого значения является незначительными.

Метод не является устойчивым: массив по ходу работы «перетряхивается», и исходный порядок элементов может изменяться случайным образом

6. Сортировка Хоара (быстрая сортировка)

Данную сортировку изобрели больше сорока лет назад, её используют чаще чем любую другую сортировку, потому что она является практически самой эффективной. На каждое разделение приходится O (n) операций. Сумма шагов деления составляет примерно log n, если массив может делится на более или менее равные части. Общее быстродействие: О (n log n), что происходит на практике. Охват стека, при данной реализации постоянно имеет порядок O (log n), так что указанного значения в MAXSTACK предостаточно.

7. Поразрядная сортировка.

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

Этот метод имеет ввиду следующее: элементы начинают сортироваться по последнему разряду, потом по предпоследнему и так до тех пор, пока не дойдет до первого разряда. На каждой итерации алгоритм включает в себя два этапа: распределение и сборку. Скорость алгоритмов, определяет число проходов по всем элементам исходного списка, равна максимальному количеству разрядов в элементе. Если мы сортируем числа, то число разрядов - будет равно числу десятичных разрядов этого числа, например: 27 - Число разрядов 2, 487 - колво разрядов 3, цифра 9 - 1 разряд, и т.д. В случае сортировки текстовых строк - число разрядов определяется количеством букв в строке. сортировка массив программист

8. Сортировка подсчетом.

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

Информация о реализации всех методов сортировки, представлена на форуме для начинающих программистов «С++ для начинающих» [3].

В заключение хочется сказать, что какой метод использовать решает каждый сам, потому что для каждого случая не всегда подходит один и тот же метод сортировки. Но прежде чем приступать к изучению методов сортировки массивов любой программист должен знать, что такое массив, как он задается, а так же как с ними работать. Подробный и понятный материал для изучения массивов находится в книге Г. Шилдта, в главе 4 и 13 «Полный справочник по с++» [2].

Размещено на Allbest.ru