DjangoBB LoFi version

Полная версия: Quick sort. Рекурсивный вызов для множеств больше и меньше медианы.

Начало » Python для новичков » Quick sort. Рекурсивный вызов для множеств больше и меньше медианы.

sergey.odessa.niceplace

Окт. 27, 2011 14:19:47

Всем привет) Буду очень признателен, если у кого-то есть свободное время обратить внимание на мой пост и помочь советом.

Столкнулся с проблемой во время кодирования алгоритма быстрой сортировки на Python. Массив делится на множества меньше медианы и больше медианы, после прохождения циклов. Далее, вызываю рекурсивно метод для множеств меньше и больше медианы. Алгоритм до конца не отрабатывает. Я думаю это из-за того, что при вызове рекурсии возвращается новый список, после среза mas, а не изменятся текущий.
Как рекурсивно можно вызвать метод для меньшей и большей части списка еще? думал преобразовать строку в список, но это не есть рационально. Помогите, советом. Спасибо, если что =)

Код:

def sort_quick(mas):
    l = 0                                   # минималный индекс
    r = len(mas) - 1                   # максимальный индекс
    m = round((r + l)/2)            # выбор медианны
    while l <= r:
        while mas[l] < mas[m]:
            l += 1
        while mas[r] > mas[m]:
            r -= 1
        [mas[l], mas[r]] = [mas[r], mas[l]]
        l += 1
        r -= 1
    if len(mas[0:m]) > 1:
        sort_quick(mas[0:m])
    if len(mas[m+1:len(mas)]) > 1:
        sort_quick(mas[m+1:len(mas)])

    return mas

Enchantner

Окт. 27, 2011 14:25:35

sergey.odessa.niceplace
а что мешает после рекурсивного вызова склеивать отсортированные части обратно?

sergey.odessa.niceplace

Окт. 27, 2011 14:35:25

спасибо. попробую сейчас сделать =)

Enchantner
sergey.odessa.niceplace
а что мешает после рекурсивного вызова склеивать отсортированные части обратно?

sergey.odessa.niceplace

Окт. 27, 2011 18:01:17

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

if len(mas[0:m]) > 1:
        sort_quick(mas[0:m])
    if len(mas[m+1:len(mas)]) > 1:
        sort_quick(mas[m+1:len(mas)])

sergey.odessa.niceplace
спасибо. попробую сейчас сделать =)
Enchantner
sergey.odessa.niceplace
а что мешает после рекурсивного вызова склеивать отсортированные части обратно?

Окт. 27, 2011 22:04:44

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

while l <= r:
        while mas[l] < mas[m]:
            l += 1
        while mas[r] > mas[m]:
            r -= 1
        [mas[l], mas[r]] = [mas[r], mas[l]]
        l += 1
        r -= 1

не приводят к желаемому эффекту. Части не содержат большие и меньшие значения в результате.
Это легко проверить поставив после внешнего цикла print m, l, r, mas, mas

Кроме того у вас слишком много лишних вычислений. Например len(mas) используется в четырех местах вместо одного.

pyuser

Окт. 28, 2011 03:33:16

И похоже алгоритм не совсем правильный. здесь посмотрите

sergey.odessa.niceplace

Окт. 28, 2011 11:36:15

type(round(7/2))
<class 'int'>

. По-моему с индексом r все нормально.

Ed
Во-первых round возвращает float, что не может быть индексом в списке.
Во-вторых вот эти ваши манипуляции
while l <= r:
        while mas[l] < mas[m]:
            l += 1
        while mas[r] > mas[m]:
            r -= 1
        [mas[l], mas[r]] = [mas[r], mas[l]]
        l += 1
        r -= 1
не приводят к желаемому эффекту. Части не содержат большие и меньшие значения в результате.
Это легко проверить поставив после внешнего цикла print m, l, r, mas, mas

Кроме того у вас слишком много лишних вычислений. Например len(mas) используется в четырех местах вместо одного.

Окт. 28, 2011 12:23:17

С индексом r все будет нормально по-любому, поскольку базой может быть любой элемент сортируемой последовательности. Можете взять первый элемент, например. r = 0. Никакого round не нужно будет.
Вот почему я про float написал:

$ python test.py 
Traceback (most recent call last):
  File "test.py", line 23, in <module>
    print sort_quick([7,2,9,3,6,1,0])
  File "test.py", line 9, in sort_quick
    while mas[l] < mas[m]:
TypeError: list indices must be integers, not float

И поэтому: http://docs.python.org/library/functions.html?highlight=round#round
И поэтому:

> python -c 'print type(round(7/2))'
<type 'float'>

Если же вам нужно, чтобы ваш код работал только под python 3, то так бы и написали.

sergey.odessa.niceplace

Окт. 28, 2011 13:44:03

ок)понял, надо было мне указать, что я на python 3 делаю) спасибо за помощь всем)) буду стараться все-же закончить и довести до ума таким способом как сделал я))