Показать меню
Показать категории

Чем сортировка методом Шелла отличается от сортировки методом прямого выбора?

+1 голос
201 просмотров
спросил(а) enginr (111 баллов) в категории Образование и наука

1 Ответ

+1 голос
 
Лучший ответ

Общая схема алгоритма сортировки методом прямого выбора имеет следующий

вид:

-1.Выбирается наименьщий из элементов массива.

-2.Выбранный элемент меняется местами с первым элементом.

Первый элемент считается отсортированным, само действие повторяется вначале для n-1 элементов массива, затем для n-2, вплоть до того, пока в неотсортированной части массива не остается один, являющийся наиболее большим в исходном массиве, элемент. Алгоритм имеет квадратичную размерность n² .

 

Суть сортировки массива данных методом Шелла, заключена в многократном разбиении исходного массива на группы и их независимой сортировке.

Например, необходимо разбить исходный массив на четыре группы элементов, отстоящих друг от друга на расстояние 4, и отсортировать каждую четвертную группу независимо (к примеру,методом прямого выбора). Затем, на втором этапе, сформировать две группы, в которых элементы отстоят друг от друга на две позиции, и произвести их сортировку отдельно для каждой из групп (двойная сортировка). На последнем этапе производится одинарная сортировка всего имеющегося массива, в результате чего получается упорядоченный массив.

Выигрыш данного метода достигается за счет того, что меняются элементы, расположенные на значительном расстоянии друг от друга.

ответил(а) Александра-lab (404 баллов)

...