я изобрел новый алгоритм сортировки? или это так же, как быстрая сортировка - PullRequest
Новая
       23

я изобрел новый алгоритм сортировки? или это так же, как быстрая сортировка

3 голосов
/ 20 марта 2012

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

Однако я слышал, что быстрая сортировка - это O (N ^ 2) худший случай;Я думаю, что мой алгоритм должен быть только O (NLogN) в худшем случае.

Это то же самое, что и быстрая сортировка?

Алгоритм работает путем обмена значениями, так что все значения, меньшие, чем медиана, перемещаются влево от массива.Затем он работает рекурсивно на каждой стороне.

Алгоритм начинается с i = 0, j = n-1

i и j движутся навстречу друг другу со списком [i] и списком [j]меняя местами при необходимости.

Вот код для первой итерации перед рекурсией: 

_list = [1,-4,2,-5,3,-6]

def in_place(_list,i,j,median):
    while i<j:
        a,b = _list[i],_list[j]
        if (a<median and b>=median):
            i+=1
            j-=1
        elif (a>=median and b<median):
            _list[i],_list[j]=b,a
            i+=1
            j-=1
        elif a<median:
            i+=1
        else:
            j-=1
    print "changed to ", _list



def get_median(_list):
    #approximate median in O(N) with O(1) space
    return -4

median = get_median(_list)
in_place(_list,0,len(_list)-1,median)

"""
changed1 to  [-6, -5, 2, -4, 3, 1]
"""

Ответы [ 2 ]

4 голосов
/ 20 марта 2012

http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting

И наоборот, когда мы знаем, что доступен алгоритм выбора O (n) в худшем случае, мы можем использовать его для нахождения идеального центра (медианы) на каждом шагебыстрая сортировка, производящая вариант с O (n log n) наихудшего случая.В практических реализациях, однако, этот вариант в среднем значительно медленнее.

Другой вариант - выбрать Медиану Медиан в качестве основного элемента вместо самой медианы для разделения элементов.Поддерживая асимптотически оптимальную сложность времени выполнения O (n log n) (предотвращая наихудшие разделы), она также значительно быстрее, чем вариант, который выбирает медиану как опорную.

2 голосов
/ 20 марта 2012

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

Извините, что украл ваш огонь, но я боюсь, что код, который вы показываете, кажется Quicksort, и не только это, но код, возможно, страдает от некоторых ошибок.

Рассмотрим случай сортировки списка идентичных элементов. Ваш метод _in_place, который в Quicksort обычно называется разделением, не будет корректно перемещать какие-либо элементы, но в конце j и i отражают список, имеющий только один раздел, содержащий весь список , в этом случае вы бы снова повторить на весь список навсегда. Я полагаю, что, как уже упоминалось, вы ничего не возвращаете из этого или, кажется, на самом деле полностью сортируете где угодно, поэтому мне остается только догадываться, как это будет использовано.

Боюсь, что использование настоящей медианы для быстрой сортировки - это не только, возможно, довольно медленная стратегия в среднем случае, она также не избегает наихудшего случая O (n ^ 2), опять же, список идентичных элементов обеспечит такой худший случай. Тем не менее, я думаю, что трехсторонняя сортировка Quicksort с таким алгоритмом выбора медианы гарантирует время O (n * log n). Тем не менее, это известная опция для выбора сводной области, а не новый алгоритм.

Короче говоря, это, кажется, неполная и, возможно, глючная быстрая сортировка, и без трехстороннего разбиения использование медианы не гарантирует вам O (n * log n). Однако я чувствую, что это хорошая вещь и стоит поздравить вас с тем, что вы сами подумали об идее использования медианы - даже если об этом раньше думали другие.

...