C++: сортировка вставками со сторожевым элементом
Изучали сортировку вставками массива целых чисел с реализацией на C/C++. Тема достаточно заезженная, в интернете много информации, десятки реализаций этого алгоритма на разных языках программирования. Дошел до объяснения некоторых способов оптимизации этого алгоритма, в частности рассмотрели оптимизацию с помощью так называемого «сторожевого» элемента. После выполнения домашних заданий выяснилось, что многие студенты не поняли, как работает эта оптимизация. К тому же, в интернете почему-то мало информации по этой теме (вот вменяемый источник по этому вопросу).
Я решил немного прояснить этот момент в этом посте.
Сортировка вставками без оптимизации
Отправная точка: одна из реализаций сортировки вставками без оптимизаций на языке C++ (ближе к Си, конечно, так как до классов мы пока еще в тот момент не дошли по учебному плану, то же касается и шаблонов функций):
// функция сортировки вставками массива целых чисел (по возрастанию)
void insertionSort(int arr[], const int arrSize)
{
for(int i{ 1 }; i < arrSize; i++) // внешний цикл
{
int key = arr[i]; // очередной элемент для вставки (ключ)
int j{};
for(j = i - 1; j >= 0 && arr[j] > key; j--) // внутренний цикл
{
arr[j + 1] = arr[j]; // сдвиг элементов вправо
}
arr[j + 1] = key; // вставка элемента (ключа) в нужное место
}
}
Суть алгоритма сортировки вставками в том, что массив разбивается на две части: отсортированную и не отсортированную (этот прием используется и в других алгоритмах), затем мы поочередно берем элементы из неотсортированной части и вставляем их на правильное место в отсортированной части (из-за этих вставок данный алгоритм и получил свое название).
В приведенной выше реализации отсортированная часть находится слева, неотсортированная - справа. В самом начале в отсортированную часть входит только один элемент массива (его индекс равен нулю). Элементы в неотсортированной части массива - это элемент с индексом 1 и все после него до конца массива. Поэтому внешний цикл в реализации выше начинает свою работу с индекса 1. В ходе работы внешнего цикла отсортированная часть постепенно увеличивается, а неотсортированная часть массива постепенно уменьшается. После окончания работы внешнего цикла все элементы массива окажутся в отсортированной части.
Внутренний цикл нужен для поиска правильного места в отсортированной части массива для очередного элемента (ключа), взятого из неотсортированной части массива. При поиске правильного места мы постепенно сдвигаем отсортированную часть вправо поэлементно, пока не найдем нужное место, в которое и записываем сортируемый элемент (ключ). Такой способ сортировки позволяет производить сортировку на месте самого сортируемого массива. Дополнительно в памяти создается место только для переменной key (ключ), в которую мы временно сохраняем очередной сортируемый элемент.
В реализации алгоритма, приведенной выше, сортировка происходит по возрастанию. Для сортировки по убыванию достаточно сменить одну из операций сравнения в заголовке внутреннего цикла на противоположную (изменение выделено красным цветом):
for(j = i - 1; j >= 0 && arr[j] < key; j--) // внутренний цикл
Итак, второе подусловие во внутреннем цикле служит для определения правильного места при вставке сортируемого элемента в отсортированную часть массива. Также с помощью операции сравнения во втором подусловии можно переключать тип сортировки: по возрастанию или по убыванию.
А зачем нужно первое подусловие j >= 0? Оно нужно, чтобы при поиске правильного места для сортируемого элемента в отсортированной части массива поиск не ушел за пределы левой границы массива. Если поиск уйдет за левую границу массива, то это приведет к неопределенному поведению программы, что является ошибкой.
Сортировка вставками со сторожевым элементом
В качестве одного из способов оптимизации вышеприведенной реализации предлагают избавиться от первого подусловия j >= 0 внутреннего цикла. На проверку этого подусловия тратится время, если это подусловие убрать, время работы программы уменьшится (совсем чуть-чуть, но на практике бывают случаи, когда и такая мелочь важна).
Для того, чтобы не случилось выхода за левую границу сортируемого массива, предлагают вместо элемента с нулевым индексом поставить самое маленькое число (при сортировке по возрастанию; при сортировке по убыванию это должно быть самое большое число), которое может быть (элемент с нулевым индексом при этом можно сохранить в отдельную временную переменную). Таким образом элемент с нулевым индексом превращается в «сторожевой» элемент, который ни при каких обстоятельствах не даст выйти за левую границу массива при поиске правильного места для очередного сортируемого элемента.
После окончания обычной работы алгоритма сортировки вставками нужно будет в дополнительном цикле еще один раз поэлементно сдвинуть элементы отсортированной части влево и в нужный момент вставить в правильное место значение сохраненного в начале элемента с нулевым индексом.
Вот реализация сортировки вставками со сторожевым элементом (тип сортировки: по возрастанию):
// сортировка вставками (со сторожевым элементом) массива целых чисел
void insertionSort2(int arr[], const int arrSize)
{
int backup = arr[0]; // сохранить значение нулевого элемента
arr[0] = INT_MIN; // нулевой элемент стал сторожевым
for(int i{ 1 }; i < arrSize; i++) // внешний цикл
{
int key = arr[i];
int j{};
for(j = i - 1; arr[j] > key; j--) // внутренний цикл (убрано первое подусловие)
{
arr[j + 1] = arr[j]; // сдвиг элементов вправо
}
arr[j + 1] = key;
}
int k{};
for(k = 1; k < arrSize && arr[k] < backup; k++) // дополнительный цикл
{ // (поиск места для backup)
arr[k - 1] = arr[k]; // сдвиг элементов влево
}
arr[k - 1] = backup; // вставка backup на найденное место
}
Поскольку в нашей реализации мы сортируем целые числа типа int, то можем использовать стандартные константы INT_MIN и INT_MAX для сторожевого элемента при сортировке соответственно по возрастанию или по убыванию. Для работы с этими константами нужно подключить библиотеку .
Замер времени работы реализаций алгоритмов
Для замера времени работы (в наносекундах) реализаций алгоритмов можно использовать возможности стандартной библиотеки , но для ее корректной работы может потребоваться запустить компилятор с поддержкой возможностей свежего стандарта C++20 или более новых. Вот полезные источники по этой теме:
https://en.cppreference.com/w/cpp/chrono/high_resolution_clock/now
https://stackoverflow.com/questions/7889136/stdchrono-and-cout
Я решил немного прояснить этот момент в этом посте.
Сортировка вставками без оптимизации
Отправная точка: одна из реализаций сортировки вставками без оптимизаций на языке C++ (ближе к Си, конечно, так как до классов мы пока еще в тот момент не дошли по учебному плану, то же касается и шаблонов функций):
// функция сортировки вставками массива целых чисел (по возрастанию)
void insertionSort(int arr[], const int arrSize)
{
for(int i{ 1 }; i < arrSize; i++) // внешний цикл
{
int key = arr[i]; // очередной элемент для вставки (ключ)
int j{};
for(j = i - 1; j >= 0 && arr[j] > key; j--) // внутренний цикл
{
arr[j + 1] = arr[j]; // сдвиг элементов вправо
}
arr[j + 1] = key; // вставка элемента (ключа) в нужное место
}
}
Суть алгоритма сортировки вставками в том, что массив разбивается на две части: отсортированную и не отсортированную (этот прием используется и в других алгоритмах), затем мы поочередно берем элементы из неотсортированной части и вставляем их на правильное место в отсортированной части (из-за этих вставок данный алгоритм и получил свое название).
В приведенной выше реализации отсортированная часть находится слева, неотсортированная - справа. В самом начале в отсортированную часть входит только один элемент массива (его индекс равен нулю). Элементы в неотсортированной части массива - это элемент с индексом 1 и все после него до конца массива. Поэтому внешний цикл в реализации выше начинает свою работу с индекса 1. В ходе работы внешнего цикла отсортированная часть постепенно увеличивается, а неотсортированная часть массива постепенно уменьшается. После окончания работы внешнего цикла все элементы массива окажутся в отсортированной части.
Внутренний цикл нужен для поиска правильного места в отсортированной части массива для очередного элемента (ключа), взятого из неотсортированной части массива. При поиске правильного места мы постепенно сдвигаем отсортированную часть вправо поэлементно, пока не найдем нужное место, в которое и записываем сортируемый элемент (ключ). Такой способ сортировки позволяет производить сортировку на месте самого сортируемого массива. Дополнительно в памяти создается место только для переменной key (ключ), в которую мы временно сохраняем очередной сортируемый элемент.
В реализации алгоритма, приведенной выше, сортировка происходит по возрастанию. Для сортировки по убыванию достаточно сменить одну из операций сравнения в заголовке внутреннего цикла на противоположную (изменение выделено красным цветом):
for(j = i - 1; j >= 0 && arr[j] < key; j--) // внутренний цикл
Итак, второе подусловие во внутреннем цикле служит для определения правильного места при вставке сортируемого элемента в отсортированную часть массива. Также с помощью операции сравнения во втором подусловии можно переключать тип сортировки: по возрастанию или по убыванию.
А зачем нужно первое подусловие j >= 0? Оно нужно, чтобы при поиске правильного места для сортируемого элемента в отсортированной части массива поиск не ушел за пределы левой границы массива. Если поиск уйдет за левую границу массива, то это приведет к неопределенному поведению программы, что является ошибкой.
Сортировка вставками со сторожевым элементом
В качестве одного из способов оптимизации вышеприведенной реализации предлагают избавиться от первого подусловия j >= 0 внутреннего цикла. На проверку этого подусловия тратится время, если это подусловие убрать, время работы программы уменьшится (совсем чуть-чуть, но на практике бывают случаи, когда и такая мелочь важна).
Для того, чтобы не случилось выхода за левую границу сортируемого массива, предлагают вместо элемента с нулевым индексом поставить самое маленькое число (при сортировке по возрастанию; при сортировке по убыванию это должно быть самое большое число), которое может быть (элемент с нулевым индексом при этом можно сохранить в отдельную временную переменную). Таким образом элемент с нулевым индексом превращается в «сторожевой» элемент, который ни при каких обстоятельствах не даст выйти за левую границу массива при поиске правильного места для очередного сортируемого элемента.
После окончания обычной работы алгоритма сортировки вставками нужно будет в дополнительном цикле еще один раз поэлементно сдвинуть элементы отсортированной части влево и в нужный момент вставить в правильное место значение сохраненного в начале элемента с нулевым индексом.
Вот реализация сортировки вставками со сторожевым элементом (тип сортировки: по возрастанию):
// сортировка вставками (со сторожевым элементом) массива целых чисел
void insertionSort2(int arr[], const int arrSize)
{
int backup = arr[0]; // сохранить значение нулевого элемента
arr[0] = INT_MIN; // нулевой элемент стал сторожевым
for(int i{ 1 }; i < arrSize; i++) // внешний цикл
{
int key = arr[i];
int j{};
for(j = i - 1; arr[j] > key; j--) // внутренний цикл (убрано первое подусловие)
{
arr[j + 1] = arr[j]; // сдвиг элементов вправо
}
arr[j + 1] = key;
}
int k{};
for(k = 1; k < arrSize && arr[k] < backup; k++) // дополнительный цикл
{ // (поиск места для backup)
arr[k - 1] = arr[k]; // сдвиг элементов влево
}
arr[k - 1] = backup; // вставка backup на найденное место
}
Поскольку в нашей реализации мы сортируем целые числа типа int, то можем использовать стандартные константы INT_MIN и INT_MAX для сторожевого элемента при сортировке соответственно по возрастанию или по убыванию. Для работы с этими константами нужно подключить библиотеку .
Замер времени работы реализаций алгоритмов
Для замера времени работы (в наносекундах) реализаций алгоритмов можно использовать возможности стандартной библиотеки , но для ее корректной работы может потребоваться запустить компилятор с поддержкой возможностей свежего стандарта C++20 или более новых. Вот полезные источники по этой теме:
https://en.cppreference.com/w/cpp/chrono/high_resolution_clock/now
https://stackoverflow.com/questions/7889136/stdchrono-and-cout