Сортировка гребней — Comb sort
Гребень рода является относительно простым алгоритмом сортировки , первоначально разработанный Влодзимежем Dobosiewicz и Артур Borowy в 1980 году, а затем вновь (и получил название «Combsort») Стивен Лейси и Ричард Box в 1991 году Comb рода улучшает пузырьковую сортировку таким же образом , что Shellsort улучшает сортировку вставками .
nist.gov ‘ s „уменьшение прироста рода“ определение упоминает термин „гребенку рода“ как визуализируя итерационный проходят данные „ где зубы гребенки прикосновения;“ первый термин связан с Доном Кнутом .
Алгоритм
Основная идея состоит в том, чтобы исключить черепах или небольшие значения в конце списка, поскольку при пузырьковой сортировке они значительно замедляют сортировку. Кролики , большие значения в начале списка, не представляют проблемы при пузырьковой сортировке.
В пузырьковой сортировке, когда любые два элемента сравниваются, они всегда имеют зазор (расстояние друг от друга), равный 1. Основная идея гребенчатой сортировки состоит в том, что зазор может быть намного больше 1. Внутренний цикл пузырьковой сортировки, который делает фактический своп , изменяются таким образом, что зазор между обмениваемыми элементами идет вниз (для каждой итерации внешнего цикла) с шагом в «сжиматься фактором» к : [ п / к , п / к 2 , п / к 3 ,. . 1].
Пробел начинается с деления длины сортируемого списка n на коэффициент сжатия k (обычно 1,3; см. Ниже), и к этому пробелу применяется один проход вышеупомянутой модифицированной пузырьковой сортировки. Затем промежуток снова делится на коэффициент сжатия, список сортируется с этим новым промежутком, и процесс повторяется до тех пор, пока промежуток не станет 1. На этом этапе сортировка гребенок продолжается с промежутком, равным 1, пока список не будет полностью отсортирован. Таким образом, заключительный этап сортировки эквивалентен сортировке по пузырькам, но к этому времени с большинством черепах уже разобрались, поэтому сортировка по пузырькам будет эффективной.
Фактор усадки имеет большое влияние на эффективность гребенчатой сортировки. k = 1,3 был предложен в качестве идеального коэффициента сжатия авторами оригинальной статьи после эмпирического тестирования более чем 200 000 случайных списков. Слишком маленькое значение замедляет алгоритм, делая ненужное много сравнений, в то время как слишком большое значение не позволяет эффективно справиться с черепахами, что требует много проходов с 1 размером промежутка.
Шаблон повторяющихся проходов сортировки с уменьшающимися промежутками аналогичен Shellsort, но в Shellsort массив полностью сортируется на каждом проходе перед переходом к следующему наименьшему промежутку. Проходы гребенчатой сортировки не полностью сортируют элементы. Это причина того, что последовательности разрывов Shellsort имеют больший оптимальный коэффициент сжатия, составляющий около 2,2.
Псевдокод
function combsort(array input) is gap := input.size // Initialize gap size shrink := 1.3 // Set the gap shrink factor sorted := false loop while sorted = false // Update the gap value for a next comb gap := floor(gap / shrink) if gap ≤ 1 then gap := 1 sorted := true // If there are no swaps this pass, we are done end if // A single "comb" over the input list i := 0 loop while i + gap < input.size// See Shell sort for a similar idea if input[i] > input[i+gap] then swap(input[i], input[i+gap]) sorted := false // If this assignment never happens within the loop, // then there have been no swaps and the list is sorted. end if i := i + 1 end loop end loop end function
Код Python
Плюс две быстрые реализации Python: одна работает со списком (или массивом, или другим изменяемым типом, где операции, используемые с ним, имеют смысл для языка) на месте, другая составляет список с теми же значениями, что и заданные данные, и возвращает это после сортировки (аналогично встроенной функции `sorted`).
def combsort_inplace(data): length = len(data) shrink = 1.3 _gap = length sorted = False while not sorted: # Python has no builtin 'floor' function, so we/I just have one variable (_gap) to be shrunk, # and an integer variable (gap) to store the truncation (of the other variable) in and # to use for stuff pertaining to indexing _gap /= shrink # gap = np.floor(_gap) gap = int(_gap) if gap 1: sorted = True gap = 1 # equivalent to `i = 0; while (i + gap) < length: . . i += 1` for i in range(length - gap): sm = gap + i if data[i] > data[sm]: # because Python is very nice, this accomplishes the swap data[i], data[sm] = data[sm], data[i] sorted = False def combsort(data): length = len(data) shrink = 1.3 _gap = length out = list(data) is_sorted = False while not is_sorted: _gap /= shrink gap = int(_gap) if gap 1: is_sorted = True gap = 1 for i in range(length - gap): sm = gap + i if out[i] > out[sm]: out[i], out[sm] = out[sm], out[i] is_sorted = False return out
Смотрите также
- Пузырьковая сортировка , обычно более медленный алгоритм, является основой гребенчатой сортировки.
- Коктейльная сортировка или двунаправленная пузырьковая сортировка — это разновидность пузырьковой сортировки, которая также решает проблему черепах, хотя и менее эффективно.
WikiSort.ru — Программирование
Сортировка расчёской ( англ. comb sort ) — это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991 г [1] . Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком).
В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица (сортировка Шелла также основана на этой идее, но она является модификацией сортировки вставками, а не сортировки пузырьком).
Алгоритм
В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди. Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной величины, называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива, разделённого на фактор уменьшения (результат округляется до ближайшего целого). Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.
Реализация на Паскаль
const n = 5; var a: array [0..n] of integer; i, jr: integer; j: real; begin for i := 0 to n do a[i] := Random(12); j := n; jr := Round(j); while i i + jr do begin i := 0; jr := Round(j); while i + j n do begin if a[i] > a[i + Round(j)] then begin a[i] := a[i] + a[i + jr]; a[i + jr] := a[i] - a[i + jr]; a[i] := a[i] - a[i + jr]; end; Inc(i); end; j := j / 1.247; end; for i := 0 to n do begin for jr := 0 to i - 1 do begin if a[jr] > a[jr + 1] then begin a[jr] := a[jr] + a[jr + 1]; a[jr + 1] := a[jr] - a[jr + 1]; a[jr] := a[jr] - a[jr + 1]; end; end; end; Writeln(a); end.
Цикл прекратится лишь тогда, когда j станет равной 0, иначе говоря, когда i станет равным i + j.
Реализация на C++
int comb(vectordouble> sort)// sort-название массива, size-размер массива,если нужно ввести массив с клавиатуры, то нужно создать динамический массив int n = 0; // количество перестановок double fakt = 1.2473309; // фактор уменьшения double step = sort.size() - 1; while (step >= 1) for (int i = 0; i + step sort.size(); ++i) if (sort[i] > sort[i + step]) swap(sort[i], sort[i + step]); n++; > > step /= fakt; > // сортировка пузырьком for (int i = 0; i sort.size() - 1; i++) bool swapped = false; for (int j = 0; j sort.size() - i - 1; j++) if (sort[j] > sort[j + 1]) swap(sort[j], sort[j + 1]); swapped = true; ++n; > > if (!swapped) break; > return n; >
Реализация на 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++; > > >
Реализация на PHP
function combsort($array) $sizeArray = count($array); // Проходимся по всем элементам массива for ($i = 0; $i $sizeArray; $i++) // Сравниваем попарно. // Начинаем с первого и последнего элемента, затем постепенно уменьшаем // диапазон сравниваемых значеный. for ($j = 0; $j $i + 1; $j++) // Индекс правого элемента в текущей итерации сравнения $elementRight = ($sizeArray - 1) - ($i - $j); if ($array[$j] > $array[$elementRight]) $buff = $array[$j]; $array[$j] = $array[$elementRight]; $array[$elementRight] = $buff; unset($buff); > > > return $array; >
Реализация на Python
def combsort(alist): alen = len(alist) gap = (alen * 10 // 13) if alen > 1 else 0 while gap: if 8 gap 11: ## variant "comb-11" gap = 11 swapped = False for i in range(alen - gap): if alist[i + gap] alist[i]: alist[i], alist[i + gap] = alist[i + gap], alist[i] swapped = True gap = (gap * 10 // 13) or swapped
Реализация на JavaScript
function combSorting(array) const factor = 1.247; let gapFactor = array.length / factor; while (gapFactor > 1) const gap = Math.round(gapFactor); for (let i = 0, j = gap; j array.length; i++, j++) if (array[i] >= array[j]) [ array[i], array[j] ] = [ array[j], array[i] ]; > > gapFactor = gapFactor / factor; > return array; >
Примечания
- ↑Lacey S., Box R. A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines (англ.) // Byte. — Апрель 1991. — Vol. 16, no. 4 . — P. 315—320. — ISSN0360-528.