Справочник от Автор24
Найди эксперта для помощи в учебе
Найти эксперта
+2

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

Определение 1

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

Введение

Замечание 1

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

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

Сортировка целых чисел

Это наиболее простая версия алгоритма. Имеется начальный числовой набор, длиной nn, а итоги сортировки буду сохранены в массиве АА. Создадим для удобства работы некий служебный массив СС, который обладает индексацией от нуля до k−1k−1 и в исходном состоянии заполнен нулевыми значениями. Очерёдность действий в алгоритме, следующая:

  1. Выполняется проход по массиву АА и запись в C[i]C[i] количества чисел, которые равны ii.
  2. Выполняется проход по массиву СС, где для всех number∈{0,...,k−1}number∈{0,...,k−1} в массив АА поочерёдно пишется число C[number]C[number] раз.

Ниже приведена программная реализация алгоритма на уровне псевдокодов:

Псевдокод. Автор24 — интернет-биржа студенческих работ

Рисунок 1. Псевдокод. Автор24 — интернет-биржа студенческих работ

«Сортировка подсчётом» 👇
Помощь эксперта по теме работы
Найти эксперта
Решение задач от ИИ за 2 минуты
Решить задачу
Помощь с рефератом от нейросети
Написать ИИ

Выполнение сортировки сложных объектов

Часто возникает проблема сортировки сложных информационных объектов, под которыми понимается структурное построение, которое содержит несколько полей. Одно из этих полей необходимо выделить и обозначить как ключ. Сортировка производится по этому ключу, диапазон целочисленных значений ключа простирается от нуля до k−1k−1. Но в данном случае, нельзя применять алгоритм сортировки подсчётом целых чисел, так как в общем списке возможно наличие разных структур, но с одинаковыми ключами. Есть два метода обойти эту проблему, а именно, применять списки, хранящие структуры в прошедшем сортировку массиве, или определить заранее число структур, которые имеют одинаковые ключи. Причём сделать это надо для каждого значения ключа. Итак, начальный набор из nn структур сохраняется в массиве АА, а прошедшие сортировку структуры записываются в массив ВВ, который имеет такой же объём. И в добавок, применяется служебный массив РР, имеющий индексацию от нуля до k−1k−1.

Основная концепция алгоритма заключается в предварительном определении числа элементов с разными ключами в начальном массиве и подразделении итогового массива на участки необходимого размера (блоки). Далее при следующем обходе начального массива копия каждого его компонента записывается в специальный блок с ключами этого размера, в первую не занятую ячейку. Делать эту процедуру помогает массив индексов РР, хранящий индексы начала блоков для всех размеров ключей. P[key]P[key] обозначает индексацию итогового массива, которая соответствует начальному компоненту блока для ключа keykey. Очерёдность операций в алгоритме, следующая:

  1. Выполняется проход по начальному массиву АА и запись в P[i]P[i] числа структур с ключом, равным ii.
  2. Массив ВВ условно подразделяется на kk блоков, с длиной каждого из них, равной P[0]P[0], P[1]P[1], ..., P[k]P[k].
  3. Поскольку массив РР больше не потребуется, он преобразуется в массив P[i]P[i], который будет сохранять сумму компонентов от нуля до i−1i−1 бывшего массива PP.
  4. Выполняется сдвиг массива РР на один компонент вперёд. В новом массиве P[0]=0P[0]=0, а для i>0i>0 P[i]=Pold[i−1]P[i]=Pold[i−1]. Здесь PoldPold является прежним массивом PP. Такое действие возможно выполнить в течение одного прохода по массиву РР, и даже единовременно с выполнением предыдущего шага. По завершению этой операции, в массиве РР окажутся сохранёнными индексы массива ВВ. P[key]P[key] будет указывать на начальный элемент блока ВВ, который соответствует ключу keykey.
  5. Выполняется собственно сортировка. Осуществляется ещё один проход по начальному массиву АА и для всех i∈[0,n−1]i∈[0,n−1] и пересылается структура A[i]A[i] в массив BB на место P[A[i].key]P[A[i].key]. Далее выполняется увеличение P[A[i].key]P[A[i].key] на одиннадцать. Здесь A[i].keyA[i].key является ключом структуры, которая расположена в массиве АА на ii-том месте.

После окончания действия алгоритма в массиве ВВ окажется записанным начальный набор структур, но прошедший сортировку. Блоки располагаются в порядке увеличения значений ключей. Необходимо ещё отметить, что такая сортировка будет устойчивой, поскольку два компонента, имеющие одинаковые ключи, добавляются в такой же очерёдности, в какой выполнялся их просмотр в начальном массиве ВВ. Это свойство определяет существование цифровой сортировки. Ниже приведена программная реализация алгоритма со следующими обозначениями. АА и ВВ являются массивами структур с размером nn и индексацией от нуля до n−1n−1. PP является массивом целых чисел, имеющим размер kk и индексацию от нуля и до k−1k−1, где kk – это число разных ключей.

Программа. Автор24 — интернет-биржа студенческих работ

Рисунок 2. Программа. Автор24 — интернет-биржа студенческих работ

В программе третий и четвёртый пункты алгоритма выполняются в едином цикле и в последнем цикле выполнено копирование всей структуры вместе с ключом.

Анализ сложности

В первом алгоритме (сортировка целых чисел) начальная пара циклов выполняется за Θ(k)Θ(k) и Θ(n)Θ(n). Алгоритм обладает линейной временной трудоёмкостью Θ(n+k)Θ(n+k). Применяемая добавочная память равняется Θ(k)Θ(k). Второй алгоритм имеет в своём составе два обхода массива АА с размером nn и один обход массива РР с размером kk. То есть он обладает трудоёмкостью, равной Θ(n+k)Θ(n+k). При практической реализации, сортировку подсчётом целесообразно использовать, если k=O(n)k=O(n), то есть возможно учитывать время выполнения алгоритма по формуле Θ(n)Θ(n). Аналогично простой сортировке подсчётом, необходимо иметь Θ(n+k)Θ(n+k) добавочной памяти.

Дата написания статьи: 26.12.2019
Получи помощь с рефератом от ИИ-шки
ИИ ответит за 2 минуты
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot