Сортиране по директен избор
Сортирането с директен избор е в известен смисъл обратното на сортирането с директно включване.
При директно включване, на всяка стъпка, само един следващ елемент от входната последователност и всички елементи от готовата последователност се считат за намиране на мястото на включване.
При директен избор за търсене на един елемент с най-малък ключ се преглеждат всички елементи от входната последователност и намереният елемент се поставя като следващ елемент в края на готовата последователност.
Методът за сортиране с директен избор се основава на следните правила:
- Избира се елементът с най-малък ключ.
- Разменя се с първия елементa0.
- След това тези операции се повтарят с останалитеn-1 елементи,n-2 елементи и така нататък, докато остане най-големият елемент.
Анализ на алгоритъма чрез директен избор
Броят на ключовите сравнения C не зависи от реда на ключовете:
C=1/2(n 2 -n).
Броят на пермутациите е минимален
Mmin=3(n-1)
при първоначално поръчани ключове и макс
Mmax= n2/4 +3(n-1),
ако първоначално ключовете са в обратен ред.
Средни трансфери
Mav≈n(ln n + g),
къдетоg = 0,577216... е константата на Ойлер.
Обобщение: Като цяло сортирането с директен избор се предпочита пред алгоритъма за директно включване, но ако ключовете са подредени или почти подредени в началото, директното включване ще остане малко по-бързо.