Печать промежуточного списка Quicksort Python

Подсказка для this Проблема HackerRank меня озадачила. Это, по сути, реализация quicksort, но в качестве исключения вы должны печатать промежуточный (или полураздельный) «исходный» массив в каждой своей итерации.Печать промежуточного списка Quicksort Python

Мой рабочий код без печати промежуточных продуктов. Он работает так, как ожидалось.

def quicksort(array): 

    if len(array) > 1: 
     left = 0 
     right = len(array)-2 
     pivot = len(array)-1 
     while left <= right: 
      while array[left] < array[pivot]: 
       left +=1 
      while array[right] > array[pivot]: 
       right -= 1 
      if left <= right: 
       array[left], array[right] = array[right], array[left] 
       left += 1 
       right -=1 
     array[left], array[pivot] = array[pivot], array[left] 

     return quicksort(array[0:left]) + quicksort(array[left::]) 
    else: 
     # return single element arrays 
     return array

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

def quicksort2(array, start=0, end=None): 
    size = len(array[start:end]) 


    if size > 1: 
     left = start 
     right = len(array[start:end])-2 
     pivot = len(array[start:end])-1 
     print("Print") 
     print("left: {}\nright: {}\npivot: {}".format(left, right, pivot)) 
     while left <= right: 
      while array[left] < array[pivot]: 
       left +=1 
      while array[right] > array[pivot]: 
       right -= 1 
      if left <= right: 
       array[left], array[right] = array[right], array[left] 
       left += 1 
       right -=1 
     array[left], array[pivot] = array[pivot], array[left] 
     print(array) 
     print("the end is {}".format(end)) 

     size = len(array[0:left]) # 3 

     return quicksort2(array, start=0, end=left) + quicksort2(array, start=left, end=left+(size-len(array))) 
    else: 
     # return single element arrays 
     return array 



if __name__ == '__main__': 
    size = int(input()) # size is 7 
    arr = [int(i) for i in input().split()] 
    print(quicksort2(arr, start=0, end=size))

Однако теперь список не полностью отсортирован по второй половине входного списка, так что я уверен, что это что-то делать с параметром ключевого слова конца, который передается в нижней части определения quicksort2.

источник

2015-06-01 trendsetter37

Выяснено, что я делаю неправильно. Мне действительно нужно было использовать Lomuto Partitioning method, чтобы удовлетворить требованиям операторов печати.

Код для всех, кто ищет для этого в будущем

def partition(array, lo, hi): 
    pivot_index = hi 
    pivot_value = array[pivot_index] 
    store_index = lo 

    for i in range(lo, hi): 
     if array[i] <= pivot_value: 
      array[i], array[store_index] = array[store_index], array[i] 
      store_index += 1 
    array[pivot_index], array[store_index] = array[store_index], array[pivot_index] 
    return store_index 


def quicksort(array, lo, hi): 
    if lo < hi: 
     p = partition(array, lo, hi) 
     print(' '.join([str(i) for i in array])) 
     quicksort(array, lo, p-1) 
     quicksort(array, p+1, hi) 

if __name__ == '__main__': 
    size = int(input()) 
    ar = [int(i) for i in input().split()] 
    quicksort(ar, 0, size-1)

источник

2015-06-03 11:01:21 trendsetter37

Печать промежуточного списка Quicksort Python

ответ

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