Quick sort shitz

Такаааааа ;-) Значи, имам си един масив от някакви обекти, и искам да сортирам този масив по дадено пропърти от обектите (всички обекти в масива са от един тип). За целта използвам Array.Sort(), който от своя страна използвал QuickSort за да сортира или поне така пише в MSDN. Не в важно защо използвам обикновени масиви, а не ArrayList или друга колекция (Btw ArrayList.Sort е същото като Array.Sort() само дето е за инстанция...)
Ей това "нещо" го подавам на Sort за да може да сортира обектите правилно и той си ги сортира:

public class Comparer : IComparer
{
private PropertyInfo _property;
private bool _sortOrder;
public Comparer(Type type, string propertyName, bool Ascending)
{
this._property = type.GetProperty(propertyName);
this._sortOrder = Ascending;
}

public int Compare(object x, object y)
{
if (this._property == null)
{
return 0;
}
object valueX = this._property.GetValue(x, new object[]{});
object valueY = this._property.GetValue(y, new object[]{});

IComparable cmp = valueX as IComparable;
if (cmp == null)
{
return 0;
}

return this._sortOrder ? cmp.CompareTo(valueY) : -cmp.CompareTo(valueY);
}
}

проблема е, че искам понякога да не се сортират ;-) Но викам всеки път Sort. За да не се сортира просто подавам празен стринг за propertyName в конструктора и всичко би трябвало да е ОК, защото тогава Compare() връща 0, което би трябвало да значи, че елементите са еднакви, т.е. не би трябвало да се разместват, но явно не е точно така... Оказва се, че първата половина на масива е преместена накрая, т.е. масива ми се е разместил.

Та аз си оправих проблема, като сложих още една проверка и не всеки път викам метода за сортиране на масива.
Има ли някой идея ЗАЩО се размества масива, въпреки че явно Array.Sort() смята, че елементите са еднакви?

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

Че защо си си въобразил, че някой ти гарантира еднакжите елементи да не са разместени? За тази цел в STL си има stable_sort, чиято имплементация е малко по-сложна от тази на обикновенния сорт, но гарантира това, което ти искаш.
Не знам обаче в .NET -а да има такова нещо.

Нали алгоритмите за сортиране се делят на стабилни и нестабилни - такива, които не разместват равните елементи, и такива, които разместват. Предполагам бързото сортиране е от вторите.

--
"Agile is a mindset, not a set of practices, rules, or tools."
Tom Poppendieck

Мда, явно е така, но щеше да бъде удобно някой да беше написал, че не се гарантира положението на еднаквите елементи... А може и аз да не съм го видял ;-) Поне за мен е логично еднаквите елементи да си седят на местата, а не да си ги сменят...

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

и после се програмира. Ти сигурно искаш някой да напише и че 2+2 е 4. Пише го, прочети където искаш за QuickSort и ще разбереш, че не запазва наредбата на еднаквите ключове, а при обратно сортирани елементи се изражда в квадратичен. Т.е. Ако имаш ascending и descending не е подходящ. Предполагам, че и това не знаеш та се надявам да съм бил полезен.


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

Ами точно този урок ми се стори излишен и не го научих ;-) Сега сериозно - не го знаех, но пък наблюденията ми показват, че си работи съвсем добре със ascending/descending, поне по начина, по който е направено в случая ;-)

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

Ми то еднаквите елементи си стоят на същото място,
само дето ти ту ги считаш за еднакви, ту за различни

Със същия успех, но с малко по-добър константен фактор ще ти работи всеки елементарен квадратичен алгоритъм. Просто елементите са ти малко и не усещаш проблема. А ако разбираш повечко ще обърнеш реда на елементите без да сортираш. В краен случай ако трябва сортиране един InsertSort ще работи почти линейно на 'почти сортирани' данни.


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

За целта трябва аз да си напиша сортиращия метод, което не е зле, но след като има готов, защо да правя нов?

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

>>Т.е. Ако имаш ascending и descending не е подходящ

ЛОЛ. А какъв друг сорт освен ascending и descending мога да имам? Аз лично се сещам само за ascending и descending сорт и щом QuickSort не е подходящ, то тогава пичовете дето са писали .НЕТ-а са някви "дето не са ходили на училище", че да направят дефоултния сорт QuickSort.

Е може поне да им пратиш мейла си на пичовете от Майкрософт да се консултират с тебе при следващата версия на .НЕТ-а, че нещо явно сериозно са се объркали.

public static void sort(Object[] a, Comparator c)

Sorts the specified array of objects according to the order induced by the specified comparator. All elements in the array must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the array).

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance.

Parameters:
a - the array to be sorted.
c - the comparator to determine the order of the array. A null value indicates that the elements' natural ordering should be used.

Throws:

ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.

See Also:

Comparator


j2sdk1.4.2, Copy+Paste technology®


Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

В нормална ситуация бих само те напсувал, ама понеже съм на 4 водки ще ти обясня да се образоваш малко. Майкрософт не са измислили математиката, тя си съществува. Независимо от хората. До сега не е измислено по-добро сортиране от QuickSort и това никой не го отрича. Но то си има недостатъци. Това също никой не го отрича. Те са точно 2.5:
1. Не запазва реда на еднаквите ключове.
2. Изражда се при обратна сортировка.
2.5. Следствие от 2 - съществува реална ситуация, която е доста естествена, а преебава здраво алгоритъма. Само да поясня - и за други алгоритми са измислени лоши случаи, но те не са реални. Т.е. могат да се случат само ако ги нагласиш.
Ти за кое точно се смееш - че който е написал .net е реализирал QuickSort, или не вярваш на това което ти казвам?!? Ако ти си ламер, сигурен съм че пичовете от Майкросогт не са. И не смятам, че заради такива елементарни познания биха ми се зарадвали много. Иначе с удоволствие бих се включил в екипа им.


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

> пичовете дето са писали .НЕТ-а
"Pichove" e demode. Veche se kazva "top-hora".

Kakvi tropanici na kakvi horA tuka e klub programisti aloo

До сега не е измислено по-добро сортиране от QuickSort и това никой не го отрича.

Е тука може да се спори, в зависимост от бирите. Средната му сложност може и да е най-добрата в най-общия случай, но:

1. Worst-case сложността му си е квадратична.

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

Иначе си прав, че трябва да се ходи на училище, преди да се ползва QuickSort. Btw, чудно къде е Гюро да ни обясни пак как няма нужда да учим алгоритми, щото то в .NET фреймуърка си има Sort()

Btw, чудно къде е Гюро да ни обясни пак как няма нужда да учим алгоритми, щото то в .NET фреймуърка си има Sort()

Това не се иска за сертификациране за .НЕТ-спешълист оф тхе иеар и за това е irrelevant.

А и сега - съгласете се, че сложността на QuickSort вълнува само разни леймъри - истинските девелопери не падат по-ниско от Dataset

Ммммммммм, Java rules ;-) От утре сменям платформата и този път ще е завинаги... ;-)))

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

„I„x MSDN-a:
...
This method uses the QuickSort algorithm. This is an O(n ^2) operation, where n is the number of elements to sort, with an average of ѓЖ(n log n).

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.
...

btw. „N„u „ѓ„„„u „Ѓ„‚„p„r„y „x„p „ѓ„|„Ђ„w„~„Ђ„ѓ„„„p „~„p qsort-„p „y„}„p „„„u„‡„~„y„{„y „{„Ђ„y„„„Ђ „s„p„‚„p„~„„„y„‚„p„„ ѓЖ(n log n) „t„Ђ„‚„y „y „r „~„p„z-„|„Ђ„Љ„y„‘ „ѓ„|„…„‰„p„z. „L„Ђ„Љ„Ђ„„„Ђ „u „‰„u „ѓ„p „ѓ „Ѓ„Ђ-„s„Ђ„|„‘„}„p „{„Ђ„~„ѓ„„„p„~„„„p. „D„Ђ „{„Ђ„|„{„Ђ„„„Ђ „ѓ„Њ„} „x„p„Ѓ„Ђ„x„~„p„„ „~„p„z-„t„Ђ„q„‚„y„„„u „Ѓ„Ђ„ѓ„„„y„w„u„~„y„‘ „ѓ„p „ѓ „ѓ„|„Ђ„w„~„Ђ„„ 3 n log n, „~„Ђ „x„p „‚„u„p„|„y„x„p„€„y„‘„„„p „y„} „ѓ„u „y„ѓ„{„p „t„Ђ„ѓ„„„p „‰„u„„„u„~„u . „D„‚„…„s „u „r„Њ„Ѓ„‚„Ђ„ѓ„p „‰„u M$ „~„‘„}„p„„ „y„„„u„‚„u„ѓ „t„p „‚„u„p„|„y„x„y„‚„p„„ „Ѓ„Ђ-„ѓ„|„Ђ„w„~„y „p„|„s„Ђ„‚„y„„„}„y („~„u„x„~„p„} „x„p„‹„Ђ).

Posledniqt abzac neshto ne e multiplatforming, ne se chete.

Мечтата е мисъл, мисълта е идея, всяка идея се реализира. Аз не мечтая, а реализирам идеите си.

Много поучаваш приятел. "Ходи на училище" ще казват само тия, дето преди това са минали детската градина.

>>1. Не запазва реда на еднаквите ключове.
Нито един сорт не запазва реда на ключовете, било те еднакви или различни. Нали трябва да ги премести, за да ги сортира? Най-добре пиши на английски, а не като преподавател от клона на ТУ в Харманли. Искаш да кажеш, че сорта е stable.

>>2. Изражда се при обратна сортировка.
Worst-case scenario, O(n*n). Това искаш да кажеш ?

>>2.5. Следствие от 2 - съществува реална ситуация, която е доста >>естествена, а преебава здраво алгоритъма.
Коя е тая толкова естествена ситуация? До сортирам постоянно вече обратно сортирана структура от данни?

Ами ако тая естествена ситуация се случва постоянно, както твърдиш, защо не си reverse-неш структурата за скромното време O(n) и после да минеш с QuickSort от О(nlogn), за сумарно O(n+ logn), което за по-големи стойности на n клони към О(nlogn) ? Не че има смисъл, хората затова и са ти казали, че в общия случай QuickSort e О(nlogn), ама щом толкова те притеснява този "мега вероятен случай" ...

И това не е най-лошия случай дори. Може да падне тухла в/у компютъра докато сортира - тогава ако искаш ползвай технология от Вогоните и пак няма да ти помогне.