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))
![](/static/compass_v2/shared-icons/check-mark.png)
Step by step
Solved in 2 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![C++ Programming: From Problem Analysis to Program…](https://www.bartleby.com/isbn_cover_images/9781337102087/9781337102087_smallCoverImage.gif)
![EBK JAVA PROGRAMMING](https://www.bartleby.com/isbn_cover_images/9781337671385/9781337671385_smallCoverImage.jpg)
![C++ Programming: From Problem Analysis to Program…](https://www.bartleby.com/isbn_cover_images/9781337102087/9781337102087_smallCoverImage.gif)
![EBK JAVA PROGRAMMING](https://www.bartleby.com/isbn_cover_images/9781337671385/9781337671385_smallCoverImage.jpg)