Быстрая сортировка по набору длины 2

Question

При быстрой сортировке набора данных список разбивается на части и является рекурсивным, поскольку решение вызывает себя в меньших списках. Я занимался быстрой сортировкой по алгоритму, но подсписок длины 2 - камень в моей обуви, я не могу его решить. Первоначальный список был:

2  0  1  7  4  3  5  6

Пивот находится на 2, слева на 0, справа на 6, я начинаю. Левый движется по 7, 7> = 2. Право движется вниз до 1, 1 <= 2. Левый и правый пересеклись. Как я понимаю, теперь право становится точкой разделения, и формируются два новых списка. </p>

2  0      1      7  4  3  5  6

Как видите, первый список, 2 и 0, состоит из 2 элементов. Таким образом, 2 - это опорная точка, а 0 - и левая, и правая. Левый не движется, правый движется к 2, 2 <= 2. Левый и правый пересеклись, поэтому p заменяет R, а L - новый список. Но это оставляет 2 и 0 несортированными. </p>

Где я иду не так?

Answer 1

Проблема в вашем случае возникла из-за того, что я не перемещаю шарнир в его отсортированном месте.После разбиения с помощью pivot 2 ваш массив должен выглядеть следующим образом:

0  1  2  7  4  3  5  6
      ^

Давайте пройдем процедуру partition с входным массивом 13 19 9 5 12 8 7 4 21 2 6 11.И давайте выберем 11 в качестве стержня.

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

Код выглядит так:

A is array left..right
pivot = A[right]
i = left - 1                 // the one before the first bigger than the pivot
for j = left to right - 1
    if A[j] <= pivot
        i = i + 1
        swap A[i] with A[j]
swap A[i+1] with A[right]    // put pivot at its place, i + 1 - is the index to split on

И пример:

    13  19   9   5  12   8   7   4  21   2   6  11 

    13  19   9   5  12   8   7   4  21   2   6  11   13 > 11, skip
^^  ||

    13  19   9   5  12   8   7   4  21   2   6  11   19 > 11, skip
^^      ||

     9  19  13   5  12   8   7   4  21   2   6  11    9 < 11, swap
    ^^      ||

     9   5  13  19  12   8   7   4  21   2   6  11    5 < 11, swap
        ^^      ||

     9   5  13  19  12   8   7   4  21   2   6  11   12 > 11, skip
        ^^          ||

     9   5   8  19  12  13   7   4  21   2   6  11    8 < 11, swap
            ^^          ||

     9   5   8   7  12  13  19   4  21   2   6  11    7 < 11, swap
                ^^          ||

     9   5   8   7   4  13  19  12  21   2   6  11    4 < 11, swap
                    ^^          ||

     9   5   8   7   4  13  19  12  21   2   6  11   21 > 11, skip
                    ^^              ||

Вы можете продолжить себя?