Python-сообщество

Понадобилось мне отсортировать обьекты, а list.sort() меня не устраивает, подскажите, код, приведенный ниже, хоть и рабочий но вызывает у меня опасения, может в нем можно что-то конструктивно подкорректировать

def swap(a, b):
    c = a
    a = b
    b = c
    return a, b

def getbest(population, metric = 0):
    sigma = max(population[:len(population) - metric])
    population[len(population)-1- metric], population[population.index(sigma)] = swap(population[len(population)-1-metric], population[population.index(sigma)])
    if metric + 1 < len(population):
        getbest(population, metric+1)
    return population

1. весь свап заменяется на
a, b = b, a

2. у вас N рекурсивных вызывов getbest внутри которых просмотр массива из ~ N/2 элементов (сначала просмотр N, затем уменьшается каждый шаг на 1, тоесть в среднем N/2) и того N*N/2 ~ O(N^2) )сложность же быстрой сортировки (тоже ркурсивный алгоритм) в среднем O(N*logN). Так что я прям не знаю чем вас не устроил стандартный сорт :)

Отредактировано (Ноя. 22, 2010 16:00:06)

Свал не уменьшится, просто пропадет 6 символов, но и на том спасибо =)

Про сложность это да, но проблема в том что мне надо написать именно такую сортировку =(

Вы помните, что максимальная глубина стека по умолчанию - 1000?
А вызов - довольно дорогая операция? В Питоне сложность кода считают именно по количеству необходимых вызовов.
Простым циклом было бы быстрее - это все же не функциональный язык программирования с tail recursion optimization.

list.sort, равно как и sorted - не подошли по объективным причинам?

population == population
Второй вариант пишется проще а работает быстрее

Нет, по субьективным, попросил друг написать пример рекурсивной функции.

За условие спасибо большое, я долго изворачивался чтоб оно работало нормально =)

Глубина стека в данном случае не важна, важна сама структура программы, вообще говоря я хотел писать это на Turbo Delphi, так как-то нагляднее выходит, но он настоял на пайтоне.

Ещё раз спасибо =)