Квиксорт — разлика између измена
Садржај обрисан Садржај додат
м Бот Мења: no:Sorteringsalgoritme#Quick sort |
м Граматичке и(ли) правописне грешке |
||
Ред 18:
=== Опширнији опис ===
Алгоритам на почетку добије низ и леву и десну границу интервала кога треба сортирати. За ове границе мора да важи да лева има мањи индекс од десне, иначе се алгоритам прекида. Унутар тог интервала, алгоритам изабере тзв. пивот-елемент, који се обично узима са његове средине или њене околине. Потом, алгоритам замењује места пивот-елемента и последњег елемента у низу (из разлога који ће бити споменут касније) и сортирање може да почне. Алгоритам пролази кроз цео задат интервал и све елементе који су мањи или једнаки том пивот-елементу слаже на прво, друго, треће итд. место у низу.
По завршетку овог процеса, пивот-елемент са краја интервала се ставља на крај овог низа, иза задњег постављеног елемента. Тај елемент је сад на свом месту и неће бити више потребе премештати га. Због овога је на почетку и био премештен на крај — да се током размештања не би морало пратити његово место у низу те да премештање на крај буде лакше. Дати интервал је сад овим пивот-елементом подељен на два подинтервала од којих леви садржи све елементе њему мање или једнаке, а десни све оне који су од њега већи. Алгоритам се сада понавља за ова два новонастала интервала.
| |||