Skip to main content
added 17 characters in body
Source Link
janos
  • 113.1k
  • 15
  • 154
  • 396

You have a bug

Try this:

items = [14, 3, 9, 2, 1, 5, 4, 2, 1, 3]
quicksort(items)
print(items)

It gives:

[14, 1, 1, 2, 2, 3, 3, 4, 5, 9]

In quicksort_partition, left_div = 1 looked suspicious, if I change that to left_div = 0, then it seems to be better:

[1, 1, 2, 2, 3, 3, 4, 5, 9, 14]

But not good enough. If you try with items = [14, 13, 9, 2, 1, 5, 4, 2, 1, 3] (change the first 3 to 13), you will get RuntimeError: maximum recursion depth exceeded. You need to debug this.

Naming

I propose these renames:

  • l to items
  • s to start, naturally
  • e to end, naturally
  • left_div to left, ldiv, or leave as is
  • right_div to right, rdiv, or leave as is

This is a matter of taste though. input is not a good name for l because it's too generic and says nothing about what it is, but even more importantly, a built-in function with that name exists in Python 3.

Returning a sorted list

The built-in function sorted doesn't mutate the input list, it returns a new sorted list. You edit in-place, which is space efficient, and can be acceptable. However, the fact that you don't return the list makes it slightly more tedious to test. It would be easier if the function returned the sorted list. But that's really a good option, because then users might mistakenly believe that you don't mutate input list. Mirroring sorted, a good middle ground might be adding a helper called quicksorted:

def quicksorted(items):
    newitems = items[:]
    quicksort(newitems)
    return newitems

PEP8

Since you're new to Python, let me point out PEP8, the official Python coding style guide. Your code mostly passes (with flying colors), the only violation is that you should put 2 blank lines before each function definition. Overall, you're doing great, this just FYI.

You have a bug

Try this:

items = [14, 3, 9, 2, 1, 5, 4, 2, 1, 3]
quicksort(items)
print(items)

It gives:

[14, 1, 1, 2, 2, 3, 3, 4, 5, 9]

In quicksort_partition, left_div = 1 looked suspicious, if I change that to left_div = 0, then it seems to be better:

[1, 1, 2, 2, 3, 3, 4, 5, 9, 14]

But not good enough. If you try with items = [14, 13, 9, 2, 1, 5, 4, 2, 1, 3] (change the first 3 to 13), you will get RuntimeError: maximum recursion depth exceeded. You need to debug this.

Naming

I propose these renames:

  • l to items
  • s to start, naturally
  • e to end, naturally
  • left_div to ldiv, or leave as is
  • right_div to rdiv, or leave as is

This is a matter of taste though. input is not a good name for l because it's too generic and says nothing about what it is, but even more importantly, a built-in function with that name exists in Python 3.

Returning a sorted list

The built-in function sorted doesn't mutate the input list, it returns a new sorted list. You edit in-place, which is space efficient, and can be acceptable. However, the fact that you don't return the list makes it slightly more tedious to test. It would be easier if the function returned the sorted list. But that's really a good option, because then users might mistakenly believe that you don't mutate input list. Mirroring sorted, a good middle ground might be adding a helper called quicksorted:

def quicksorted(items):
    newitems = items[:]
    quicksort(newitems)
    return newitems

PEP8

Since you're new to Python, let me point out PEP8, the official Python coding style guide. Your code mostly passes (with flying colors), the only violation is that you should put 2 blank lines before each function definition. Overall, you're doing great, this just FYI.

You have a bug

Try this:

items = [14, 3, 9, 2, 1, 5, 4, 2, 1, 3]
quicksort(items)
print(items)

It gives:

[14, 1, 1, 2, 2, 3, 3, 4, 5, 9]

In quicksort_partition, left_div = 1 looked suspicious, if I change that to left_div = 0, then it seems to be better:

[1, 1, 2, 2, 3, 3, 4, 5, 9, 14]

But not good enough. If you try with items = [14, 13, 9, 2, 1, 5, 4, 2, 1, 3] (change the first 3 to 13), you will get RuntimeError: maximum recursion depth exceeded. You need to debug this.

Naming

I propose these renames:

  • l to items
  • s to start, naturally
  • e to end, naturally
  • left_div to left, ldiv, or leave as is
  • right_div to right, rdiv, or leave as is

This is a matter of taste though. input is not a good name for l because it's too generic and says nothing about what it is, but even more importantly, a built-in function with that name exists in Python 3.

Returning a sorted list

The built-in function sorted doesn't mutate the input list, it returns a new sorted list. You edit in-place, which is space efficient, and can be acceptable. However, the fact that you don't return the list makes it slightly more tedious to test. It would be easier if the function returned the sorted list. But that's really a good option, because then users might mistakenly believe that you don't mutate input list. Mirroring sorted, a good middle ground might be adding a helper called quicksorted:

def quicksorted(items):
    newitems = items[:]
    quicksort(newitems)
    return newitems

PEP8

Since you're new to Python, let me point out PEP8, the official Python coding style guide. Your code mostly passes (with flying colors), the only violation is that you should put 2 blank lines before each function definition. Overall, you're doing great, this just FYI.

Source Link
janos
  • 113.1k
  • 15
  • 154
  • 396

You have a bug

Try this:

items = [14, 3, 9, 2, 1, 5, 4, 2, 1, 3]
quicksort(items)
print(items)

It gives:

[14, 1, 1, 2, 2, 3, 3, 4, 5, 9]

In quicksort_partition, left_div = 1 looked suspicious, if I change that to left_div = 0, then it seems to be better:

[1, 1, 2, 2, 3, 3, 4, 5, 9, 14]

But not good enough. If you try with items = [14, 13, 9, 2, 1, 5, 4, 2, 1, 3] (change the first 3 to 13), you will get RuntimeError: maximum recursion depth exceeded. You need to debug this.

Naming

I propose these renames:

  • l to items
  • s to start, naturally
  • e to end, naturally
  • left_div to ldiv, or leave as is
  • right_div to rdiv, or leave as is

This is a matter of taste though. input is not a good name for l because it's too generic and says nothing about what it is, but even more importantly, a built-in function with that name exists in Python 3.

Returning a sorted list

The built-in function sorted doesn't mutate the input list, it returns a new sorted list. You edit in-place, which is space efficient, and can be acceptable. However, the fact that you don't return the list makes it slightly more tedious to test. It would be easier if the function returned the sorted list. But that's really a good option, because then users might mistakenly believe that you don't mutate input list. Mirroring sorted, a good middle ground might be adding a helper called quicksorted:

def quicksorted(items):
    newitems = items[:]
    quicksort(newitems)
    return newitems

PEP8

Since you're new to Python, let me point out PEP8, the official Python coding style guide. Your code mostly passes (with flying colors), the only violation is that you should put 2 blank lines before each function definition. Overall, you're doing great, this just FYI.