Quicksort

Быстрая сортировка(std sort)

p

p p

                p (pivot)

<p<p<p

p>p>p Пусть выбран p. Как построить разбиение? Метод 1. (С доп. памятью) - исх. массив а C - результат i p а) for (i = 1…n) Стабильная. if (a < i) < p) c.push_back(a(i)) б) for (i = 1…n) ai = p в) for (i = 1…n) ai > p pppp r r l l c for (I = 1…n) Не стабильная. if (a(i) < p): c (l) = a (i), ++ l if (a(i) > p): c (r) = a (i), -- r Метод 2. i = 1, i = n while (i < j): while (i < j && a(i) p) ++i; while (i < j && a(j) p) -- j; if (i < j) swap (a(i), a(j)), ++i, -- j; swap (a(micl), a(j)); нач. позиция p (в исх. массиве) i и j находят разделение p и p 1) Произвольный детерм. выбор ( mid = 1 / micl = n / …) В худшем случае может работать 2) Выбор случайного p. Теорема (б/д). В среднем quick sort со случайным выбором p работает за