Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 13.11.2010, 17:59
Новичок

Отправить личное сообщение для JON_BOY Посмотреть профиль Найти все сообщения от JON_BOY
 
Регистрация: 11.11.2010
Сообщений: 5

QUICK SORT усиление сортировкой INSERT
Я бы хотел узнать как правильно записать 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
  #2  
Старый 13.11.2010, 18:09
гость

 
Сообщений: n/a

Подобрать методом монте карло. Генеришь случайные массивы, замеряешь сколько твой сорт работает для разных cutoffов и ищеш минимум.
  #3  
Старый 13.11.2010, 18:44
Новичок

Отправить личное сообщение для JON_BOY Посмотреть профиль Найти все сообщения от JON_BOY
 
Регистрация: 11.11.2010
Сообщений: 5

Ну да понятно. Но думалось что будет проще.
Только уточнение
Правильно так:
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
  #4  
Старый 13.11.2010, 20:13
гость

 
Сообщений: n/a

Что у тебя в коде X и Y? Индекс начального и конечного элемента в подмассиве что ли? В таком случае в начале процедуры сравниваешь X-Y с катоффом, и если X-Y меньше, то сортируешь вставками.
  #5  
Старый 13.11.2010, 20:55
Новичок

Отправить личное сообщение для JON_BOY Посмотреть профиль Найти все сообщения от JON_BOY
 
Регистрация: 11.11.2010
Сообщений: 5

Что у тебя в коде 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 ?
  #6  
Старый 13.11.2010, 22:14
гость

 
Сообщений: n/a

Цитата:
Потом, сортировка INSERT делается после завершения быстрой сортировки. внутри Qwick sort нужно выйти из рекурсии.
Можно и так. Тогда значит при входе в процедуру проверяешь, если Y-X < CUTOFF, тогда выходишь и все.
  #7  
Старый 14.11.2010, 03:55
Новичок

Отправить личное сообщение для JON_BOY Посмотреть профиль Найти все сообщения от JON_BOY
 
Регистрация: 11.11.2010
Сообщений: 5

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

 
Сообщений: n/a

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

Цитата:
Меня же просто интересует где добавляются cutоff(ы) в моем примере и все.
в самое начало
if Y-X < CUTOFF then return end if
  #9  
Старый 14.11.2010, 04:11
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Quick sort na Pascal ("special" для НУБОВ)) Dlthan Сортировка и поиск 4 01.03.2011 09:50
задача с быстрой сортировкой гость Сортировка и поиск 2 16.11.2008 21:09
pigeonhole & Counting sort wof Сортировка и поиск 1 06.04.2008 18:32
Алторитм Quick Sort гость Сортировка и поиск 1 28.02.2008 01:29
Quick Sort toto Сортировка и поиск 3 18.05.2007 08:01