быстрая сортировка

[.Amira.]

Добрый вечер!

Задание:
Вводится нечётное количество разных натуральных чисел. Определить, какое число после сортировки будет находится по середине.

По идее задание решено, единственное НО - при проверке решение не укладывается во времени (1с). Сортировка методом пузыря слишком медленна, quicksort (он же метод хоара) даёт ещё худший результат (ещё большее кол-во проверок не успевает выполнится).

Кто-нибудь знает ещё более эффективный метод сортировки?? Хотя бы идеи какие-нибудь???

@темы: Pascal, Алгоритм

Comments

[Южени]

is.ifmo.ru/vis/ordstat/doc.pdf вот такое есть...
Ну и ещё на Гугле про это есть Ссылка

То?
Вообще это не на сортировку, а на поиск k-той порядковой статистики (=

[.Amira.]

Южени

Вообще это не на сортировку, а на поиск k-той порядковой статистики (=

вполне возможно, но т.к. задание для школьников на олимпиаде оно сформулировано примерно так (мой перевод). я к сожалению на олимпиады не ходила)

читаю ваш материал, пока что процесс представляется долгим.... но нужно попробовать.

[.Amira.]

в любом случае, если есть ещё идеи - делитесь, мне их очень не хватает)

[Южени]

.Amira. ну по сути нужно найти только медиану, т.е. сортировать и не надо) Алгоритмы не очень сложные - надо просто на листочке с цифирками сразу читать и выполнять действия Быстрее будет...

[.Amira.]

ну по сути нужно найти только медиану, т.е. сортировать и не надо)

по идее так оно и есть спасибо, сейчас на листочке поколдую

[[revolver]]

учите алгоритмы.
Пузырёк работает за O(N^2)
QSort за O(N log N)
А k-ая статистика -- модифицированный пузырёк, за O(N)

[.Amira.]

учите алгоритмы.

и к чему это было сказано? дабы потешить своё самолюбие? теоретическое время я уже давно прочитала. на практике задание не укладывается во времени, потому я и спросила совета.

с к-той статистикой я до этого не встречалась. пробую на бумаге применить, что-то не получается. то ли я не поняла, то ли как. может, чуть позже напишу, что у меня получается. вдруг я где ошибаюсь.

[[revolver]]

.Amira., учите алгоритмы было написано к бреду, который говорит, что qsort медленее чем пузырёк) Самолюбия нет и не было.
Чтобы найти k-ую статистику нужно исправить правильный qsort -- просто идти в нужную половину. Т.е. КАК ВЫ УЖЕ ЗНАЕТЕ по бумажке, в qsort мы сортируем левую и правую часть массива. так вот, для статистики мы идём только в ту часть, в которой находится k.

На С/С++ это выглядед примерно так:

int k_stat(int l, int r){
  int i = l; int j = r; int x = a[l+(rand()*rand())%(r-l+1)];
  do{
    while(a[i] < x) i++;
    while(a[j] > x) j--;
    if(i <= j){
      swap(a[i++], a[j--]);
    }
  }while(i <= j);
  if(l == k && r == k || j < k && k < i) return a[k];
  if(l <= j && k <= j) return k_stat(l, j);
  if(i <= r && k >= i) return k_stat(i, r);
}

где число k--паблик (глобальная) переменная текущего класса.
Как ВЫ видите, поразительное сходство с QSort

К вопросу о методах сортировки. есть много квадратичных методов, один из них пузырёк. ещё есть много извращений, но на массивах больше 1000 элементов это всё втормаживает как мама дорогая.

Нормальных сортировок есть тоже много, а именно ТРИ.
Быстрая, Слиянием и Пирамидальная. Все они работают за O(N log N)

Быстрая, она же QSort, она быстрая) и в написании и в понимании и в том, что она работает с текущим массивом) Но она -- неустойчивая и иногда делает лишние инверсии.

Слияние -- самая быстрая из всех сортировок и устойчивая. Именно ей нужно сортировать большие и ОЧЕНЬ большие массивы. Для сортировки использует дополнительный массив. Идея проста: разбить массив на два, отсортировать каждый рекурсивно, а далее слить два отсортированных массива. Является устойчивой сортировкой.

Наконец, пирамидальная -- аналог сортировки методом прямого выбора, где на каждом шаге извлекается самый маленький (большой) элемент и ставится следующим в отсортированный массив. Но поиск самого маленького / большого элемента мы делаем с помощью специальной структуры данных -- куча (heap). Является самой медленной из линейно-логарифмических сортировок. На больших и оооочень больших массивах втормаживает очень сильно.

А вообще, отсылаю ВАС к оооооочень хорошей литературе, как то:
Ахо, Хопхрофт, Ульман "Структуры данных и что то там ещё, название не помню"
Кормен, Лейзерсон, Ривест "Алгоритмы. Построение и анализ"

[https]

Кнут, Морис, Пратт "Алгоритмы. Построение и анализ"

Возможно, Кормен, Лейзерсон, Ривест, Штайн "Алгоритмы: построение и анализ"? Или трёхтомник Кнута? Вместе Кнут Морис и Прат упоминаются разве что в связи с алгоритмом поиска подстрок =)

А вообще, .Amira., если вы взялись за решение олимпиадных задачек, почитать что-то фундаментальное по алгоритмам и стуктурам данных - действительно полезный совет.

QSort кстати имеет время работы O(N lg N) в наиболее вероятном случае, в наихудшем он вполне себе может работать за O(N^2). Да и действенны такие оценки только для больших размеров данных, для маленьких всякие константы, неявно входящие в выражение, могут запросто перекрывать выгоду в количестве сравнений

[.Amira.]

[revolver] спасибо большое за код и за литературу) только с работой разберусь, сразу начну пробовать

https

если вы взялись за решение олимпиадных задачек

ох, если бы это было добровольно.... если бы)

[.Amira.]

а говоря о быстродействии пузырька и qsort.... наверное меня не совсем поняли...

я их не сравниваю теоретически. а смотрю результаты тестов. пузырёк успевает выполнить 9 тестов из 10 : www.lio.lv/olimps/rezultati_sikak.php?queue_id=...

qsort только 6/10 : www.lio.lv/olimps/rezultati_sikak.php?queue_id=...

но в любом случае к-тая статистика ещё не испробована)

[https]

.Amira. Ну, я имела в виду, что в том, что на небольшом размере данных пузырёк отрабатывае быстрее, чем qsort нет ничего "бредового"; тем не менее на больших массивах qsort всё-таки эффективнее.
По теме вопроса мне действительно нечего сказать, ссори что так просто встряла. Но по-моему это действительно задача скорее на порядковую статистику, чем на сортировку.

[[revolver]]

.Amira., так не может быть. просто физически. пузырёк медленнее в разы! в отношение линии к логарифму.
https, сорри. забыл я уже как эти книги называются. Да. Либо 3-х томник Кнута либо Кормен) Признаю, не прав)

[Южени]

А на массивах какой длины тестировали?

[[revolver]]

Южени, да блин. Я не знаю где там кто что тестировал, но это бред! на массивах больше тысячи уже всё сыпется

[Южени]

[revolver] но на маленьких-то массивах (допустим, десяток) пузырёк вполне может работать быстрее логарифма Вспомним графики параболы и логарифма

[[revolver]]

Южени, если вы сможете замерить разницу времени на 10 числах между пузырьком и кусортом -- я вам выдам грамоту))))

[Южени]

[revolver] Ну тогда прям не знаю... Разве что на избыточность кода списать

[https]

[revolver] Действительно существуют перестановки, на которых быстрая сортировка работает не лучше пузырька - если на каждой итерации массив разбивается на два подмассива "один элемент" - "все остальные" - время работы алгоритма в таком случае будет O(N^2). Про это написано везде, где более-менее подробно рассматривается оценка времени работы qsort. С учётом того что тестирование проводилось в специальной системе - некоторые тесты там вполне могут быть "подлыми", а не случайносформированными.

[[revolver]]

https, оооо ГОСПАДИ!!!! Неужели вы думаете, что я этого не знаю? Существуют! Но если написать QSort не div 2 для выбора опорного элемента, а rand(), то всё будет в шоколаде. Написано блин. Теория есть теория. Не надо меня злить, пожалуйста))) Я начинаю нервничать)))

[[revolver]]

P.S. Коллега написал:

xxx (23:37:43 6/10/2010)
Тестов, которые его валят, нет (с) инженер Росгидромета Олейников И. С. - можешь так и написать.

[https]

Цитата из вышеупомянутого Кормена и Ко:
"Мак-Илрой (McIlroy) [216] показал, как создать конструкцию, позволяющую получить массив, при обработке которого практически каждая реализация быстрой сортировки будет выполняться в течении времени O(n^2). Если реализация рандомизированная, то данная конструкция может создать данный массив на основании информации о том, каким образом в рандомизированном алгоритме быстрой сортировки осуществляется случайный выбор".

Ссылка на статью McIlroy

"The general method works against any implementation of quicksort – even a randomizing one – that satisfies
certain very mild and realistic assumptions."

Мне кажется, слова этих товарищей можно считать не менее компетентными, чем г-на Олейникова.

[[revolver]]

Вы просто немного путаете смысл слов, которые пишут эти товарищи. Они -- великие учёные, которые показывают, что и как можно сломать с помощью МАТЕМАТИЧЕСКИХ методов. На практике же, никогда такое не наблюдается. Посчитайте вероятность того, что на массиве из N элементов на каждом шаге вы будете попадать в САМЫЙ максимум

А теперь ещё и представьте, что ВАМ нужно протестировать программу по ЧЁРНОМУ ящику Изложите суть?))) Нужно составить int вариантов для randseed * количество вариантов сгенерировать случайное число тестов. =)

[https]

Я уже запуталась, о чём мы спорим.
1. Если о том что лучше использовать быструю сортировку, чем пузырьковую, в том числе и для поиска порядковой статистики - с этим я спорить не стану.

2. Если о том, что реализованный автором обсуждения qsort (по-видимому не рандомизированный) на некоторых тестах даёт большее время, чем пузырёк - то по-моему, мы выяснили, что нерандомизированному алгоритму просто подставить "плохие" данные.

4.Если о том, что существуют перестановки, на которых даже рандомизированный qsort будет иметь скорость работы O(N*N) - то в смысле их существования, а не нахождения он ничем не лучше нерандомизированного.

5.Так что по-видимому спор сводится к тому, можно ли, если задаться целью, создать такие данные, что рандомизированная qsort с неизвестным seed'ом проиграет пузырьку. Я не математик и не специалист в теории алгоритмов, да и досконально изучать 5-ти страничный научный текст на английском мне не хочется. Но то что моя дурная голова не может составить такую схему, не является доказательством, что это невозможно в принципе. В то же время, могу привести доводы, которые свидетельствуют, что это возможно:

а) Едва ли необходимо попадать на каждой итерации в самый максимум: если алгоритм работает в среднем случае за О(N logN), а в наихудшем - О(N*N), значит есть и "плохие" случаи, быстродействие в которых к О(N*N) близко, хоть и не равняется.

б) Подойдут не только максимумы, но и минимумы - они тоже приводят к отщеплению одного элемента. Причём в любых комбинациях на последовательных итерациях.

в) Если в массиве много одинаковых чисел, равномерно расположеных по всему массиву (а rand возвращает равномерно распределённые числа, если я не ошибаюсь), то вероятность попадания в "максимум-минимум" для данного подмассива велика.

г) randseed будет ограничиваться отнудь не MAXINT, а размером массива, который у нас вроде бы значительно меньше.

д) Накладные расходы у алгоритмов разные. Если взять полностью отсортированный массив - пузырёк не будет выполнять никаких операций, кроме сравнений; qsort - на каждом разбиении два раза себя рекурсивно вызывать, что является куда более дорогостоящей операцией. Плюс вызов генератора случайных чисел.
На массиве, состоящем из сплошь одинаковых элементов пузырёк так же не будет ничего переставлять, а быстрая сортировка - постоянно менять местами элементы (если неравество строгое) или разбиваться на пресловутые подмасивы "все-один" (если нестрогое).

Сформулировать математически обоснованную схему, балансирующую и сводящую всё воедино, мне навыков и времени не хватает; что, однако, не является доказательством несуществования такого алгоритма. Если только вы не можете, тоже формально, обосновать, что это невозможно в принципе.

[[revolver]]

ОМГ.... Ладно. PEACE ж)
Вот щас уже я просто не хочу спорить.

[https]

[revolver] Ок-ок-ок. PEACE =)