Какова связь между «сортировкой массива только с двумя различными элементами» и быстрой сортировкой

Question

Я учусь быстрой сортировке из книги Седжвика.Одна из его задач - это

. Напишите программу, которая сортирует массив, который, как известно, содержит только два различных значения ключа.
Просмотр решения

Мне кажется, я понимаю решение.Это работает в O (N).Однако я не понимаю связь между этим и быстрой сортировкой?Я не вижу никакого разделения, как в быстрой сортировке.Все, что здесь делается, - депонировать меньшие и большие элементы за соответствующими границами, на которые указывают lt и gt.

Answer 1

Решение аналогично быстрой сортировке за один проход.

Быстрая сортировка псевдокода:

1. Check stopping condition
2. Pick one number called pivot
3. Move smaller or equal elements than pivot on left part of array
4. Move greater elements than pivot on right part of array
5. Quicksort left part
6. Quicksort right part

Там, где вы ищите душу, то же самое, что и quicsort, кроме 1,5,6

1. Pick one number called pivot
2. Move smaller or equal elements than pivot on left part of array
3. Move greater elements than pivot on right part of array