Quicksort Python

Question

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

def quicksort(array, left, right): 
    if left < right: 
     pivot = partition(array, left, right) 
     quicksort(array, left, pivot - 1) 
     quicksort(array, pivot + 1, right) 
     return array 

def partition(array, left, right): #left and right are indices 
    #pick the pivot as the middle element 
    pivot = array[round((left + right)/2)] 
    while left < right: 
     while array[left] < pivot: 
      left += 1 
     while array[right] > pivot: 
      right -= 1 
    if left < right: 
     # swap the 2 elements 
     array[left], array[right] = array[right], array[left] 
     left += 1 
     right -= 1 

    # swap the pivot and the last element (where the 2 pointers meet each other) 
    array[left], array[array.index(pivot)] = array[array.index(pivot)], array[left] 
    return left 

так, когда

print(quicksort([4, 6, 8, 1, 3], 0, 4)) 

результат

[3, 4, 6, 1, 8] 

Answer 1

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

Защиту раздела (массив, L, R): #left и вправо являются индексами #pick шарнира в качестве среднего элемента м = круглый ((L + R)/2) массива [л], массив [ м] = массив [м], массив [л] = поворота массива [л] держатели #place я = L + 1 J = г в то время как я < = J: в то время как массив [J]> ось: # do, тогда как массив [j] больше, чем pivot
j = j - 1 while i < = j и array [i] < pivot: #do в то время как массив [i] меньше, чем точка поворота
I + = 1 , если я < = J: массив [I], массив [J] = массив [J], массив [I] I + = 1 J - = 1

array[l], array[j] = array[j], array[l] # swap the pivot and last elements 
return j 

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

Окончательный ответ: снова

def partition(array, l, r): #left and right are indices 
    #pick the pivot as the middle element 
    m = round((l + r)/2)' 
    array[l], array[m] = array[m], array[l] #move pivot to right side 
    pivot = array[l] 
    #place holders 
    i = l + 1 
    j = r 
    while i <= j: 
     while array[j] > pivot: #do while array[j] is greater than pivot 
      j = j - 1 
     while i <= j and array[i] < pivot: #do while array[i] is less than pivot 
      i += 1 
     if i <= j: 
      array[i], array[j] = array[j], array[i] 
      i += 1 
      j -= 1 

    array[l], array[j] = array[j], array[l] # if swap the pivot and last element 
    return j return partition