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

Содержание

Слайд 2

Массив

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

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

Слайд 3

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

Одномерный массив — массив, с одним параметром,

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

Слайд 4

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

Кроме одномерных массивов в C++ есть многомерные. Элементы таких массивов сами

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

Такой массив состоит из трех элементов, при этом каждый элемент представляет массив из двух элементов. Инициализируем подобный массив:

Слайд 5

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

Поразрядная сортировка (англ. radix sort) — алгоритм сортировки, который выполняется за линейное время.

Массив несколько раз

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

Слайд 9

Источники

|http://algolab.valemak.com
|https://metanit.com
|https://code-live.ru
|http://cppstudio.com
|https://ru.wikipedia.org

Энс А.|Зеленов С.|П-210

Источники |http://algolab.valemak.com |https://metanit.com |https://code-live.ru |http://cppstudio.com |https://ru.wikipedia.org Энс А.|Зеленов С.|П-210