Сортировка подсчетом и применение встроенных сортировок

ГОАОУ
«Центр поддержки одаренных детей
«Стратегия»
Липецкой области, к.т.н., доц. Шуйкова И.А., студент ИТМО, призер ВсОШ по информатике 2018 Первеев М.В. ветственно. Процедура продолжается до тех пор, пока выполняется условие i <= j. В конце работы процедуры переупорядочивания элементов указатели i и j поменяются местами. i j p
0 1
2 3
4 5
6 0
6 p=a[3]=2 7

i
8 1
4 3
6

j
0 5
2 7

i
8 1
4 3

j
6 0
4 2
7

i
8 1
4

j
3 6
0 3
2 7

i
8 1

j
4 3
6 1
2 2
8

i
1

j
7 4
3 6
2 1
2 1

j
8

i
7 4
3 6
Левая часть массива a[l, i - 1] состоит из элементов не больших, чем опорный (на рисунке выделена серым цветом). Правая часть массива a[j + 1, r] состоит из элементов не меньших, чем опорный.
Далее вызывается рекурсивно процедура QuickSort для левой и правой частей массива. Рекурсивный вызов осуществляется при условии, что l < j (для левой части) и r > i (для правой части).
Рекурсивный вызов Quicksort(l=0,j=1) от левой части массива
0 1
2

i
1

j
8 7
4 3
6 0
1 2
1

j

i
8 7
4 3
6
Рекурсивный вызов Quicksort(l=2,j=6) от правой части массива
2 6
4 1
2 8

7 3
6

2 5
4 1
2 8

i
7 3

j
6 3
4 4
1 2
3 7

i

j
8 6
4 3
4 1
2 3

j
7

i
8 6
Рекурсивный вызов Quicksort(l=4,j=6)
4 6
8 1
2 3
4 7

i
6

j
5 6
8 1
2 3
4 7

i
6

j
6 5
8 1
2 3
4 7
6

j

i
Рекурсивный вызов Quicksort(l=4,j=5)
4 5
7 1
2 3
4

i
6

j
8 5
4 7
1 2
3 4
6

j

i
8
Приведем программную реализацию функции быстрой сортировки. void quick_sort(int l, int r)
{ int i = l, j = r, p = a[(l + r) / 2], temp; while (i <= j)
{ while (a[i] < p) i++; while (a[j] > p) j--; if(i <= j)
{ temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--;
}
} if (l < j) quick_sort(l, j);
// Левая часть if (i < r) quick_sort(i, r);
// Правая часть
}
2 2
2 2
2 2
2 2
2 2
2 4
4 4
4 8
=
8
=
8 8
=
8
=
8 8
=
8
=
8 7
=
8
=
8 7
=
8
=
8

ГОАОУ
«Центр поддержки одаренных детей
«Стратегия»
Липецкой области, к.т.н., доц. Шуйкова И.А., студент ИТМО, призер ВсОШ по информатике 2018 Первеев М.В.
Оценка сложности быстрой сортировки
Алгоритм быстрой сортировки в среднем использует 𝑂(𝑁𝑙𝑜𝑔 𝑁) сравнений и 𝑂(𝑁𝑙𝑜𝑔 𝑁) присваиваний, 𝑂(𝑙𝑜𝑔 𝑁) дополнительной памяти для хранения стека рекурсивных вызовов.
Быстрая сортировка неэффективна на некоторых простых массивах данных, например, если она применяется для сортировки уже отсортированных массивов. В худшем случае алгоритм имеет сложность 𝑂(𝑁
2
). Кроме того, рекурсивные вызовы являются затратными операциями, и для небольших массивов данных быстрая сортировка будет работать не очень эффективно. Поэтому в случае небольших объемов данных (< K, где K – некоторое небольшое число, например, 32), быстрая сортировка также работает не очень хорошо. В случае небольшого количества данных используют нерекурсивные методы сортировки, например, сортировку вставками или выбором, что дает прирост производительности алгоритма сортировки.
Рассмотрим худший случай работы алгоритма быстрой сортировки на примере упорядоченного массива данных, в котором N элементов. При первом разбиении массива процедурой partition производится N сравнений. Рекурсивный вызов от левой части массива размером (N - 1) / 2 и в дальнейшем от правой части массива размером (N - 1) / 2 приводит в общей сложности к N сравнениям.
Рассуждая далее, получим общее количество сравнений для упорядоченного файла, равное N + (N - 1) +
(N - 2) + … + 2 + 1 = (N + 1) * N / 2, то есть порядка
𝑁
2
В среднем быстрая сортировка выполняет 2𝑁𝑙𝑜𝑔𝑁 сравнений. Проведем оценку количества сравнений, выполняемых во время быстрой сортировки N >= 2 случайно распределенных различных элементов.
С
𝑁
= 𝑁 + 1 +
1
𝑁
∑ (𝐶
𝑘−1
+ 𝐶
𝑁−𝑘
)
1≤𝑘≤𝑁
N+1 – количество сравнений опорного элемента на первом шаге алгоритма с N-1 элементом и еще двумя, когда индексы пересекутся. Каждый k-й элемент может быть центральным с вероятностью
1/N. После выбора k-го опорного элемента получаем частично упорядоченные части массива c размерами k-1 и N-k. Заметим, что С
0
+ С
1
+ ⋯ С
𝑁−1
= С
𝑁−1
+
С
𝑁−2
+…+С
0
. Значит,
С
𝑁
= 𝑁 + 1 +
2
𝑁
∑
𝐶
𝑘−1 1≤𝑘≤𝑁
Умножим обе части сравнения на N и вычтем эту же формулу для N-1.
𝑁С
𝑁
− (𝑁 − 1)С
𝑁−1
= 𝑁(𝑁 + 1) − (𝑁 − 1)𝑁 + 2С
𝑁−1
𝑁С
𝑁
= 2𝑁 + (𝑁 + 1)С
𝑁−1
Поделим обе части на 𝑁(𝑁 + 1) и получим соотношение С
𝑁
/(𝑁 + 1) = 2/(𝑁 + 1) + С
𝑁−1
/𝑁.
Применив дальнейшие преобразования, получим
С
𝑁
𝑁+1
=
2
𝑁+1
+
2
𝑁
+
С
𝑁−2
𝑁−1
= ⋯ =
С
2 3
+ ∑
2
𝑘+1 3≤𝑘≤𝑁
Из курса математического анализа в дальнейшем вы узнаете, что приблизительное значение
С
𝑁
𝑁+1
≈
2 ∑
1
𝑘
1≤𝑘<𝑁
≈ 2𝑙𝑛𝑁. То есть, сложность алгоритма быстрой сортировки в среднем равно 𝑂(𝑁𝑙𝑜𝑔 𝑁).
Поиск k-й порядковой статистики
Поиск k-й порядковой статистики заключается в поиске k-го элемента в упорядоченном по неубыванию массиве A, состоящего из N элементов. Первая порядковая статистика (k = 1)– это минимум массива, N-я порядковая статистика (k = N) – это максимум массива. Медиана – это порядковая статистика, где k=N/2. Приведем пример k-х порядковых статистик на примере конкретного массива.
Исходный массив а[16]
5 1
9 2
0 5
7 3
4 5
8 5
5 5
10 6
При k = 1, k-я порядковая статистика равна 0. При k = 3, k-я порядковая статистика равна 2.
Конечно, чтобы найти порядковую статистику, сначала можно отсортировать массив (например, при помощи быстрой сортировки за 𝑂(𝑁𝑙𝑜𝑔𝑁)), а затем вывести k-й элемент. Но оптимальный алгоритм поиска k-ой порядковой статистики работает за линейное в среднем время со сложностью 𝑂(𝑁).

ГОАОУ
«Центр поддержки одаренных детей
«Стратегия»
Липецкой области, к.т.н., доц. Шуйкова И.А., студент ИТМО, призер ВсОШ по информатике 2018 Первеев М.В.
Идея алгоритма схожа с алгоритмом быстрой сортировки. На вход алгоритма подаются l и r – левая и правая граница поиска k -ой порядковой статистики, число k. Перестановку элементов делаем так: находим первый «неправильный» элемент слева, затем первый «неправильный» элемент справа, и если не сошлись указатели обмениваем найденные значения. В зависимости от того, в какой части частично-упорядоченного массива находится индекс k, переходит в левую или правую часть. int k_st(vector<
int
> a, int l, int r, int k)
{ if
(l >= r) return a[l]; int i = l, j = r, p = a[(l + r) / 2]; while
(i < j)
{ while
(a[i] < p) i++; while
(a[j] > p) j--; if
(i < j)
{ swap(a[i], a[j]); i++; j--;
}
} if
(k >= l && k < i) return k_st(a, l, i - 1, k); else if
(j < k && k <= r) return k_st(a, j + 1, r, k); else return p;
}
Рассмотрим работу функции на примере массива a[7] = { 8, 9, 9, 1, 7, 5, 5 }, k = 5.
8 9 9 1 7 5 5 l=0 r=6 p=1 1 9 9 8 7 5 5 l=1 r=6 p=8 1 5 5 7 8 9 9 l=4 r=6 p=9 1 5 5 7 8 9 9 l=4 r=5 p=8 k-я порядковая статистика равна 8. Заметим, что алгоритм нахождения k-й порядковой статистики ставит k-й элемент упорядоченного массива на свое место. Также с помощью этого алгоритма можно найти k наименьших чисел массива – они будут находиться в интервале [0, k], но не будут упорядочены.
Сортировка слиянием
Идея алгоритма заключается в разделении массива на два подмассива. Каждый подмассив сортируется (к ним рекурсивно применяется сортировка слиянием). Полученные упорядоченные подмассивы объединяются в один отсортированный массив. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы – в массиве будет находиться один элемент
(массив из одного элемента упорядочен). void
Merge(vector<
int
> &tm, int l1, int m2, int r)
{ int k1 = l1, k2 = m2 + 1; vector<
int
> temp; while
(k1 <= m2 && k2 <= r)
{ if
(tm[k1] > tm[k2])

ГОАОУ
«Центр поддержки одаренных детей
«Стратегия»
Липецкой области, к.т.н., доц. Шуйкова И.А., студент ИТМО, призер ВсОШ по информатике 2018 Первеев М.В. temp.push_back(tm[k2++]); else temp.push_back(tm[k1++]);
} while
(k1 <= m2) temp.push_back(tm[k1++]); while
(k2 <= r) temp.push_back(tm[k2++]); for
(
int i = l1; i <= r; ++i) tm[i] = temp[i - l1];
} void
MergeSort(vector<
int
> &t, int l, int r)
{ if
(l >= r) return
; int m = (l + r) / 2;
MergeSort(t, l, m);
MergeSort(t, m + 1, r);
Merge(t, l, m, r);
}
Вызов сортировки
MergeSort(a, 0, a.size() - 1);
Алгоритм имеет сложность 𝑂(𝑁𝑙𝑜𝑔 𝑁).
Сортировка подсчётом
Сортировка QuickSort использовала операции сравнения элементов. Сортировка подсчетом
(Counting Sort) не использует операции сравнения, и применяется для массива A дискретных данных
(например, целых чисел, символов), которые принимают значения из небольшого диапазона
𝑎
𝑖
∈ [0, 𝐾 −
1]. Для данного алгоритма применяют вспомогательный массив C, элементы которого с[𝑖] = 𝑐𝑜𝑢𝑛𝑡(А, 𝑖)
, где 𝑐𝑜𝑢𝑛𝑡(А, 𝑖) - количество элементов в массиве А, равных значению i. Размер массива С равен максимальному элементу массива А.
Приведем пример исходного массива А и вспомогательного массива С.
a[i]
2 5
3 0
2 3
0 3
i
0 1
2 3
4 5
6 7
c[i]
2 1
3 2
2 3
2 3
По массиву С легко получить упорядоченный массив А. Делая проход по массиву С, мы столько раз последовательно включаем в массив А элемент i, сколько раз он встречался в А, а именнос[𝑖] раз. for
(
int i = 0; i < n; ++i) c[a[i]]++; int l=0; for
(
int i = 0; i < k; ++i)
{ for
(
int j = 1; j <= c[i]; ++j)
{ a[l] = i; l++;
}
}
Массив использует 𝑂(𝐾) дополнительной памяти и имеет сложность О(𝑁 + 𝐾). Сортировка подсчетом может быть реализована так, чтобы она обладала свойством стабильности.

ГОАОУ
«Центр поддержки одаренных детей
«Стратегия»
Липецкой области, к.т.н., доц. Шуйкова И.А., студент ИТМО, призер ВсОШ по информатике 2018 Первеев М.В.
Известны и другие сортировки, не использующие операции сравнения, например поразрядная сортировка.
Поразрядная сортировка
Рассмотрим идею поразрядной сортировки массива чисел. Например, необходимо выполнить сортировку массива трехразрядных чисел а[5] = { 523, 153, 088, 554, 235 }, k = 3 – количество разрядов.
Числа даны в десятичной системе счисления – m = 10. Дополнительно потребуются 10 векторов, отвечающие за цифру обрабатываемого разряда. Записываем числа исходного массива в векторы, отвечающие за цифры: 0, 1, 2, …, 9 в младшем разряде.
523, 153 – числа в векторе, отвечающем за цифру 3 .
554 - число в векторе, отвечающем за цифру 3.
235 – число в векторе, отвечающем за цифру 5.
088 -число в векторе, отвечающем за цифру 8.
Помещаем числа из вспомогательных векторов в исходный вектор.
Получаем: 523, 153, 554, 235, 088.
Производим распределение чисел во вспомогательные векторы по второму разряду.
523 235 153 554 088
Помещаем числа из вспомогательных векторов в исходный вектор.
Получаем: 523, 235, 153, 554, 088.
Производим распределение чисел во вспомогательные векторы по старшему разряду.
088 153 235 523 554
Помещаем числа из вспомогательных векторов в исходный вектор.
Получаем: 088, 153, 235, 523, 554. Получили отсортированный массив. Сложность сортировки
𝑂(𝑘𝑛 + 𝑘𝑚). Используется дополнительная память 𝑂(𝑛 + 𝑚).
Квадратичные сортировки. Справочная информация
В качестве справочной информации, приведем программные реализации некоторых квадратичных сортировок, то есть сортировок, которые имеют сложность - 𝑂(𝑁
2
). Приведенные ниже сортировки используют только сравнения и перестановки соседних элементов. Пузырьковая сортировка, сортировка вставками и выборочная сортировка не используют дополнительной памяти и являются стабильными.
Название сортировки
Пример реализации
Пузырьковая сортировка
BubbleSort
Сложность - 𝑂(𝑁
2
). for
(
int i = 0; i < n - 1; ++i)
{ for
(
int j = 0; j < n – i - 1; ++j)
{ if
(a[j + 1] < a[j]) swap(a[j], a[j + 1]);
}
}
Cортировка вставками
InsertSort int n, x, j;

ГОАОУ
«Центр поддержки одаренных детей
«Стратегия»
Липецкой области, к.т.н., доц. Шуйкова И.А., студент ИТМО, призер ВсОШ по информатике 2018 Первеев М.В.
Сложность в среднем 𝑂(𝑁
2
), в лучшем случае 𝑂(𝑁).
Может сортировать элементы в процессе их ввода int a[100]; cin >> n; cin >> x; a[0] = x; for (int i = 1; i < n; ++i)
{ cin>>x; for (j = i - 1; j >= 0 && a[j] > x; j--) a[j + 1] = a[j]; a[j + 1] = x;
}
Выборочная сортировка
SelectSort
Сложность - 𝑂(𝑁
2
) for
(
int i = 0; i < n; ++i)
{ min = a[i]; min_i = i; for
(
int j = i + 1; j < n; ++j) if
(a[j] < min)
{ min = a[j]; min_i = j;
} swap(a[min_i], a[i]);
}
Для файлов небольших размеров сортировка вставками и сортировка выбором работают примерно в два раза быстрее пузырьковой сортировки, однако время работы любого из этих алгоритмов квадратично зависит от размера файла. Поэтому ни один из этих методов не нужно использовать для сортировки больших случайно упорядоченных файлов.
Литература
1. Курс сайта www.stepic.org «Алгоритмы: теория и практика. Методы». Александр Куликов
2. Ворожцов А.В., Винокуров Н.А. Лекции «Алгоритмы: построение, анализ и реализация на языке программирования Си». – М.: Издательство МФТИ, 2007.
3. Курс сайта www.stepic.org «Введение в теоретическую информатику». Александр Шень.
4. Курс «Олимпиадные задачи по программированию». М.С. Густокашин. Электронный ресурс.
5. Седжвик Р. Алгоритмы на С++. – М.: ООО «И.Д. Вильямс», 2014 .