Question: Does the choice of the pivot affect the running time of quick sort? Why or why not? It would help if you could provide examples or illustrations.
Big-O Solving (PYTHON)
Question: Does the choice of the pivot affect the running time of quick sort? Why or why not? It would help if you could provide examples or illustrations.
Given ONLY:
Quick Sort is another sorting
- A pivot element is chosen, usually the first element.
- All elements smaller than the pivot are placed to the left of the pivot. This creates 2 partitions, elements greater than the pivot and elements less than the pivot.
- The 2 partitions are sorted using Quick Sort.
Sample code in python3:
def quick_sort(arr):
def quick_sort_r(arr, start, end):
if end - start < 2:
# single element base case
return
# choose a pivot
pivot = start # you may choose other elements
store = pivot+1 # index to store less than elements
# for all elements after the pivot
for i in range(pivot+1, end):
if arr[i] < arr[pivot]:
# if element is less than pivot
arr[i], arr[store] = arr[store], arr[i] # swap
store += 1 # increment store index
# swap pivot with last element in less than partition
arr[pivot], arr[store-1] = arr[store-1], arr[pivot]
pivot = store-1 # new pivot index
# Recursive Calls
quick_sort_r(arr, start, pivot) # sort less than partition
quick_sort_r(arr, pivot+1, end) # sort greater than partition
return
quick_sort_r(arr, 0, len(arr))
Step by step
Solved in 2 steps
