Метод разбиения

Question

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

partition(A, p)  
A: array of size n, p: integer s.t. 0 <= p < n

 1. swap(A[0],A[p])

 2. i <- 1, j <- n − 1

 3. while i < j do

 4.   while A[i] <= A[0] and i < n do

 5.     i <- i + 1

 6.   while A[j] > A[0] and j > 0 do

 7.     j <- j − 1

 8.   if i < j then

 9.     swap(A[i], A[j])

10. swap(A[0], A[j])

11. return j

Answer 1

Алгоритм, который реализует этот псевдокод, - это фаза разделения алгоритма быстрой сортировки . Он упорядочит массив так, что все значения, меньшие или равные A[p], будут слева, а все большие значения - справа. Он возвращает индекс j, который является последним индексом левой стороны, для которого A[j] равен A[p].

Если вы не знакомы с быстрой сортировкой, то намерены использовать этот алгоритм разбиения, чтобы разбить массив на «маленькие» и «большие» части и рекурсивно отсортировать каждую часть. Поскольку маленькие были расположены раньше больших в массиве, массив сортируется. Если p выбран так, что A[p] находится близко к середине значений в A, это очень быстрый метод сортировки.