2

The algorithm sorts all the numbers except the first one, and sets it as last. Please help!

def bubbleSort(numbers): # Bubble Sort Algorithm
    numbers = list(numbers)
    i = 0
    j = 0
    for i in range(len(numbers)):
        for j in range(len(numbers) - i):
            if numbers[j] < numbers[j-1]: 
                       temp = numbers[j-1]
                       numbers[j-1] = numbers[j]
                       numbers[j] = temp

    print numbers
    print numbers
user970496
  • 23
  • 1
  • 1
  • 3
  • Quick note: You don't need to set `i = 0` and `j = 0` explicitly. that happens as part of the `for` loop, which says "let `i` assume the values in `range(n)` - `0,1,2,3,4...n`. – Li-aung Yip Feb 09 '12 at 02:35
  • 1
    also note that swapping two numbers can be better expressed as `a, b = b, a`, as in `numbers[j-1], numbers[j] = numbers[j], numbers[j-1]`. See http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html (required reading for all python programmers.) – Li-aung Yip Feb 09 '12 at 02:38
  • Finally, note `numbers = list(numbers)` may have strange effects when you pass in arguments that aren't a list. For example: `list("foobar") ` gives `['f', 'o', 'o', 'b', 'a', 'r']`, `list( {'key1':'value1','key2':'value2'} )` gives `['key2', 'key1']`. If you want to ensure that your function is getting a list, it's better to test the condition `type (numbers) is list`. – Li-aung Yip Feb 09 '12 at 02:52

2 Answers2

6

The problem is that sometimes [j-1] becomes negative. In python, numbers[-1] means "get the last element in numbers". Here is a fixed version:

def bubbleSort(numbers): # Bubble Sort Algorithm
    nums = list(numbers)
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if numbers[j] < numbers[i]:
                numbers[j], numbers[i] = numbers[i], numbers[j]

    print numbers

You'll notice that it is also possible to swap numbers without a temp variable in python as well

deontologician
  • 2,764
  • 1
  • 21
  • 33
  • Ah, beat me to it. To be more precise, when `j = 0` then you're comparing the first and last elements of the list. To clarify the meaning of `numbers[-1]`, try `foo = [1, 2, 3, 4]; foo[-1]; foo[-2]; foo[0:-1]`. – Li-aung Yip Feb 09 '12 at 02:44
  • is it selection sort instead of bubble sort? – Bear Feb 09 '12 at 02:51
  • @Bear, this is a slightly "optimized" bubble sort where we move along once there is no possibility of swaps any more. It still has O(n^2) time complexity however. – deontologician Feb 09 '12 at 02:57
  • No: selection sort looks for the biggest number in the unsorted part of the list, then moves it to the top of the list. Bubble sort works through the list doing swaps between adjacent values in the list. – Li-aung Yip Feb 09 '12 at 02:59
  • 1
    @habitue: "optimised bubble sort" cracks me up every time. Though for the best bubble sort possible in Python, see: http://stackoverflow.com/questions/895371/bubble-sort-homework – Li-aung Yip Feb 09 '12 at 02:59
  • I mostly changed it because I think this is a bit cleaner since we aren't doing subtraction etc in the indices – deontologician Feb 09 '12 at 03:00
  • In habitue solution ,it finds smallest in each round and move it to the left... So why it is not selection sort? Selection sort also is O(N^2) – Bear Feb 09 '12 at 11:41
  • It doesn't look for the smallest number directly and then move it to the front of the list. It does a dumb pairwise comparison like in bubblesort, the only difference being that we stop comparing to places in the list that are already sorted (which is somewhat like selection sort). – deontologician Feb 09 '12 at 14:46
0

I would not describe this as a 'Bubble sort' as it does not swap the list elements that are next to each other. Its more like a 'Selection sort' as it is looking through the list and comparing each element with the first then swapping the smallest number with the first.

It seems to be a bubble/selection mash-up.

Mr C
  • 1