- Сортировка расчёской
-
Сортировка расчёской (англ. comb sort) — это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991 г[1]. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком).
В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица (сортировка Шелла также основана на этой идее, но она является модификацией сортировки вставками, а не сортировки пузырьком).
Содержание
Алгоритм
Этот раздел ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться специальный раздел.
Вы можете помочь проекту, написав этот раздел.Реализация на C++
void sort( data *array, dword size ) { if (!array || !size) return; dword jump = size; bool swapped = true; while (jump > 1 || swapped) { if (jump > 1) jump = (dword)(jump / 1.25); swapped = false; for (dword i = 0; i + jump < size; i++) if (array[i] > array[i + jump]) swap(array, i, i + jump), swapped = true; } }
Реализация на Java
public static <E extends Comparable<? super E>> void sort(E[] input) { int gap = input.length; boolean swapped = true; while (gap > 1 || swapped) { if (gap > 1) gap = (int) (gap / 1.247330950103979); int i = 0; swapped = false; while (i + gap < input.length) { if (input[i].compareTo(input[i + gap]) > 0) { E t = input[i]; input[i] = input[i + gap]; input[i + gap] = t; swapped = true; } i++; } } }
Примечания
Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 14 мая 2011.Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.