Как правильно написать partition?

Question

[Hazlarorn]

Вопрос следующий немогу найти нормальный источник где правильно написан код! для функции partition (в том смысле что например этот алгоритм не зависит от того способа каким выбран начальный элемент Pivot) или я чет не понимаю? Или можно другим способом написать in_place сортировку Хоара?

Comments

[Hazlarorn]

Может быть я просто не понимаю как вообще после partition должен выглядить массив. Например у Вирта в его книжке данный массив разбивается на массивы в которой один из массивов "не упорядочен" относительно pivota

Т.е. бог знает как там располагаться элементы должны относительно pivota. И то забавно что в этом разбиении в разных подмассивах (1 и 3 могут быть пивоты) а в этом смысле это не разбиение

[VoidVolker]

Hazlarorn какой именно алгоритм? И в чём именно у вас проблема? Partition переводится как раздел. И под разделом обычно понимают раздел на накопителе.

[Hazlarorn]

Добрый вечер.

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low 
    j = high 

    while True:
        i += 1
        while arr[i] < pivot:
            i += 1

        j -= 1
        while arr[j] > pivot:
            j -= 1

        if i >= j:
            return j

        arr[i], arr[j] = arr[j], arr[i]

Метод partition (он начинает зацыкливать сортировку на определенных массивах). Например [37, 100, 26, 69, 91, 78, 7, 61, 46, 11, 37]. Код не мой если что взято из интернета. Про процедуру саму partition вообще конкретно нигде не написано (толком нормальных источников нету хотя эта процедура используется например в нахождении k_той статистики). Варианты типо ограничить память на стеке вызовов не предлагать

[VoidVolker]

Hazlarorn, https://qna.habr.com/help/rules#3.8

[Hazlarorn]

VoidVolker, Можно вопрос (в качестве шутки) если я напишу код своей рукой на бумажке A4 и отправлю его в качестве изображения это будет считается нарушением правил? Например у меня нету доступа к ПК

[VoidVolker]

Hazlarorn, да, будет. Ибо без ПК вы сюда никак не зайдёте и не напишете сообщение. А раз можете зайти и написать сообщение - значит и код можете написать или скопировать и вставить. Кроме того, код/лог/ошибка картинкой - это проявление неуважения к отвечающим (как и вообще любой текст без форматирования).
Кроме того, напоминаю про необходимость чётко и однозначно сформулировать ваш вопрос. Это, между прочим, пункты 3.2 и 3.5 правил. На текущий момент совершенно не понятно в чём у вас проблема.
Как правильно задавать вопросы: bugtraq.ru/forum/faq/general/smart-questions.html

[Hazlarorn]

VoidVolker, Вы пробовали прогнать функцию написаную выше на массиве о котором я написал выше. Ну вот если нет он зацикливается я этот алгоритм который написан выше увидел при просмотре лекции по алгоритмам и структурам данных и он не работает на всех данных. И я хочу узнать как его правильно реализовать или по крайней мере где тут ошибка. Что тут непонятного?

[Hazlarorn]

VoidVolker, Спасибо вопрос закрыт. Проще самому было разобраться и выдумать этот алгоритм чем что то спрашивать. Извиняюсь за неудобства недавно тут на форуме сижу. Шутка про то что только 1 процент программистов умеет нормально писать алгоритм сортировки Хоара видимо оказалась не совсем шуткой.

[alexalexes]

Hazlarorn, вы просто не умеете готовить материал для того, чтобы обозначить проблему. Тут мало код написать, нужно еще представить пример входных данных, выходных данных, отладочного лога.
Что "беру такой массив, с помощью моей функции получаю вот такой выходной массив, а должен быть вот такой выходной". Или "не получаю выходной массив - вот отладочный лог, при сравнении i-го и j-го числа (указываю в строку лога, который выполнен текстом) выполнение кода циклится в строках k и l (указываю комментарием часть кода, который выполнен текстом)".
Отвечающий без проблем скопирует код (который не написан на A4 от руки), если у него есть подходящая среда, запустит его. И по примеру входных данных (которые тоже легко забрать, не так ли) попробует разрулить вашу проблему.

[VoidVolker]

Hazlarorn, нет, не пробовал. Ибо вместо нормального вопроса у вас поток слабосвязанных слов. Я вам уже указал на необходимость нормальной формулировки вопроса.

[Hazlarorn]

alexalexes, Проще тут вообще вопросы не задавать если каждый вопрос необходимо расщеплять до атомов может вам еще байт код привести, или вообще проанализировать зацикливание алгоритма на уровне перестановки битов? (ИРОНИЯ если что сказал же тема закрыта я все понял спасибо за ваше участие, насчет того что я неправильно сформулировал вопрос (ибо его не поняли другие) то уж извините недавно на форуме сижу и не совсем пока ознакомился с правилами постановки вопроса(уже писал выше) ).

[Hazlarorn]

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

from random import randint


def hoare_partition(in_arr, l_index, r_index):
    pivot = in_arr[(l_index+r_index)//2]
    r_pointer = r_index
    l_pointer = l_index
    while l_pointer <= r_pointer:
        while in_arr[l_pointer] < pivot:
            l_pointer += 1
        while in_arr[r_pointer] > pivot:
            r_pointer -= 1
        if l_pointer >= r_pointer:
            break
        in_arr[l_pointer], in_arr[r_pointer] = in_arr[r_pointer], in_arr[l_pointer]
        r_pointer -= 1
        l_pointer += 1

    l_pointer = 0
    r_pointer_1 = r_pointer
    while l_pointer <= r_pointer_1:
        while in_arr[l_pointer] < pivot:
            l_pointer += 1
        while in_arr[r_pointer_1] == pivot:
            r_pointer_1 -= 1
        if l_pointer >= r_pointer_1:
            break
        in_arr[l_pointer], in_arr[r_pointer_1] = in_arr[r_pointer_1], in_arr[l_pointer]
        r_pointer_1 -= 1
        l_pointer += 1

    l_pointer = r_pointer + 1
    r_pointer = len(in_arr) - 1

    while l_pointer < r_pointer:
        while in_arr[l_pointer] == pivot:
            if l_pointer + 1 == len(in_arr):
                return in_arr
            l_pointer += 1
        while in_arr[r_pointer] > pivot:
            r_pointer -= 1
        if l_pointer >= r_pointer:
            break
        in_arr[l_pointer], in_arr[r_pointer] = in_arr[r_pointer], in_arr[l_pointer]
        r_pointer -= 1
        l_pointer += 1
    print(pivot)
    return in_arr


for j in range(0, 1000):
    print("N:", j)
    a = [randint(0, 10) for i in range(0, 10)]
    print(a)
    print(hoare_partition(a, 0, len(a) - 1))

Причем данный partition работает и на рандоме (недетерминированый partition) и на определенном выборе pivota. Теперь с этим костылем можно сделать быструю сортировку так как она была изначально задумана (имхо) in_place. Спасибо всем за помощь еще раз.

[Hazlarorn]

Кому интересно окончательная версия того ответа (в некоторой реализации алгоритма так сказать что я хотел услышать от многоуважаемых партнеров Хабра)

from random import randint


def hoare_partition(in_arr, l_index, r_index):
    pivot = in_arr[randint(l_index, r_index)]
    r_pointer = r_index
    l_pointer = l_index
    while l_pointer <= r_pointer:
        while in_arr[l_pointer] < pivot:
            l_pointer += 1
        while in_arr[r_pointer] > pivot:
            r_pointer -= 1
        if l_pointer >= r_pointer:
            break
        in_arr[l_pointer], in_arr[r_pointer] = in_arr[r_pointer], in_arr[l_pointer]
        r_pointer -= 1
        l_pointer += 1

    l_pointer = 0
    r_pointer_1 = r_pointer
    while l_pointer <= r_pointer_1:
        while in_arr[l_pointer] < pivot:
            l_pointer += 1
        while in_arr[r_pointer_1] == pivot:
            r_pointer_1 -= 1
        if l_pointer >= r_pointer_1:
            break
        in_arr[l_pointer], in_arr[r_pointer_1] = in_arr[r_pointer_1], in_arr[l_pointer]
        r_pointer_1 -= 1
        l_pointer += 1

    l_pointer = r_pointer + 1
    r_pointer = len(in_arr) - 1

    while l_pointer < r_pointer:
        while in_arr[l_pointer] == pivot:
            if l_pointer + 1 == len(in_arr):
                break
            l_pointer += 1
        while in_arr[r_pointer] > pivot:
            r_pointer -= 1
        if l_pointer >= r_pointer:
            break
        in_arr[l_pointer], in_arr[r_pointer] = in_arr[r_pointer], in_arr[l_pointer]
        r_pointer -= 1
        l_pointer += 1
    i_1 = 0
    while in_arr[i_1] < pivot:
        i_1 = i_1 + 1
    i_2 = 0
    while (i_1 + i_2) < len(in_arr) and in_arr[i_1 + i_2] == pivot:
        i_2 = i_2 + 1
    return i_1, i_2


def hoare_sort(in_arr, l_index, r_index):
    if l_index >= r_index:
        return in_arr
    i_1, i_2 = hoare_partition(in_arr, l_index, r_index)
    hoare_sort(in_arr, l_index, i_1)
    hoare_sort(in_arr, (i_1 + i_2), r_index)


def main():
    for j in range(0, 1000):
        print("N:", j)
        a = [randint(0, 10) for i in range(0, 10)]
        print(a)
        hoare_sort(a, 0, len(a)-1)
        print(a)

Answer 1

[Антон Весельчак]

Классика. Pivot — обычно середина. Возвращает индекс, где массив нужно "порезать".
Не гарантирует, что pivot окажется на своём месте!

def partition(arr, low, high):
pivot = arr[(low + high) // 2]
i = low - 1
j = high + 1

while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
→ Не зависит от pivot, но работает чётко, если правильно делишь левую/правую часть в рекурсии
(quicksort(arr, low, p) и quicksort(arr, p + 1, high))

Comments

[Hazlarorn]

А через randint нельзя pivot выбирать? Обязательно по середине? Вообще если оптимум делать то пивот нужно брать медианной.

[Антон Весельчак]

Hazlarorn, Да, можно и даже нужно брать pivot через randint, если хочешь более устойчивую быструю сортировку

Пример: случайный pivot в Hoare-схеме
import random

def partition(arr, low, high):
pivot_index = random.randint(low, high)
pivot = arr[pivot_index]

i = low - 1
j = high + 1

while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]

Зачем это нужно:
pivot = arr[(low+high)//2] — норм, но может ловить худшие случаи на отсортированных массивах
randint делает поведение менее предсказуемым → средняя сложность сохраняется ближе к O(n log n)

[Hazlarorn]

Спасибо. Я так и думал

Answer 2

[Wataru]

https://en.m.wikipedia.org/wiki/Quicksort
Смотрите секцию algorithm. Там аж 2 варианта с объяснением и кодом.