Scribd Logo
Upload

Welcome to Scribd!

  • 23 views

    Quick Sort: Characteristics

    Uploaded by

    Ojasvi Monga
    Quicksort is a divide-and-conquer algorithm that works by partitioning an array into two subarrays such that elements in one subarray are less than or equal to elements in the other subarray. It then recursively sorts the subarrays. The average runtime is O(n log n) but the worst case is O(n^2) when the array is already sorted. Randomizing the pivot selection makes the worst case runtime unlikely and results in an expected runtime of O(n log n).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Quick Sort: Characteristics

    Uploaded by

    Ojasvi Monga
    23 views20 pages
    Quicksort is a divide-and-conquer algorithm that works by partitioning an array into two subarrays such that elements in one subarray are less than or equal to elements in the other subarray. It then recursively sorts the subarrays. The average runtime is O(n log n) but the worst case is O(n^2) when the array is already sorted. Randomizing the pivot selection makes the worst case runtime unlikely and results in an expected runtime of O(n log n).

    Original Description:

    Learn QuickSort

    Original Title

    lec10

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Quicksort is a divide-and-conquer algorithm that works by partitioning an array into two subarrays such that elements in one subarray are less than or equal to elements in the other subarray. It then recursively sorts the subarrays. The average runtime is O(n log n) but the worst case is O(n^2) when the array is already sorted. Randomizing the pivot selection makes the worst case runtime unlikely and results in an expected runtime of O(n log n).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    23 views20 pages

    Quick Sort: Characteristics

    Uploaded by

    Ojasvi Monga
    Quicksort is a divide-and-conquer algorithm that works by partitioning an array into two subarrays such that elements in one subarray are less than or equal to elements in the other subarray. It then recursively sorts the subarrays. The average runtime is O(n log n) but the worst case is O(n^2) when the array is already sorted. Randomizing the pivot selection makes the worst case runtime unlikely and results in an expected runtime of O(n log n).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 20

    Quick Sort

    Characteristics
    sorts

    almost in "place," i.e., does not require


    an additional array
    very practical, average sort performance O(n
    log n) (with small constant factors), but worst
    case O(n2)

    Quick Sort the Principle


    To

    understand quick-sort, lets look at a


    high-level description of the algorithm
    A divide-and-conquer algorithm
    Divide:

    partition array into 2 subarrays such


    that elements in the lower part <= elements in
    the higher part
    Conquer: recursively sort the 2 subarrays
    Combine: trivial since sorting is done in place
    2

    Partitioning
    Linear

    time partitioning procedure

    Partition(A,p,r)
    01
    02
    03
    04
    05
    06
    07
    08
    09
    10
    11

    j j

    i i

    xA[r]
    17 12
    ip-1
    X=10
    i
    jr+1
    while TRUE
    10 12
    repeat jj-1
    until A[j] x
    repeat ii+1
    until A[i] x
    10 5
    if i<j
    then exchange A[i]A[j]
    else return j

    10

    19 23

    10

    j
    6

    19 23

    19 23

    17

    12 17

    23 19 12 17
    3

    Quick Sort Algorithm


    Initial

    call Quicksort(A, 1, length[A])

    Quicksort(A,p,r)
    01 if p<r
    02
    then q Partition(A,p,r)
    03
    Quicksort(A,p,q)
    04
    Quicksort(A,q+1,r)

    Analysis of Quicksort
    Assume

    that all input elements are distinct


    The running time depends on the
    distribution of splits

    Best Case

    If we are lucky, Partition splits the array evenly

    T (n) = 2T (n / 2) + (n)

    Worst Case
    What

    is the worst case?


    One side of the parition has only one element
    T (n) = T (1) + T (n 1) + (n)
    = T (n 1) + (n)
    =

    ( k )
    k =1

    = ( k )
    k =1

    = ( n 2 )
    7

    Worst Case (2)

    Worst Case (3)


    When

    does the worst case appear?

    input

    is sorted
    input reverse sorted
    Same

    recurrence for the worst case of


    insertion sort
    However, sorted input yields the best case
    for insertion sort!

    Analysis of Quicksort
    Suppose

    the split is 1/10 : 9/10

    T (n) = T (n /10) + T (9n /10) + (n) = (n log n)!

    10

    11

    An Average Case Scenario

    Suppose, we alternate
    lucky and unlucky
    cases to get an
    average behavior

    (n)

    L(n) = 2U (n / 2) + (n) lucky


    U (n) = L(n 1) + (n) unlucky
    we consequently get
    L(n) = 2( L(n / 2 1) + (n / 2)) + (n)
    = 2 L(n / 2 1) + (n)
    = (n log n)

    n-1

    1
    (n-1)/2

    (n-1)/2

    (n-1)/2+1

    ( n )
    (n-1)/2
    12

    An Average Case Scenario (2)

    How can we make sure that we are usually


    lucky?
    Partition around the middle (n/2th) element?
    Partition around a random element (works well in
    practice)

    Randomized algorithm
    running time is independent of the input ordering
    no specific input triggers worst-case behavior
    the worst-case is only determined by the output of the
    random-number generator

    13

    Randomized Quicksort
    Assume

    all elements are distinct


    Partition around a random element
    Consequently, all splits (1:n-1, 2:n-2, ..., n1:1) are equally likely with probability 1/n
    Randomization

    is a general tool to improve


    algorithms with bad worst-case but good
    average-case complexity
    14

    Randomized Quicksort (2)


    Randomized-Partition(A,p,r)
    01 i Random(p,r)
    02 exchange A[r] A[i]
    03 return Partition(A,p,r)
    Randomized-Quicksort(A,p,r)
    01 if p < r then
    02
    q Randomized-Partition(A,p,r)
    03
    Randomized-Quicksort(A,p,q)
    04
    Randomized-Quicksort(A,q+1,r)

    15

    Randomized Quicksort Analysis


    Let T(n) be the expected number of
    comparisons needed to quicksort n numbers.
    Since each split occurs with probability 1/n, T(n)
    has value T(i-1)+T(n-i)+n-1 with probability 1/n.
    Hence,

    16

    Randomized Quicksort Analysis(2)


    We

    have seen this recurrence before.


    It is the recurrence for the expected
    number of comparisons required to insert
    a randomly chosen permutation of n
    elements.
    We proved that T(n) = O(nlog2 n).
    Hence expected number of comparisons
    required by randomized quicksort is
    O(nlog2 n)
    17

    Randomized Quicksort running times


    Worst

    case running time of quicksort is

    O(n2)
    Best case running time of quicksort is
    O(nlog2 n)
    Expected running time of quicksort is
    O(nlog2 n)

    18

    What does expected running time mean?


    The running time of quicksort does not depend
    on the input. It depends on the random numbers
    provided by the generator.
    Thus for the same input the program might take
    3sec today and 5sec tomorrow.
    The average time taken over many different runs
    of the program would give us the expected time.
    Same as saying that we are taking average over
    all possible random number sequences provided
    by the generator.

    19

    Analysis of insertion in BST


    When creating a binary search tree on n
    elements the running time does depend on the
    order of the elements.
    Our algorithm for insertion did not employ an
    random bits.
    Given a specific input order the algorithm takes
    the same time each day.
    However, the time taken is different for different
    input orders.
    The average time taken over all possible input
    orders is O(nlog2 n).

    20

    You might also like