Classic: Quicksort

Question:

Please implement Quicksort


Answer:

This answer below performs a Quicksort without in-place element swaps. Thus, it requires bigger memory space but results in simpler and easier-to-understand code implementation.

def quicksort(arr):
  if len(arr) <= 1:
    return arr
  n = len(arr)
  pivot = arr[random.randint(0, n-1)]
  arr_low = []
  arr_mid = []
  arr_high = []
  for i in range(n):
    if arr[i] < pivot:
      arr_low.append(arr[i])
    elif arr[i] > pivot:
      arr_high.append(arr[i])
    else:
      arr_mid.append(arr[i])
  return quicksort(arr_low) + arr_mid + quicksort(arr_high)

# call the function
input = [8, 3, 2, 8, 5, -1, 4, 6, 7, 2, 6, 4, 0, 9, 6, 5, 8]
print(quicksort(input))

Below is a code for Quicksort with in-place swapping. The code is a bit more involved than without in-place swapping (above), but it requires less memory space.

import random

def quicksort_aux(arr, low, high):
  if low >= high:
    return

  # choose a pivot randomly 
  idx_pivot = random.randint(low, high)
  pivot = arr[idx_pivot]
  idx_last_pivot = idx_pivot

  # move smaller elements to the left, larger elements to the right
  idx_border = low-1
  for i in range(low, high+1):
    # bring all elements less than or equal to pivot to the left
    if arr[i] <= pivot:
      idx_border += 1
      arr[idx_border], arr[i] = arr[i], arr[idx_border]
      # record the right-most position of the pivot element
      if arr[idx_border] == pivot:
        idx_last_pivot = idx_border

  # the border element should always be the pivot
  arr[idx_last_pivot], arr[idx_border] = arr[idx_border], arr[idx_last_pivot]
  
  # next iteration, sort the left and the right part
  quicksort_aux(arr, low, idx_border-1)
  quicksort_aux(arr, idx_border+1, high)

def quicksort(arr):
  quicksort_aux(arr, 0, len(arr)-1)
  return arr

# call the function
input = [8, 3, 2, 8, 5, -1, 4, 6, 7, 2, 6, 4, 0, 9, 6, 5, 8]
print(quicksort(input))

👍 Have fun while coding with Python!

👌 Please subscribe to receive notifications on future challenges.

💬 If you have any questions simply write a comment down below.

Leave a Comment