Quick sort shitz

Освен това - quicksort има О(n*logn) expected time и O(n^2) worst.
Докато при merge (това в Java) имаш worst O(n*logn).

1. Бъркаш ред с място. Повече няма да коментирам.
2. Искам да кажа точно каквото съм казал : Пише го, прочети където искаш за QuickSort и ще разбереш, че не запазва наредбата на еднаквите ключове, а при обратно сортирани елементи се изражда в квадратичен - ( цитат ) . По-точно е. Аз говоря български.
3. А ако разбираш повечко ще обърнеш реда на елементите без да сортираш. В краен случай ако трябва сортиране един InsertSort ще работи почти линейно на 'почти сортирани' данни.
- (пак цитат) - както виждаш предложил съм му по-добро решение, защото QuickSort няма best case scenario, а InsertSort е тъкмо за случая. Да не говорим, че е и списък та няма да мести елементи.
За това че не трябва да обиждам си прав, ама ставам дружелюбен към петата водка чак.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Пише го, прочети където искаш за QuickSort и ще разбереш, че не запазва наредбата на еднаквите ключове, а при обратно сортирани елементи се изражда в квадратичен

Е аре ся... кой е луд да избира винаги първия елемент за pivot У наше село избираме или средния или медианата на някои три, или правим нещо като IntroSort, или направо праскаме std::sort.

Освен това - quicksort има О(n*logn) expected time и O(n^2) worst.
Докато при merge (това в Java) имаш worst O(n*logn).

А memory requirements-ите? А? А скритата константа? И що mergesort, а не heapsort?

Нищо лично, просто ме хвана яд че се заяждаш за един от малкото смислени и добре формулирани въпроси. Пича беше даже пейстнал нелош код и добре беше обяснил какво не му е ясно - и то по проблем, който е сравнително интересен. Някои хора не знаят какво е stable/unstable sort, но това не значи че ако ти го знаеш си по-добър от тях - и особено не значи че трябва да се заяждаш с "трябва да се ходи на училище..."

А иначе за сортирането има доста неща освен worst-case scenario - константа, дали сортира in-place (в същата структура като QuickSort или отделя нова памет) и доста други такива детайли, така че аз лично бих се доверил на избора на .НЕТ тийма и не бих го оспорвал.

HeapSort не е стабилен. MergeSort иска log n за стека ( също като QuickSort ) и си се прави без проблем на място.
Разбира се, че ще избереш средния - това е най-бързо, но пак е n^2. В случая само MergeSort ще свърши работа ( или направо std::stable_sort :-)


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

При обратна сортировка ако не взимаш първия елемент си е прекрасноO(n*log(n)) . Закърнял ми е мозъка - от лятото не съм правил нищо алгоритмично. Иначе най-добре си остава да обърнеш масива и да пуснеш InsertSort, но едва ли е нужно.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Ако не ти е проблем добави някакви уникални ID-та и си сортирай по тях като искаш елементите да са сортирани в първоначалния ред. Няма проблем с обратната сортировака при QuickSort, объркал съм се.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Всичко е оправено отдавна (още когато написах първия постинг) и работи добре ;-)

The road to hell is full of good intentions...