Introduction to QuickSort Algorithm
Explore the QuickSort algorithm with details on the worst-case time complexity, partitioning process, recursive method, and example scenarios. Understand how QuickSort efficiently sorts arrays by choosing a pivot, comparing elements, and recursively partitioning the array until sorted. Dive into the implementation steps and key points of the QuickSort algorithm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
COEN 352 SUMMER 2019 Tutorial Session 3 1
WORSTCASETIMECOMPLEXITYLINEAR DATASTRUCTURE 2
QUICKSORT: OUTLINE Recursive method: Input: array, firstindex, lastindex Check the stopping case: firstindex<lastindex Find the splitpoint : partition Most important point NEXT SLIDE!!!! Recursion on left part Recursion on Right part 1. 1. 2. 3. 3
QUICKSORTALGORITHM def quickSort(alist): quickSortHelper(alist,0,len(alist)-1) def quickSortHelper(alist,first,last): if first<last: splitpoint = partition(alist,first,last) quickSortHelper(alist,first,splitpoint-1) quickSortHelper(alist,splitpoint+1,last) 4
THE QUICKSORT : ALGORITHM Partition: return the pivot position 1) Choose a pivot 2) Set a left pointer and right pointer 3) Compare the left pointer element (lelement) with the pivot and the right pointer element (relement) with the pivot. 4) Check if lelement<pivot and relement>pivot: If yes, increment the left pointer and decrement the right pointer If not, swap the lelement and relement 5) When left >= right, swap the pivot with either left or right pointer. a. b. 5
QUICKSORT: PARTITION def partition(alist,first,last): pivotvalue = alist[first] leftmark = first+1 rightmark = last done = False while not done: while (leftmark <= rightmark and alist[leftmark] <= pivotvalue): leftmark = leftmark + 1 while (alist[rightmark] >= pivotvalue and rightmark >= leftmark): rightmark = rightmark -1 6
QUICKSORT: PARTITION (END) if (rightmark < leftmark): done = True else: temp = alist[leftmark] alist[leftmark] = alist[rightmark] alist[rightmark] = temp temp = alist[first] alist[first] = alist[rightmark] alist[rightmark] = temp return rightmark 7
PARTITION ALGORITHM: EXAMPLE Choosing the pivot: 1. Moving through the array to find the last position of the pivot: the partition 2. 8
ANALYSISOFCOMPLEXITY Worst case: O(N2) When the array is sorted and one choose as pivot the smallest/largest element. Then one partition is empty the other has N-1 Best case: O(NlogN) When the pivot is the median of the array an the partitions have the same size Then we have log(N) partitions on which N comparisons are applied. Average case: O(NlogN) 1. 2. 3. 12
IMPROVEMENTS? Another way to chose the pivot: Median of three (last, middle, first) Switching to another sorting algorithm when size of partition become small: mostly insertion sort. Improvement on the recursion: consider the longest partition as the last statement Memory improvement 1. 2. 3. 13
EXERCISE: Program the quicksort with the improvements. Your algorithm should offer the possibility to switch to the optimize version of the code Quicksort(arr,lo,hi) { stopping case: lo>=hi else p= partition(arr,lo,high) rec1: Quicksort(arr, lo, p-1) rec2:Quicksort(arr, p+1, hi) 14 }
COMPLETETHECODE Partition(arr, lo, hi){ piv=arr[lo] i=lo+1 j=hi+1 /* Find the partitions */ } 15
EXERCISE 2: HOWDOWEKNOWTHATTHE PARTITIONISSMALLENOUGH? Exercise: Here we will discuss how to find the right cutoff to switch to insertion sort. Consider four array size: 1e+05, 4e+05,7e+05 and 1e+06 Generate a sequence of cutoff: 1:100 (for example) Record the time taken on each array size with different cutoff. For each array size generate several replicates of array. Apply the hybridQuicsort on each of the replicate and measure the time for each possible cutoff. 1. 2. 3. 16
EXERCISE 2: HOWDOWEKNOWTHATTHE PARTITIONISSMALLENOUGH? Average the time on the replicates. Do it for all cutoff and all array size Plot the Time Taken vs cutoff Find the good cutoff 4. 5. 17
OTHEROPTIMIZATION 3 ways quicksort: Implementation: https://rubyalgo.github.io/algorithms/sorting/3way- quick-sort/ https://algs4.cs.princeton.edu/lectures/23Quicksort. pdf Quicksort pseudo code: http://interactivepython.org/courselib/static/python ds/SortSearch/TheQuickSort.html 1. 2. 18
REFERENCES Image are from: http://interactivepython.org/courselib/static/python ds/SortSearch/TheQuickSort.html 19
