Турнир сорт

Из Википедије, слободне енциклопедије
Турнир сорт
Намена Алгоритам за сортирање
Структура података низ
Временска компл. O(n log n)

Турнир сорт је алгоритам за сортирање. Унапређује наивно сортирање селекцијом користећи приоритетни ред ради налажења следећег елемента у низу. Сортирањем селекцијом, потребно је O(n) операција како би се одабрао идући од n елемената; у турнир сортирању, потребно је O(log n) операција (након креирања почетног турнира у времену O(n)). Турнир сорт је варијација хипсорта.

Честа имплементација[уреди]

Сортирања селекцијом за замену турнира се користе како би се прикупила почетна стања за спољашње алгоритме за сортирање. Концептуално, спољашња датотека се чита, и њени елементи се стављају у приоритетни ред док се он не напуни. Онда се минимални елемент извади из реда и означи се као део првог круга. Следећи улазни елемент се чита и ставља у ред, и минимум се поново бира и ставља у круг. Ако је нови елемент, који се ставља у ред, мањи од последњег елемента који је додат у круг, онда се вредност сортирања елемента увећа, тако да он буде део следећег круга. У просеку, круг ће бити 100% дужи него капацитет приоритетног реда.[1]

Турнир[уреди]

Име долази из његове сличности са елиминационим турниром у коме више играча или тимова играју у "један на један" мечевима где губитник испада из турнира, а победник иде у следећи круг. Процес се наставља до финалног меча, који одлучује победника турнира. Турнир даје најбољег играча, али играч који је изгубио у финалу не мора бити други најбољи, већ може бити и лошији од других играча које је победник избацио из турнира.

Референце[уреди]

  1. ^ Donald Knuth, The Art of Computer Programming, Sorting and Searching, Volume 3, 1973. The "snowplow" argument.