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.
