Introduction to QuickSort Algorithm
undefined
C
OEN
352 – S
UMMER
2019
Tutorial Session 3
1
W
ORST
CASE
TIME
COMPLEXITY
LINEAR
DATA
STRUCTURE
2
Q
UICKSORT
:
OUTLINE
Recursive method:
Input: array, firstindex, lastindex
1.
Check the stopping case: firstindex<lastindex
1.
Find the splitpoint : partition
Most important
point NEXT SLIDE!!!!
2.
Recursion on left part
3.
Recursion on Right part
3
Q
UICK
SORT
ALGORITHM
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
T
HE
Q
UICKSORT
:
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:
a.
If yes, increment the left pointer and decrement the right
pointer
b.
If not, swap the lelement and relement
5) When left >= right, swap the pivot with either left or
right pointer.
5
Q
UICKSORT
: P
ARTITION
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
Q
UICKSORT
: P
ARTITION
(
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
P
ARTITION
ALGORITHM
:
EXAMPLE
1.
Choosing the pivot:
2.
Moving through the array to find the last
position of the pivot: the partition
8
P
ARTITION
:
CONT
’
D
9
P
ARTITION
:
CONT
’
D
10
P
ARTITION
:
END
11
A
NALYSIS
OF
COMPLEXITY
1.
Worst case: O(N
2
)
•
When the array is sorted and one choose as pivot the
smallest/largest element. Then one partition is empty the
other has N-1
2.
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.
3.
Average case: O(NlogN)
12
I
MPROVEMENTS
?
1.
Another way to chose the pivot: Median of three (last,
middle, first)
2.
Switching to another sorting algorithm when size of
partition become small: mostly insertion sort.
3.
Improvement on the recursion: consider the longest
partition as the last statement
Memory
improvement
13
E
XERCISE
:
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
C
OMPLETE
THE
CODE
Partition(arr, lo, hi){piv=arr[lo]
i=lo+1
j=hi+1
/*
Find the partitions
*/
}
15
E
XERCISE
2: H
OW
DO
WE
KNOW
THAT
THE
PARTITION
IS
SMALL
ENOUGH
?
Exercise: Here we will discuss how to find the right
cutoff to switch to insertion sort.
1.
Consider four array size: 1e+05, 4e+05,7e+05
and 1e+06
2.
Generate a sequence of cutoff: 1:100 (for
example)
3.
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.
16
E
XERCISE
2: H
OW
DO
WE
KNOW
THAT
THE
PARTITION
IS
SMALL
ENOUGH
?
4.
Average the time on the replicates. Do it for all
cutoff and all array size
Plot the Time Taken vs cutoff
5.
Find the good cutoff
17
O
THER
OPTIMIZATION
3 ways quicksort:
1.
Implementation:
https://rubyalgo.github.io/algorithms/sorting/3way-
quick-sort/
2.
https://algs4.cs.princeton.edu/lectures/23Quicksort.
Quicksort pseudo code:
http://interactivepython.org/courselib/static/python
ds/SortSearch/TheQuickSort.html
18
REFERENCES
Image are from:
http://interactivepython.org/courselib/static/python
ds/SortSearch/TheQuickSort.html
19
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
