Skip to content

Instantly share code, notes, and snippets.

@M0r13n
Last active June 23, 2018 15:13
Show Gist options
  • Save M0r13n/96c10f6e9ebbe855aee0064e6826d1c2 to your computer and use it in GitHub Desktop.
Save M0r13n/96c10f6e9ebbe855aee0064e6826d1c2 to your computer and use it in GitHub Desktop.
Quicksort implementation in Python
data = [1, 5, 2, 5, 3, 5, 5]
def quicksort(left, right):
if 0 > left:
raise ValueError("left border must be greater or equal zero")
if right >= len(data):
raise ValueError("right index cant be greater than length")
if left < right:
divider = divide(left, right)
quicksort(left, divider - 1)
quicksort(divider + 1, right)
def swap(i, j):
temp = data[i]
data[i] = data[j]
data[j] = temp
def divide(left, right) -> int:
i = left
j = right - 1
pivot = data[right]
while i < j:
# find an element bigger than the pivot element, starting left
while data[i] < pivot and i < right - 1:
i = i + 1
# find an element which is smaller the the pivot element, this time starting from right
while data[j] >= pivot and j > left:
j = j - 1
if i < j:
swap(i, j)
if data[i] > pivot:
# right not left
swap(i, right)
return i
quicksort(0, len(data) - 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment