Попытка сделать рекурсивную версию функции пузырьковой сортировки из псевдокода - PullRequest
Новая
       35

Попытка сделать рекурсивную версию функции пузырьковой сортировки из псевдокода

0 голосов
/ 01 мая 2019

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

def bsort(L):
   if the length of L is less than or equal to 1:
        return L
   else:
        bubble sort the tail of L (all elements of L except the first) to get a sorted list called T
        if the head (first element) of L is less than or equal to  the head T:
              return  a list formed by joining the ehad of L with T
         else:
              combine the head of L and the tail of T to get a list called P
              bubble sort P to get a list called Q
              return a list formed by joining the head of T with Q

Вот код, который я сделал с помощью псевдокода 

def bsort(L):
    if len(L)<=1:
        return L
    else:
        T= bsort(L[1:])
        if L[0]<=T[0]:
            return (L[0] if type(L[0]) is list else [L[0]]) + (T[0] if type(T[0]) is list else [T[0]])
        else:
            P= (L[0] if type(L[0]) is list else [L[0]]) + (T[1:] if type(T[1:]) is list else [T[1:]])
            Q= bsort(P)
            return (T[0] if type(T[0]) is list else [T[0]]) + (Q if type(Q) is list else [Q])

Когда я использую список типа [14,26,83,17,87] и использую bsort([14,26,83,17,87]) Функция это дает вывод [14,17].Не должно ли вывод для этой функции сортировки пузырьков быть [14, 17, 26, 83, 87].Я не понимаю, чего мне не хватает.Любая помощь будет оценена.

1 Ответ

0 голосов
/ 01 мая 2019

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

def bsort(L):
if len(L) <= 1:
    return L
else:
    T = bsort(L[1:])
    if L[0] <= T[0]:
        return [L[0]] + T
    else:
        P = [L[0]] + T[1:]
        Q = bsort(P)
        return [T[0]] + Q

Ошибка была возвращена после того, как если L [0] <= T [0]: условие, потому что вы возвращаете 2 головы списка вместо головы и хвоста. </p>

...