Algo Lecture 6 Quick Sor

  • Upload
    anony1

  • View
    215

  • Download
    0

Embed Size (px)

Citation preview

  • 8/2/2019 Algo Lecture 6 Quick Sor

    1/30

    Algorithms Analysis

    Lecture 6Quicksort

  • 8/2/2019 Algo Lecture 6 Quick Sor

    2/30

    Quick Sort

    8814

    982562

    52

    79

    3023

    31

    Divide and Conquer

  • 8/2/2019 Algo Lecture 6 Quick Sor

    3/30

    Quick Sort

    8814

    982562

    52

    79

    3023

    31

    Partition set into two using

    randomly chosen pivot

    14

    25

    302331

    8898

    6279

    52

  • 8/2/2019 Algo Lecture 6 Quick Sor

    4/30

  • 8/2/2019 Algo Lecture 6 Quick Sor

    5/30

    Quick Sort

    14,23,25,30,31

    62,79,88,98

    52

    Glue pieces together.

    14,23,25,30,31,52,62,79,88,98

  • 8/2/2019 Algo Lecture 6 Quick Sor

    6/30

    Quicksort

    Quicksort pros [advantage]:

    Sorts in place

    Sorts O(n lg n) in the average case

    Very efficient in practice , its quick

    Quicksort cons [disadvantage]:

    Sorts O(n2) in the worst case

    And the worst case doesnt happen often sorted

  • 8/2/2019 Algo Lecture 6 Quick Sor

    7/30

    Quicksort

    Another divide-and-conquer algorithm:

    Divide: A[pr] is partitioned (rearranged) into twononempty subarraysA[pq-1] andA[q+1r] s.t.each element ofA[pq-1] is less than or equal to

    each element ofA[q+1r]. Index q is computed here,called pivot.

    Conquer: two subarrays are sorted by recursive callsto quicksort.

    Combine: unlike merge sort, no work needed sincethe subarrays are sorted in place already.

  • 8/2/2019 Algo Lecture 6 Quick Sor

    8/30

    Quicksort

    The basic algorithm to sort an arrayA consists of the following foureasy steps:

    If the number of elements inA is 0 or 1, then return Pick any element v inA. This is called the pivot

    PartitionA-{v} (the remaining elements inA) into two disjointgroups:

    A1 = {xA-{v} |x v}, and

    A2 = {xA-{v} |x v} return

    { quicksort(A1) followed by v followed byquicksort(A2)}

  • 8/2/2019 Algo Lecture 6 Quick Sor

    9/30

    Quicksort Small instance has n 1

    Every small instance is a sorted instance

    To sort a large instance: select a pivot element from out of the n elements

    Partition the n elements into 3 groups left, middle andright The middle group contains only the pivot element All elements in the left group are pivot

    All elements in the right group are pivot

    Sort left and right groups recursively

    Answer is sorted left group, followed by middle group

    followed by sorted right group

  • 8/2/2019 Algo Lecture 6 Quick Sor

    10/30

  • 8/2/2019 Algo Lecture 6 Quick Sor

    11/30

    Partition

    Clearly, all the action takes place in thepartition() function

    Rearranges the sub

    array in place End result:

    Two subarrays

    All values in first subarray e all values in second

    Returns the index of the pivot elementseparating the two subarrays

  • 8/2/2019 Algo Lecture 6 Quick Sor

    12/30

    Partition CodePartition(A, p, r)

    {

    x = A[r] // x is pivot

    i = p - 1

    for j = p to r 1

    {

    do if A[j]

  • 8/2/2019 Algo Lecture 6 Quick Sor

    13/30

    Partition Example

    A = {2, 8, 7, 1, 3, 5, 6, 4}

    2 8 7 1 3 5 62 8 7 1 3 5 6 44

    rp ji

    2 8 7 1 3 5 62 8 7 1 3 5 6 44

    rp i j

    rp i j

    2 8 7 1 3 5 62 8 7 1 3 5 6 44

    rp i j

    8822 77 11 33 55 66 44

    rp j

    1122 77 88 33 55 66 44

    i rp j

    1122 33 88 77 55 66 44

    i

    rp j

    1122 33 88 77 55 66 44

    i rp

    1122 33 88 77 55 66 44

    i

    rp

    1122 33 44 77 55 66 88

    i

    22

    22

    22 22

    22 22

    22

    11

    11 33

    33 11 33

    11 33

  • 8/2/2019 Algo Lecture 6 Quick Sor

    14/30

    Partition Example Explanation

    Red shaded elements are in the first partitionwith values e x (pivot)

    Gray shaded elements are in the secondpartition with values u x (pivot)

    The unshaded elements have no yet been put in

    one of the first two partitions

    The final white element is the pivot

  • 8/2/2019 Algo Lecture 6 Quick Sor

    15/30

    Choice Of PivotThree ways to choose the pivot:

    Pivot is rightmost element in list that is to be sorted

    When sortingA[6:20], useA[20] as the pivot

    Textbook implementation does this

    Randomly select one of the elements to be sorted as

    the pivot

    When sortingA[6:20], generate a random numberrinthe range [6, 20]

    UseA[r] as the pivot

  • 8/2/2019 Algo Lecture 6 Quick Sor

    16/30

    Choice Of Pivot

    Median-of-Three rule - from the leftmost, middle, and rightmost

    elements of the list to be sorted, select the one with median key as

    the pivot

    When sorting A[6:20], examineA[6],A[13] ((6+20)/2), andA[20]

    Select the element with median (i.e., middle) key

    If A[6].key = 30,A[13].key = 2, andA[20].key = 10,A[20]

    becomes the pivot

    If A[6].key = 3,A[13].key = 2, andA[20].key = 10,A[6] becomes

    the pivot

  • 8/2/2019 Algo Lecture 6 Quick Sor

    17/30

    Worst Case Partitioning

    The r unning time of quicksort depends on whether the partitioning isbalanced or not.

    5(n) time to partition an array ofn elements

    Let T(n) be the time needed to sort n elements

    T(0) = T(1) = c, where cis a constant

    When n > 1,

    T

    (n

    ) =T

    (|left|) +T

    (|right|) +5

    (n

    )

    T(n) is maximum (worst-case) when either |left| = 0 or |right| = 0following each partitioning

  • 8/2/2019 Algo Lecture 6 Quick Sor

    18/30

    Worst Case Partitioning

  • 8/2/2019 Algo Lecture 6 Quick Sor

    19/30

    Worst Case Partitioning

    Worst-Case Performance (unbalanced):

    T(n) = T(1) + T(n-1) + 5(n)

    partitioning takes 5(n)

    = [2 + 3 + 4 + + n-1 + n ]+ n == [k= 2 to nk]+ n = 5(n

    2)

    This occurs when

    the input is completely sorted

    or when

    the pivot is always the smallest (largest) element

    )(2/)1(...21 2

    1

    nnnnk

    n

    k

    5!!!!

  • 8/2/2019 Algo Lecture 6 Quick Sor

    20/30

  • 8/2/2019 Algo Lecture 6 Quick Sor

    21/30

    Best Case Partitioning

  • 8/2/2019 Algo Lecture 6 Quick Sor

    22/30

    Average Case

    Assuming random input, average-case running time is

    much closer to 5(n lg n) than 5(n2)

    First, a more intuitive explanation/example: Suppose that partition() always produces a 9-to-1

    proportional split. This looks quite unbalanced!

    The recurrence is thus:

    T(n) = T(9n/10) + T(n/10) + 5(n) = 5(n lg n)?

    [Using recursion tree method to solve]

  • 8/2/2019 Algo Lecture 6 Quick Sor

    23/30

    Average Case

    ( ) ( /10) (9 /10) ( ) ( log )!T n T n T n n n n! 5 ! 5

    log2n = log10n/log102

  • 8/2/2019 Algo Lecture 6 Quick Sor

    24/30

    Average Case

    Every level of the tree has cost cn, until a boundary conditionis reached at depth log10n = ( lgn), and then the levels havecost at most cn.

    The recursion terminates at depth log10/9 n= (lg n).

    The total cost of quicksort is therefore O(n lg n).

  • 8/2/2019 Algo Lecture 6 Quick Sor

    25/30

    Average Case

    What happens if we bad-split root node, then good-splitthe resulting size (n-1) node?

    We end up with three subarrays, size

    1, (n-1)/2, (n-1)/2

    Combined cost of splits = n + n-1 = 2n -1 = 5(n)

    n

    1 n-1

    (n-1)/2 (n-1)/2

    ( )n5

    (n-1)/2 (n-1)/2

    n ( )n5

    )1( 5 n

  • 8/2/2019 Algo Lecture 6 Quick Sor

    26/30

    Intuition for the Average Case

    Suppose, we alternate lucky and unlucky cases to get

    an average behavior

    ( ) 2 ( / 2) ( ) lucky

    ( ) ( 1) ( ) unlucky

    we consequently get

    ( ) 2( ( / 2 1) ( / 2)) ( )

    2 ( / 2 1) ( )

    ( log )

    L n U n n

    U n L n n

    L n L n n n

    L n n

    n n

    ! 5

    ! 5

    ! 5 5

    ! 5

    ! 5

    The combination of good and bad splits would result in

    T(n) = O (n lg n),but with slightly larger constant hidden by

    the O-notation.

  • 8/2/2019 Algo Lecture 6 Quick Sor

    27/30

    Randomized Quicksort

    An algorithm is randomizedif its behavior is determined

    not only by the input but also by values produced by a

    random-numbergenerator.

    ExchangeA[r] with an element chosen at random from

    A[pr] in Partition.

    This ensures that the pivot element is equally likely to be

    any of input elements.

    We can sometimes add randomization to an algorithm in

    order to obtain good average-case performance over all

    inputs.

  • 8/2/2019 Algo Lecture 6 Quick Sor

    28/30

    Randomized QuicksortRandomized-Partition(A,p, r)

    1. in Random(p, r)

    2. exchangeA[r] mA[i]

    3. return Partition(A,p, r)

    Randomized-Quicksort(A,p, r)

    1. ifp

  • 8/2/2019 Algo Lecture 6 Quick Sor

    29/30

    Review: Analyzing Quicksort

    What will be the worst case for the algorithm?

    Partition is always unbalanced

    What will be the best case for the algorithm?

    Partition is balanced

  • 8/2/2019 Algo Lecture 6 Quick Sor

    30/30

    Summary: Quicksort

    In worst-case, efficiency is 5(n2)

    But easy to avoid the worst-case

    On average, efficiency is 5(n lg n)

    Better space-complexity than mergesort.

    In practice, runs fast and widely used