Yet another post for the crawlers to better index my site for algorithms and as a repository for Python code. The quick sort algorithm is well explained in the topmost Google search result for ‘*Quick Sort Python Code’*, but the code is unnecessarily convoluted. Instead, go with the code below.

In it, I assume the **pivot** to be the *first element*. You can easily add a function to randomize selection of the pivot. Choosing a random pivot minimizes the chance that you will encounter worst-case O(n^{2}) performance. Always choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data.

def quicksort(x): | |

if len(x) == 1 or len(x) == 0: | |

return x | |

else: | |

pivot = x[0] | |

i = 0 | |

for j in range(len(x)-1): | |

if x[j+1] < pivot: | |

x[j+1],x[i+1] = x[i+1], x[j+1] | |

i += 1 | |

x[0],x[i] = x[i],x[0] | |

first_part = quicksort(x[:i]) | |

second_part = quicksort(x[i+1:]) | |

first_part.append(x[i]) | |

return first_part + second_part | |

alist = [54,26,93,17,77,31,44,55,20] | |

quicksort(alist) | |

print(alist) |

*Also read:*

Computing Work Done (Total Pivot Comparisons) by Quick Sort

Karatsuba Multiplication Algorithm – Python Code

Merge Sort

Hi, there is a bug in your code. When I use list = [18, 16, 17] to test you code, it returns [17, 16, 18].

LikeLike

Very very useful

Code is very easy to understand

Thank you

LikeLike

[…] Quick Sort Python Code Computing Work Done (Total Pivot Comparisons) by Quick […]

LikeLike

it doesn’t actually fully sort the list. output is:

[20, 26, 17, 31, 44, 54, 77, 55, 93]

LikeLike

Replace the ending with below to have it print correctly.:

alist = [54,26,93,17,77,31,44,55,20]

alist = quickSort(alist)

print alist

LikeLike

still did not work for me.

23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19 returns

‘ 1’, ‘ 11’, ‘ 14’, ‘ 15’, ‘ 17’, ‘ 19’, ‘ 27’, ‘ 29’, ‘ 31’, ‘ 37’, ‘ 4’, ‘ 43’, ‘ 49’, ‘ 56’, ‘ 64’, ‘ 78’, ‘ 91’, ‘ 99′, ’23’

LikeLike