UniLecs. Топ-10 вопросов по сортировке
UniLecs
🔥 Мы начинаем цикл статей, посвященных алгоритмам сортировки. Сразу скажу, что здесь мы коснемся только основных понятий в алгоритмике сортировок: основные свойства алгоритмов, понятия устойчивая/неустойчивая сортировка, а также затронем оценки эффективности алгоритмов. Цель этих статей - помочь вам вспомнить или освежить в памяти основные моменты и особенности сортировок, это будет некая шпаргалка для тех, кто готовится к техническому интервью или к экзамену в университете.
Если же вы хотите более подробно изучить тему сортировок, то рекомендую взять/скачать/купить книгу Дональда Кнута: Искусство программирования. Том 3. Сортировка и поиск. Кстати, я подробно описывал эту книгу в своей подборке основных книг по программированию.
А начинаем наш цикл статей с важных понятий сортировок. Итак, топ-10 вопросов по сортировкам.
1. Назовите основные свойства/параметры, по которым оценивают алгоритмы сортировки.
- Время — основной параметр, характеризующий быстродействие алгоритма. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный [1…n]. Худшее время — наибольшее время.
- Память - ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и не зависящие от входной последовательности затраты, например, на хранение кода программы.
- Устойчивость — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.
- Естественность поведения - эффективность метода при обработке уже отсортированных или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности, и работает лучше.
2. Чем отличается класс внутренней сортировки от класса внешней сортировки?
- Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
Особенности: в современных архитектурах компьютеров и системных архитектурах широко применяется подкачка и кэширование памяти. Поэтому в большинстве случаев имеется возможность использовать внутреннюю сортировку даже для задач, в которых объём данных несколько превышает выделяемую процессу оперативную память. - Внешняя сортировка оперирует запоминающими устройствами большого объема, но с доступом не произвольным, а последовательным (сортировка файлов), т.е. в данный момент мы 'видим' только один элемент, а затраты на перемотку, по сравнению с памятью, неоправданно велики . Это приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство.
Особенности: доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим; объем данных не позволяет им разместиться в ОЗУ.
3. Вам надо отсортировать массив из 6 элементов. Какая сортировка быстрее это выполнит?
BubbleSort (Пузырьковая сортировка) - простейшая сортировка, эффективная для небольших массивов.
4. Какой алгоритм сортировки является фактически худшим?
Bogosort (также случайная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.
5. Выберите алгоритмы сортировки для которых асимптотическая оценка в наихудшем случае O(n^2)
- Сортировка выбором (Selection Sort)
- Быстрая сортировка(Quick Sort) - для быстрой сортировки наихудший случай O(n^2) маловероятен
- Пузырьковая сортировка(Bubble Sort)
- Сортировка вставками (Insertion Sort)
- Сортировка Шелла (Shellsort)
6. В чём отличие устойчивой сортировки от неустойчивой?
Устойчивой сортировкой называют алгоритм, который не меняет последовательность одинаковых элементов. Соответственно, неустойчивая может их менять.
Пример важности устойчивости: допустим, в магазин привезли молоко. Все пакеты молока заносятся в базу (файл) последовательно. Магазину нужно быстрее продать эти пакеты, т.к. молоко быстро портится.
Мы сортируем массив устойчивой сортировкой, например, по производителю, и первыми будут как раз пакеты, которые привезли в магазин раньше всех. Их и нужно продать быстрее остальных.
Если бы мы использовали неустойчивый алгоритм сортировки, то магазин мог поступить не очень рационально и продать пакеты молока, которые могли бы еще полежать :)
7. Назовите минимум 3 устойчивые сортировки (при которой порядок одинаковых элементов не меняется)
- Пузырьковая сортировка (Bubble sort)
- Сортировка слиянием (Merge sort)
- Сортировка вставками (Insertion sort)
8. Назовите минимум 3 неустойчивые сортировки (при которой порядок одинаковых элементов может меняться)
- Сортировка выбором (Selection sort)
- Сортировка Шелла (Shell sort)
- Пирамидальная сортировка (Heapsort)
9. Тонкости сортировки
На техническом интервью программист реализовал две сортировки: сортировку выбором и пузырьковую сортировку. Оба варианта используют одну и ту же функцию обмена элементов массива (с помощью 3й вспомогательной переменной).
void Swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Обе сортировки работают правильно (хотя пузырьковая раза в два медленнее).
Но позже программист вспомнил, что обмен можно произвести без промежуточной переменной, а с помощью операции побитового "исключающего или" и исправил функцию:
void Swap(int i, int j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
Однако выяснилось, что сортировка выбором перестала работать правильно.
Пояснение: Функция обмена с помощью "исключающего или", будучи вызвана для одного и того же элемента, обнуляет его. В пузырьковой сортировке такие случаи исключены. В сортировке выбором для этого нужно сделать специальную проверку.
10. Правильно ли утверждение, что лучший на практике алгоритм быстрой сортировки (QuickSort) фактически является существенной модификацией одного из худших алгоритмов Пузырьковой сортировки?
Да.
Пояснение: QuickSort является существенно улучшенным вариантом алгоритма Пузырьковой сортировки с помощью прямого обмена, известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии, и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.
Общая идея алгоритма состоит в следующем:
- Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
- Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».
- Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.