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

У меня есть псевдокод для создания рекурсивной версии функции пузырьковой сортировки. Я пытался преобразовать его в рабочую функцию на 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]. Я не понимаю, что мне не хватает. Любая помощь будет оценена.


person Tanmay Gaur    schedule 01.05.2019    source источник
comment
(L[0] if type(L[0]) is list else [L[0]]) + (T[0] if type(T[0]) is list else [T[0]]) Почему вы здесь проверяете тип?   -  person rdas    schedule 01.05.2019


Ответы (1)


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

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

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

person Dawid Paluszkiewicz    schedule 01.05.2019