Алгоритмы на C++

Идея сортировки Shell Sort - это по сути просто усовершенствование алгоритма Insertion Sort. Суть в том, чтобы повторить Insertion Sort несколько раз, только сравнивать не рядом стоящие элементы, а элементы стоящие друг от друга на расстоянии d, которое будет изменяться на каждой итерации определённым образом. Существует несколько способов выбора значений для d, но в этой статье представлен один способ - деление расстояния d на 2. Стоит заметить, что при d = 1 - будут сравниваться рядом стоящие элементы, как и в обычном Insertion Sort...

Идея сортировки Представим, что у нас есть неотсортированный массив A. Нам нужно его отсортировать по неубыванию. Давайте будем рассматривать поочерёдно каждый элемент массива, начиная со второго элемента(под индексом 1), и заканчивая последним элементом массива A. Процесс "рассмотрения" элемента будет выглядеть следующим образом: 1)Мы знаем, что слева от рассматриваемого нами элемента...

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

Идея оптимизации Посредством добавления флага swapped, который будет равняться true, если на предыдущей итерации элементы были поменяны местами хотя бы один раз, иначе будет равняться false. Теперь, если мы увидим, что swapped == false, то есть на предыдущей итерации мы не встретили хотя бы два элемента, идущие не по порядку (то есть все элементы стоят по порядку, а следовательно...

Идея Идея заключается в том, чтобы за одну итерацию по массиву мы подняли самый наибольший элемент области сортировки наверх (в конец области сортировки). После каждой итерации область, которую мы сортируем, уменьшается...