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

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

1 Ответ

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

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

вид:

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

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

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

 

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

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

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

ответил 22 Март, 14 Александра-lab (404 баллов)
выбран 27 Март, 14 enginr


Знаете ответ? Помогите другим! (без регистрации)

Отображаемое имя (по желанию):
Конфиденциальность: Ваш электронный адрес будет использоваться только для отправки уведомлений.
Анти-спам проверка:

Чтобы избежать проверки в будущем, пожалуйста войдите или зарегистрируйтесь.
Вы можете начать, задав вопрос.
...