Mapa mental Quicksort

Prévia do material em texto

Quicksort
divide- and- conquer approach
Partitioning array
(Hoare Partition)
divides input elements according to their value
select a pivot
scan the subarray from 
both ends, comparing 
elements to the pivot
left- to- right scan (i): stops upon encountering the 
first element greater than or equal tot he pivot
right- to- left scan (j): stops on encountering the 
first element smaller than or equal to the pivot
After both scans stop:
i and j have not crossed (i<j): exchange A[i] 
and A[j] and increment i and decrement j
scanning indices have crossed (i>j)
scanning indices stop while 
pointing to the same element (i=j) the value they are pointing to must be equal to p
Efficiency
number of key comparisons made bfore is achieved is n+1 
if the canning indices cross over and n if they coincide
best case: all the splits happen in the middle of corresponding subarrays
worst case: all the splits will 
be skewed to the extreme
(increasing arrays)
one of the arrays will be empty
the other array will have a size just 1 less than 
the size of the subarray being partitioned
avarage case
usually runs faster than mergesort and heapsort
Improvements
switching to insertion sort on very small subarrays (5-15 elements) 
or not sorting small subarrys at all and finishing with insertion sort
better pivot slection methods (randomized quicksort)
It is no stable and require a stack to store 
parameters of subarrays that are yet to be sorted