Метод перегородки

Question

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

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

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

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