0

I'm writing in python and I thought I might try to use recursion to create a bubble sort. My idea is that, since the rightmost element is always sorted after every iteration (list[-1]), I add that element to another call of bubblesort for the rest of my elements (bubbleSort(list[:-1])). Here is my code:

def bubbleSort(list):
sorted = True
i = 0
if len(list) <= 1:
    return list

while i < len(list) - 1:
    if list[i] > list[i+1]:
        temp = list[i+1]
        list[i+1] = list[i]
        list[i] = temp
        sorted = False
    i = i + 1

if sorted:
    return list
else:
    endElement = list[-1]
    return bubbleSort(list[:-1]) + [endElement]

However, it only ever returns the first iteration of the sort, despite it running through every iteration (I used print inside of the code to see if it was running). The recursion is necessary: I know how to do it without it. It's just the recursion part that messes up anyways.

Julian E.
  • 4,687
  • 6
  • 32
  • 49
Graham Buceta
  • 1
  • Please format you code properly. – utkbansal Dec 05 '15 at 18:29
  • Possible duplicate of [Bubble Sort Homework](http://stackoverflow.com/questions/895371/bubble-sort-homework) – Achayan Dec 05 '15 at 18:34
  • As a separate note, your code is expensive, since it is creating a new list in every recursive step. Consider passing the full list every time along with the ending index of the sublist you need to sort, like `bubbleSort(listToSort, subListIndex)`. Then, in each recursive step, you simply call `bubbleSort(listToSort, subListIndex-1)`. This will also allow you to simplify your base case check. – ethan.roday Dec 05 '15 at 18:44

2 Answers2

0

Your intuition is correct. In fact, your code works for me (once the method contents are indented): http://codepad.org/ILCH1k2z

Depending on your particular installation of Python, you may be running into issues due to your variable name. In Python, list is a reserved word (it is the constructor for lists). In general, it is not considered good form to use a reserved word as a variable name. Try renaming your variable and see if your code runs correctly.

ethan.roday
  • 2,485
  • 1
  • 23
  • 27
0

python programs are structured by indentation, not by parenthesis like c-like languages. i think this is the problem with your code.

try to indent it like this

#!/usr/env/python

def bubble(lst):
    sorted = True
    for i in range(len(lst) - 1):
        if lst[i] > lst[i + 1]:
            temp = lst[i]
            lst[i] = lst[i + 1]
            lst[i + 1] = temp
            sorted = False
    if sorted:
        return lst
    else:
        return bubble(lst[:-1]) + [lst[-1]]

also you shouldn't use reserved words like list for variable names.

the test if the list has 1 or less elements is also unnecessary, because it wouldn't enter the loop.

linluk
  • 1,650
  • 16
  • 33