Return to Answer

• This isn’t a bubble sort. In bubble sort, you compare adjacent pairs of items until the list is sorted – here, you’re doing pairwise comparisons of non-adjacent elements. If I try with a list of length 4, and print the values of i and j, this is what I get:

   0 0
   0 1
   0 2
   1 0
   1 1
   1 2
   2 0
   2 1
   2 2
   3 0
   3 1
   3 2
  

  I would expect to see 0 1, 1 2 and 2 3. This is actually much more inefficient than bubble sort.

• If you want to iterate over multiple ranges like this, you’d be better off using something like the itertools module, than constructing multiple nested loops. This products the same iterations of i and j as your code:

   for i, j in itertools.product(range(len(items)), range(len(items) - 1)):
   print(i, j)
  

• This isn’t a bubble sort. In bubble sort, you compare adjacent pairs of items until the list is sorted – here, you’re doing pairwise comparisons of non-adjacent elements. If I try with a list of length 4, and print the values of i and j, this is what I get:

   0 0
   0 1
   0 2
   1 0
   1 1
   1 2
   2 0
   2 1
   2 2
   3 0
   3 1
   3 2
  

  I would expect to see 0 1, 1 2 and 2 3. This is actually much more inefficient than bubble sort.

• If you want to iterate over multiple ranges like this, you’d be better off using something like the itertools module, than constructing multiple nested loops. This products the same iterations of i and j as your code:

   for i, j in itertools.product(range(len(items)), range(len(items) - 1)):
   print(i, j)
  

Selection sort

• This is a slightly unusual implementation of selection sort – you’re building up the sorted subset from the right (with the largest elements sorted first) rather than the left. Usually, I see selection sort as building up a sorted subset with the smallest elements first. But this seems to work, so it’s fine.

• Personally I’m not a fan of range() with three parts, especially if the step is –1, i.e. range(len(items)-1,0,-1). I think they’re a little cramped, and prefer to use reversed(range(len(items)-1)) – I find that easier to read.

• Small thing, but make sure you add a space after commas. Good for readability.

Insertion sort

• It would be helpful to have some docstrings on your utility functions. It’s not obvious to me what find_the_place() or shift_things_from() are supposed to do, which makes it hard to tell if they’re doing that correctly.

• You can improve the for loop in find_the_place with enumerate():

   for idx, item in enumerate(till):
   if v < item:
   return idx
  

I’ll do a proper review later, but for now, I’ll just point out that there seem to be some bugs in your implementation:

>>> from sorting import *
>>> bubblesort([1, 0])
[1, 0]
>>> quicksort([0, 0, 0, 1, 0, 0, 0])
[0, 0, 0, 0, 0, 1, 0]
>>> heapsort([1, 0, 1, 1, 0, 0])
[0, 0, 1, 0, 1, 1]

I used Hypothesis to create some randomised list of integers, throw them into your function, and compare them to the builtin sorted(). I couldn’t get any crashers, but those results seem a bit off to me.

I’ll do a proper review later, but for now, I’ll just point out that there seem to be some bugs in your implementation:

>>> from sorting import *
>>> bubblesort([1, 0])
[1, 0]
>>> quicksort([0, 0, 0, 1, 0, 0, 0])
[0, 0, 0, 0, 0, 1, 0]
>>> heapsort([1, 0, 1, 1, 0, 0])
[0, 0, 1, 0, 1, 1]

I used Hypothesis to create some randomised list of integers, throw them into your function, and compare them to the builtin sorted(). I couldn’t get any crashers, but those results seem a bit off to me.

The lesson here: you need more than a few simple test cases. Only having a few tests means that you’re more likely to miss edge cases, and have subtle bugs in your code.

Bubble sort

As above, this doesn’t actually work. There are a couple of things wrong here:

• This isn’t a bubble sort. In bubble sort, you compare adjacent pairs of items until the list is sorted – here, you’re doing pairwise comparisons of non-adjacent elements. If I try with a list of length 4, and print the values of i and j, this is what I get:

   0 0
   0 1
   0 2
   1 0
   1 1
   1 2
   2 0
   2 1
   2 2
   3 0
   3 1
   3 2
  

  I would expect to see 0 1, 1 2 and 2 3. This is actually much more inefficient than bubble sort.

• If you want to iterate over multiple ranges like this, you’d be better off using something like the itertools module , than constructing multiple nested loops. This products the same iterations of i and j as your code:

   for i, j in itertools.product(range(len(items)), range(len(items) - 1)):
   print(i, j)