Сложность в реализации QuickSort

Я пытаюсь реализовать quicksort как 2 дня (похоже, мои навыки программирования становятся ржавыми). Я не знаю, что я делаю неправильно. Я собирался сдаться, поэтому я подумал, что должен проконсультироваться с дискуссионным форумом.Сложность в реализации QuickSort

вот код, который я пытаюсь реализовать в python. Но это не дает желаемого результата. Любой может указать, что я делаю неправильно?

def QuickSort(A,p,r): 

if p < r: 
    pivotIndex = Partition(A,p,r) 
    QuickSort(A,p,pivotIndex-1) 
    QuickSort(A,pivotIndex+1,r) 
    return A 
def Partition(A,p,r): 

m = A[p] 
i = p+1 
for j in range(p+1 , r): 
    if A[j] < m: 
     A[j] , A[i] = A[i] , A[j] 
     i+=1 
A[p], A[i-1] = A[i-1] , A[p] 
return i-1

Выход для тестового входа является:

>>>QuickSort([9,8,7,6,5,4,3,2,1],0,9) 
[1, 3, 5, 6, 7, 4, 8, 2, 9]

Я буду очень благодарен, если кто-нибудь мне помочь в осуществлении этого.

С уважением

источник

2013-07-15 InspiredCoder

'QuickSort (A [0: pivotIndex])' уже будет исключить 'pivotIndex', поэтому я не Думаю, вам нужно вычесть 1. –

Я сделал это, но все равно получаю тот же результат:/ – InspiredCoder

Ваша однобуквенная схема именования излишне затруднительна для расшифровки. Если бы вы использовали более информативные имена, людям было бы легче помочь. – user2357112

Я выяснил ответ. Оказалось, что я проходил один-менее методу QuickSort

def QuickSort(A,p,r): 
    if r-p <= 1: return 
    pivotIndex = Partition(A,p,r) 
    QuickSort(A,p,pivotIndex) 
    QuickSort(A,pivotIndex+1,r) 
    return A 
def Partition(A,p,r): 

    m = A[p] 
    i = p+1 

    for j in range(p+1 , r): 
     if A[j] < m: 
      A[j] , A[i] = A[i] , A[j] 
     i= i + 1 
    A[p], A[i-1] = A[i-1] , A[p] 
    return i-1

Это правильная реализация

источник

2013-07-15 18:33:42 InspiredCoder

Когда я запускаю это, я получаю [8, 7, 6, 5, 4, 3, 2, 1, 9] ... – Ma3x

Я получаю это [1, 2, 3, 4, 5, 6, 7, 8 , 9] – InspiredCoder

Хорошо, если это сработает для вас :) – Ma3x

Нарезка не возвращает вид первоначального списка; он выводит новый список из старого списка. Это означает, что рекурсивные вызовы QuickSort не меняют исходный список.

источник

2013-07-15 17:22:04 user2357112

umm, что я должен изменить в коде? – InspiredCoder

У вас есть функции для индексирования, чтобы сортировать, а не нарезать список. – user2357112

На самом деле проблема в том, что я хочу сделать это так же. Можете ли вы предложить любой другой способ, чтобы я мог передать только один аргумент функции (это список)? – InspiredCoder

Вы можете попробовать эту реализацию в одной строке кода:

def QuickSort(list): 
    return [] if list==[] else QuickSort([x for x in list[1:] if x < list[0]]) + [list[0]] + QuickSort([x for x in list[1:] if x >= list[0]]) 

print QuickSort([9,8,7,6,5,4,3,2,1])

источник

2013-07-15 17:25:47 amatellanes

Этот алгоритм имеет среднюю сложность O (n^2), в то время как Quicksort имеет O (n log n). Кроме того, накладные расходы памяти составляют O (n) вместо O (log n). – cababunga

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

def Partition(A,p,r): 

    m = A[p] 
    A[p], A[r] = A[r], A[p] 
    i = p 
    for j in range(p, r): 
    if A[j] < m: 
     A[j] , A[i] = A[i] , A[j] 
     i+=1 
    A[r], A[i] = A[i] , A[r] 
    return i

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

EDIT: Извините, что я забыл добавить звонок, а затем QuickSort ([9,8,7,6,5,4,3,2,1], 0,), так как индексы включены сейчас ,

источник

2013-07-15 18:33:36 Ma3x

Сложность в реализации QuickSort

ответ

Смежные вопросы