Я получаю другие результаты быстрой сортировки из решения

Question

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

Я выбираю пивот из медианы ETC (позиции 0,4 и 9) и выбираю E. Этот разворот меняется на последнюю позицию 9 и дает:

0123456789
CLECTRONIE

Я увеличиваю i с C слева и уменьшаю j с I справа и, в конечном итоге, меняю местами 1 (L) и 4 (C), получая

0123456789
CCELTRONIE

Продолжая увеличивать и уменьшать i и j соответственно, в конечном итоге пересечение с i в позиции 3, L, и это меняет местами с шарниром в позиции 9, давая:

0123456789
CCEETRONIL

Теперь, когда шарнир находится в положении 3, я думал, что раздел будет

CCE |E| TRONIL

но у меня есть решение:

Quicksort ELECTRONIC
choose pivot: median(E,T,C)=E
partition using E: ECC|E|LTRONI
...

Я понимаю, что буквы в Sl и Sr одинаковы, но я думаю, что порядок важен. Может кто-нибудь определить, где я ошибся, или как решение получает это состояние, пожалуйста? Все ценится.

Answer 1

Ваш раздел достигает главной цели - левая часть содержит меньшие (или равные) элементы, правая часть содержит большие элементы. Раздел закончен. задача (для текущего этапа) успешно завершено.

Порядок элементов в этих частях зависит от реализации раздела (существуют разные схемы) и не влияет на правильность и скорость сортировки.