QUICK SORT усиление сортировкой INSERT

[JON_BOY]

Я бы хотел узнать как правильно записать CUTOFF,который рекомендуется
для QUICK SORT если элементов в массиве например не велико, ну допустим колеблется от 3 до 30-40. С тем чтобы вызвать сортировку вставкой.

И использую например такой алгоритм на VB
Т.е где его добавить и как его определить в зависимости от количества элементов ?
Спасибо

Sub QUICK_SORT_FULL(X, Y)



' If Y > X + CUTOFF Then

If Y > X Then

Dim XX
Dim YY
Dim PAT
'--------------------------------------------------
PAT = (X + Y) * 0.5 '(/2)
PAT = L(PAT).G_B2
XX = X
YY = Y
'--------------------------------------------------
Do
Do While L(XX).G_B2 > PAT: XX = XX + 1: Loop
Do While L(YY).G_B2 < PAT: YY = YY - 1: Loop
If XX > YY Then Exit Do
CopyMemory TEMP, L(YY), 10
CopyMemory L(YY), L(XX), 10
CopyMemory L(XX), TEMP, 10
XX = XX + 1
YY = YY - 1
Loop While XX <= YY

If X<Y then QUICK_SORT_FULL XX, Y
If X < YY Then QUICK_SORT_FULL X, YY


'If YY > SORT_FERST Then QUICK_SORT_FULL X, YY
'If YY > SORT_FERST + CUTOFF Then QUICK_SORT_FULL X, YY


End If

Подобрать методом монте карло. Генеришь случайные массивы, замеряешь сколько твой сорт работает для разных cutoffов и ищеш минимум.

[JON_BOY]

Ну да понятно. Но думалось что будет проще.
Только уточнение
Правильно так:
If XX < Y Then QUICK_SORT_FULL XX, Y
If X < YY Then QUICK_SORT_FULL X, YY

Но не совсем ясно куда cutoff (лепится ?)


If XX < Y+CUT Then QUICK_SORT_FULL XX, Y
If X < YY+CUT Then QUICK_SORT_FULL X, YY

Что у тебя в коде X и Y? Индекс начального и конечного элемента в подмассиве что ли? В таком случае в начале процедуры сравниваешь X-Y с катоффом, и если X-Y меньше, то сортируешь вставками.

[JON_BOY]

Что у тебя в коде X и Y? Индекс начального и конечного элемента в подмассиве что ли? В таком случае в начале процедуры сравниваешь X-Y с катоффом, и если X-Y меньше, то сортируешь вставками.

Ну да начальный индекс и конечный,только эти индексы
могут быть в разном интервале не обязательно от 0....
а например 50 ....100 итд.
Потом, не знаю что значит под массив, это просто один массив-структура.
Потом, сортировка INSERT делается после завершения быстрой сортировки
внутри Qwick sort нужно выйти из рекурсии. И значит в начале, я не понял.

x-y может быть сразу =50-100=-50
cutoff=5
x-y меньше cutoff сразу и выполняется процедура INSERT
извените у меня своя логика я не понимаю.
Может вы имеете ввиду перед запуском Qwick Sort
If Y-X<CUTOFF then INSERT ?

Потом, сортировка INSERT делается после завершения быстрой сортировки. внутри Qwick sort нужно выйти из рекурсии.

Можно и так. Тогда значит при входе в процедуру проверяешь, если Y-X < CUTOFF, тогда выходишь и все.

[JON_BOY]

Если проще говоря, лучше взять алгоритм приведенный на сайте с примером cutoffof и после завершения быстрой сортировки вызывать сортировку вставкой.
Ваш пример я нашел в рекомендацияx по алгоритмам VB,где вызов сортировки происходит внутри. Но там не вставочная а селективная (другой метод). Я пробовал этот вариант с INSERT,но получается что INSERT вызывается большое количество раз а это не годится.
Меня же просто интересует где добавляются cutоff(ы) в моем примере и все.

получается что INSERT вызывается большое количество раз а это не годится.

он должен вызываться примерно N/cutoff раз. И разницы почти нет, вызывать insertion sort N/cutoff раз на маленьких массивах размера cutoff или один раз сразу на всех этих маленьких массивах вместе.

Меня же просто интересует где добавляются cutоff(ы) в моем примере и все.

в самое начало
if Y-X < CUTOFF then return end if

и в любом случае на Си будет гораздо быстрее