Общая схема алгоритма сортировки методом прямого выбора имеет следующий
вид:
-1.Выбирается наименьщий из n элементов массива.
-2.Выбранный элемент меняется местами с первым элементом.
Первый элемент считается отсортированным, само действие повторяется вначале для n-1 элементов массива, затем для n-2, вплоть до того, пока в неотсортированной части массива не остается один, являющийся наиболее большим в исходном массиве, элемент. Алгоритм имеет квадратичную размерность n² .
Суть сортировки массива данных методом Шелла, заключена в многократном разбиении исходного массива на группы и их независимой сортировке.
Например, необходимо разбить исходный массив на четыре группы элементов, отстоящих друг от друга на расстояние 4, и отсортировать каждую четвертную группу независимо (к примеру,методом прямого выбора). Затем, на втором этапе, сформировать две группы, в которых элементы отстоят друг от друга на две позиции, и произвести их сортировку отдельно для каждой из групп (двойная сортировка). На последнем этапе производится одинарная сортировка всего имеющегося массива, в результате чего получается упорядоченный массив.
Выигрыш данного метода достигается за счет того, что меняются элементы, расположенные на значительном расстоянии друг от друга.
