Skip to content

Instantly share code, notes, and snippets.

@dtaivpp
Created January 9, 2020 14:23
Show Gist options
  • Save dtaivpp/1e23ebcb1e654a5a6fef2bcce79deb53 to your computer and use it in GitHub Desktop.
Save dtaivpp/1e23ebcb1e654a5a6fef2bcce79deb53 to your computer and use it in GitHub Desktop.
# Courtesy of https://stackabuse.com/sorting-algorithms-in-python/
def partition(nums, low, high):
# We select the middle element to be the pivot. Some implementations select
# the first element or the last element. Sometimes the median value becomes
# the pivot, or a random one. There are many more strategies that can be
# chosen or created.
pivot = nums[(low + high) // 2]
i = low - 1
j = high + 1
while True:
i += 1
while nums[i] < pivot:
i += 1
j -= 1
while nums[j] > pivot:
j -= 1
if i >= j:
return j
# If an element at i (on the left of the pivot) is larger than the
# element at j (on right right of the pivot), then swap them
nums[i], nums[j] = nums[j], nums[i]
def quick_sort(nums):
# Create a helper function that will be called recursively
def _quick_sort(items, low, high):
if low < high:
# This is the index after the pivot, where our lists are split
split_index = partition(items, low, high)
_quick_sort(items, low, split_index)
_quick_sort(items, split_index + 1, high)
_quick_sort(nums, 0, len(nums) - 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment