Алгоритмы и структуры данных

Сортировка расчёской

Простой и эффективный алгоритм сортировки на основе сравнения, который является улучшением алгоритма пузырьковой сортировки.

Алгоритм:
Шаг 1: Инициализируем gap. Обычно он равен длине массива, деленной на 1,3.
Шаг 2: Сравниваем элементы, расположенные на текущем промежутке. Если элементы не в правильном порядке, поменяйте их местами. Продолжайте сравнивать и менять местами элементы с одинаковым зазором по всему массиву.
Шаг 3: Каждый раз по окончанию прохода через весь массив с текущим значением gap, мы уменьшаем его на фиксированный коэффициент 1,3. Повторяем процесс сравнения и замены с новым, меньшим зазором.
Шаг 4: Когда gap = 1, выполните последний проход по массиву. Наш массив отсортирован.

Сложность: O(n*log(n))

www.tgoop.com/the_algorithms/4567

6.9K viewsOct 6, 2023 at 08:59

Сортировка расчёской

Простой и эффективный алгоритм сортировки на основе сравнения, который является улучшением алгоритма пузырьковой сортировки.

Алгоритм:
Шаг 1: Инициализируем gap. Обычно он равен длине массива, деленной на 1,3.
Шаг 2: Сравниваем элементы, расположенные на текущем промежутке. Если элементы не в правильном порядке, поменяйте их местами. Продолжайте сравнивать и менять местами элементы с одинаковым зазором по всему массиву.
Шаг 3: Каждый раз по окончанию прохода через весь массив с текущим значением gap, мы уменьшаем его на фиксированный коэффициент 1,3. Повторяем процесс сравнения и замены с новым, меньшим зазором.
Шаг 4: Когда gap = 1, выполните последний проход по массиву. Наш массив отсортирован.

Сложность: O(n*log(n))

BY Алгоритмы и структуры данных