Sorting Quick3

[rojerbaum]

Здравствуйте!
Не могу разобраться с составлением функции, которая будет принимать на вход указатель на статический массив с элементами типа int и проводить в нем сортировку по этому алгоритму.
Просьба местных гуру составить, либо разжевать способ реализации данного алгоритма на языке Си.
Заранее спасибо.

[rojerbaum]

вверх
прошу помощи

[Granus]

По ссылке ведь даже реализация написана. Что именно у Вас не получается?

[Murashov]

на сколько я знаю её смысл состоит в том, чтобы делить массив на 2(3) части (на 3 потому что больше среднего числа, меньше и равного ему) и менять местами числа. разделять части на части, части частей на части и т.д. пока не отсортирует

вот нашёл на вики даже наглядный пример

закодить пока не пробовал, надо будет как-нибудь...

думаю можно с помощью рекурсии оформить

[rojerbaum]

да, реализация там описана, но я решительно не могу ее понять.

# choose pivot
swap a[n,rand(1,n)]

меняются местами последний и рандомный элемент массива? смысл?

# 3-way partition
i = 1, k = 1, p = n
while i < p,
if a[i] < a[n], swap a[i++,k++]
else if a[i] == a[n], swap a[i,--p]
else i++
end
→ invariant: a[p..n] all equal
→ invariant: a[1..k-1] < a[p..n] < a[k..p-1]

здесь не совсем понимаю при каких условиях что меняется...

[Kukurudza]

че за люди пошли
https://www.google.ru/#hl=ru&newwind...w=1760&bih=840