Scribd Logo
Upload

Welcome to Scribd!

  • 59 views

    Sorting 32

    Uploaded by

    dmybook
    Quicksort is a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array into two subarrays - one with elements less than the pivot and one with elements greater than the pivot. It then recursively sorts the subarrays. The worst case running time is O(n^2) but the average case is O(nlogn). Randomizing the pivot selection improves the algorithm's performance on pre-sorted or partially sorted arrays to the average case of O(nlogn).

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    Sorting 32

    Uploaded by

    dmybook
    59 views11 pages
    Quicksort is a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array into two subarrays - one with elements less than the pivot and one with elements greater than the pivot. It then recursively sorts the subarrays. The worst case running time is O(n^2) but the average case is O(nlogn). Randomizing the pivot selection improves the algorithm's performance on pre-sorted or partially sorted arrays to the average case of O(nlogn).

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, 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 selecting a pivot element and partitioning the array into two subarrays - one with elements less than the pivot and one with elements greater than the pivot. It then recursively sorts the subarrays. The worst case running time is O(n^2) but the average case is O(nlogn). Randomizing the pivot selection improves the algorithm's performance on pre-sorted or partially sorted arrays to the average case of O(nlogn).

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    59 views11 pages

    Sorting 32

    Uploaded by

    dmybook
    Quicksort is a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array into two subarrays - one with elements less than the pivot and one with elements greater than the pivot. It then recursively sorts the subarrays. The worst case running time is O(n^2) but the average case is O(nlogn). Randomizing the pivot selection improves the algorithm's performance on pre-sorted or partially sorted arrays to the average case of O(nlogn).

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 11

    sorting 32

    Quick-Sort
    • To understand quick-sort, let’s look at a high-
    level
    description of the algorithm
    • 1) Divide : If the sequence S has 2 or more
    elements,
    select an element x from S to you pivot. Any
    arbitrary element, like the last, will do. Remove
    all
    the elements of S and divide them into 3
    sequences:
    - L, holds S’s elements less than x
    - E, holds S’s elements equal to x
    - G, holds S’s elements greater than x
    • 2) Recurse: Recursively sort L and G
    • 3) Conquer: Finally, to put elements back into
    S in
    order, first inserts the elements of L, then those
    of E,
    and those of G.
    • Here are some pretty diagrams....
    sorting 33
    Quick-Sort Tree
    85 24 63 45 17 31 96 50
    24 45 17 31 50 85 63 96
    sorting 34

    Quick-Sort Tree (cont.)


    24 45 17 31
    50 85 63 96
    24 17 31 45
    50 85 63 96
    sorting 35

    Quick-Sort Tree (cont.)


    24 17
    31 45
    50 85 63 96
    17 24
    31 45
    50 85 63 96
    sorting 36

    Quick-Sort Tree (cont.)


    17 24
    31 45
    50 85 63 96
    17 24
    31 45
    50 85 63 96
    sorting 37

    Quick-Sort Tree (cont.)


    17
    24
    31 45
    50 85 63 96
    17 24
    31 45
    50 85 63 96
    sorting 38

    Quick-Sort Tree (cont.)


    17 24
    31 45
    50 85 63 96
    17 24 31 45
    50 85 63 96
    sorting 39

    Quick-Sort Tree (cont.)


    17 24 31
    50 85 63 96
    45
    17 24 31
    50 85 63 96
    45
    sorting 40

    Quick-Sort Tree (cont.)


    17 24 31
    50 85 63 96
    45
    17 24 31 45 50 85 63 96
    sorting 41

    Quick-Sort Tree (cont.)


    17 24 31 45 50 63 85 96
    17 24 31 45 50 63 85 96
    sorting 42

    Analysis of Running Time


    • Consider a quick-sort tree T:
    - Let si(n) denote the sum of the input sizes of
    the
    nodes at depth i in T.
    • We know that s0(n) = n since the root of T is
    associated with the entire input set.
    • Also, s1(n) = n - 1 since the pivot is not
    propagated.
    • Thus: either s2(n) = n - 3, or n - 2 (if one of the
    nodes
    has a zero input size).
    • The worst case running time of a quick-sort is
    then:
    Which reduces to:
    • Thus quick-sort runs in time O(n2) in the worst
    case.
    O si(n)
    i=0
    n1–
    ∑
     
     
     
    O ( n–i)
    i=0
    n1–
    ∑
     
     
     
    Oi
    i=1
    n∑
     
     
     
    O n2 = = ( )
    sorting 43

    Analysis of Running Time


    (contd.)
    • Now to look at the best case running time:
    • We can see that quicksort behaves optimally
    if,
    whenever a sequence S is divided into
    subsequences
    L and G, they are of equal size.
    • More precisely:
    - s0(n) = n
    - s1(n) = n - 1
    - s2(n) = n - (1 + 2) = n - 3
    - s3(n) = n - (1 + 2 + 22) = n - 7
    ...
    - si(n) = n - (1 + 2 + 22 + ... + 2i-1) = n - 2i + 1
    ...
    • This implies that T has height O(log n)
    • Best Case Time Complexity: O(nlog n)
    sorting 44

    Randomized Quick-Sort
    • The main drawback to quick-sort is that it
    achieves
    its worst-case time complexity on data sets that
    are
    common in practice: sequences that are already
    sorted (or mostly sorted)
    • To avoid this, we modify quick-sort so that it
    selects
    the pivot as a random element of the sequence
    • The expected time of a randomized quick-sort
    on a
    sequence of size n is O(nlog n).
    • Justification: we say that an invocation of
    quicksort,
    on an input sequence of size m is “good” if
    neither L
    nor G is less than m/4.
    - there are m/2 “good” pivots and m/2 “bad”
    ones
    - The probablility that an invocation is “good” is
    1/2
    - Suppose we choose a good pivot at node v: the
    algorithm recurs on sequences with size at most
    (3/4)m each
    - On average, the height of the tree representing
    a
    randomized quick-sort is at most 2log4/3 n
    • Total time complexity: O(n log n)
    sorting 45

    In-Place Quick-Sort
    • Divide step: l scans the sequence from the left,
    and r
    from the right.
    • A swap is performed when l is at an element
    larger
    than the pivot and r is at one smaller than the
    pivot.
    85 24 63 45 17 31 96 50
    lr
    85 24 63 45 17 31 96 50
    lr
    31 24 63 45 17 85 96 50
    lr
    sorting 46

    In Place Quick Sort (contd.)


    • A final swap with the pivot completes the
    divide step
    31 24 63 45 17 85 96 50
    lr
    31 24 17 45 63 85 96 50
    lr
    31 24 17 45 63 85 96 50
    lr
    31 24 17 45 50 85 96 63
    lr
    sorting 47

    In Place Quick Sort (contd.)


    • pseude-code fragment 8.7
    sorting 48

    How Fast Can We Sort?


    • Proposition: The running time of any
    comparisonbased
    algorithm for sorting an n-element sequence S
    is Ω (nlog n).
    • Justification:
    • The running time of a comparison-based
    sorting
    algorithm must be equal to or greater than the
    depth
    of the decision tree T associated with this
    algorithm.
    • Each internal node of T is associated with a
    comparison that establishes the ordering of two
    elements of S.
    • Thus every external node of T represents a
    distinct
    permutation of the elements of S.
    • Hence T must have at least n! external nodes
    which
    again implies T has a height of at least log(n!)
    • Since n! has at least n/2 terms that are greater
    than or
    equal to n/2, we can see:
    • log(n!) log(n/2)n/2 = (n/2)log(n/2)
    • Total Time Complexity: Ω (nlog n).
    sorting 49

    How Fast Can We Sort?


    (contd.)
    • A graphical representation of a comparison-
    based
    algorithm’s decision tree.
    s1 s2
    s1 s3
    s1 sn s1 sn
    s1 s3
    s1 sn s1 sn
    ...
    ...
    ...
    ...
    sn-1 sn sn-1 sn sn-1 sn sn-1 sn
    yes no
    no no
    no no no
    no no no no
    yes yes
    yes yes yes yes
    no
    yes yes yes yes

    You might also like