Массивы и их сортировка

1. Массивы и их сортировка

2. Массив

Массив это структура данных,
представленная в виде группы ячеек
одного типа, объединенных под одним
единым именем.

3. Формальное определение массива выглядит следующим образом:

Одномерный массив — массив, с одним
параметром, характеризующим количество
элементов одномерного массива.

4. Многомерный массив

Кроме одномерных массивов в C++ есть многомерные. Элементы таких массивов
сами в свою очередь являются массивами, в которых также элементы могут быть
массивами. Например, определим двухмерный массив чисел:
Такой массив состоит из трех элементов, при этом каждый элемент представляет
массив из двух элементов. Инициализируем подобный массив:

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

Поразрядная сортировка
Поразрядная сортировка (англ. radix sort) — алгоритм
сортировки, который выполняется за линейное время.
Массив несколько раз перебирается и элементы
перегруппировываются в зависимости от того, какая цифра
находится в определённом разряде. После обработки
разрядов (всех или почти всех) массив оказывается
упорядоченным. При этом разряды могут обрабатываться в
противоположных направлениях - от младших к старшим или
наоборот.

6. Поразрядная сортировка по младшим разрядам

Элементы перебираются по порядку и группируются по самому
младшему разряду (сначала все, заканчивающиеся на 0, затем
заканчивающиеся на 1, ..., заканчивающиеся на 9). Возникает новая
последовательность. Затем группируются по следующему разряду с
конца, затем по следующему и т.д. пока не будут перебраны все
разряды, от младших к старшим.
Точное название способа LSD radix sort (Least significant digit radix
sorts) - поразрядная сортировка по наименьшей значащей цифре.

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

Элементы перегруппироввываются по определённому разряду
(сначала по самому старшему). Затем разбиваются на подгруппы в
зависимости от значения этого разряда: равного 0, равного 1,
равного 2, ..., равного 9. Каждая подгруппа обрабатывается
отдельно, в ней к следующему разряду рекурсивно применяется
radix sort.
Точное название способа MSD radix sort (Most significant digit radix
sorts) - поразрядная сортировка по наибольшей значащей цифре.

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

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

9. Источники

10. Спасибо за внимание!

English Русский Правила