Изисквания за сортиране и свойства

Памет - допълнителни разходи за памет в зависимост от размера на масива.

Стабилност - постоянното сортиране не променя относителното положение на равни елементи. Много методи (например HeapSort) разклащат масива по такъв начин, че след сортирането равни елементи да могат да преминат в съвсем различна последователност от преди.

Естественост на поведението - ефективността на метода при обработка на вече сортирани или частично сортирани данни. Естествено означава, че отчита този факт и работи по-бързо. Неестественият метод не отчита този факт или се случва дори да работи още по-зле (!).

Освен това има два вида основни сортове:

SelectSort, BubbleSort, ShellSort - не се прилага на практика.

TreeSort - сортиране на двоично дърво

Общото представяне винаги е O (nlogn).

Редовно дърво: n елемента (ключ + 2 указателя), избор с подмяна: 2n-1 елемента

Забележка.
Следователно TreeSort обикновено се използва където
конструираното дърво може успешно да се прилага за други задачи.
данните вече са вградени в „дърво“. > не е изразходван
данните могат да се четат директно в дървото. > допълнително
> памет
H например, когато поточно въвеждане от конзолата или от файл. За повече информация относно избора на сорт TreeSort вижте съответния въпрос.

Общата производителност е O (n ^ 2), но поради простотата на изпълнението на метода тя е най-бърза за малки (12-20 елемента) масиви и списъци.

Сортирането се извършва "на място", т.е. няма допълнителни режийни памет.

Забележка. Поради своите особености методът е добър за частично сортирани данни.

Цялостното представяне на Quicksort е O (nlogn) време. Случаят n ^ 2 е възможен само на теория, но вероятността за това е изключително малка. Като цяло, най-бързото сравнение се сортира за неуредени масиви с 50 или повече елемента.

Итеративната опция изисква регистрационна памет, рекурсивна - O (n).

Поведението е неестествено. Практически сортиран масив ще бъде сортиран толкова, колкото и напълно неподреден.

Хепсорт - купчина.

1,5 пъти по-бавно от бързо. Общото представяне винаги е O (nlogn).

---