Scribd Logo
Upload

Welcome to Scribd!

  • 58 views

    Algorithms and Data Structures: Counting Sort and Radix Sort

    Uploaded by

    DAWIT SEGED
    The document discusses counting sort and radix sort algorithms. Counting sort runs in linear time O(n+m) when keys are integers from 1 to m, where m=O(n). Radix sort works by sorting keys digit by digit using a stable sorting algorithm like counting sort at each stage, requiring overall time Θ(d(n+R)) to sort keys of length d with a maximum digit value R.

    Copyright:

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

    Algorithms and Data Structures: Counting Sort and Radix Sort

    Uploaded by

    DAWIT SEGED
    58 views21 pages
    The document discusses counting sort and radix sort algorithms. Counting sort runs in linear time O(n+m) when keys are integers from 1 to m, where m=O(n). Radix sort works by sorting keys digit by digit using a stable sorting algorithm like counting sort at each stage, requiring overall time Θ(d(n+R)) to sort keys of length d with a maximum digit value R.

    Original Title

    lecture9.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses counting sort and radix sort algorithms. Counting sort runs in linear time O(n+m) when keys are integers from 1 to m, where m=O(n). Radix sort works by sorting keys digit by digit using a stable sorting algorithm like counting sort at each stage, requiring overall time Θ(d(n+R)) to sort keys of length d with a maximum digit value R.

    Copyright:

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

    Algorithms and Data Structures: Counting Sort and Radix Sort

    Uploaded by

    DAWIT SEGED
    The document discusses counting sort and radix sort algorithms. Counting sort runs in linear time O(n+m) when keys are integers from 1 to m, where m=O(n). Radix sort works by sorting keys digit by digit using a stable sorting algorithm like counting sort at each stage, requiring overall time Θ(d(n+R)) to sort keys of length d with a maximum digit value R.

    Copyright:

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

    Algorithms and Data Structures:

    Counting sort and Radix sort

    8th February, 2016

    ADS: lect 9 – slide 1 – 8th February, 2016


    Special Cases of the Sorting Problem
    In this lecture we assume that the sort keys are sequences of bits.
    I Quite a natural special case. Doesn’t cover everything:
    I eg, exact real number arithmetic doesn’t take this form.
    I In certain applications, eg Biology, pairwise experiments may only
    return > or < (non-numeric).
    I Sometimes the bits are naturally grouped, eq, as characters in a
    string or hexadecimal digits in a number (4 bits), or in general bytes
    (8 bits).
    I Today’s sorting algorithms are allowed access these bits or groups of
    bits, instead of just letting them compare keys . . .
    This was NOT possible in comparison-based setting.

    ADS: lect 9 – slide 2 – 8th February, 2016


    Easy results . . . Surprising results
    Simplest Case:
    Keys are integers in the range 1, . . . , m, where m = O(n) (n is (as usual)
    the number of elements to be sorted). We can sort in Θ(n) time

    ADS: lect 9 – slide 3 – 8th February, 2016


    Easy results . . . Surprising results
    Simplest Case:
    Keys are integers in the range 1, . . . , m, where m = O(n) (n is (as usual)
    the number of elements to be sorted). We can sort in Θ(n) time
    (big deal

    ADS: lect 9 – slide 3 – 8th February, 2016


    Easy results . . . Surprising results
    Simplest Case:
    Keys are integers in the range 1, . . . , m, where m = O(n) (n is (as usual)
    the number of elements to be sorted). We can sort in Θ(n) time
    (big deal . . . but will help later).

    ADS: lect 9 – slide 3 – 8th February, 2016


    Easy results . . . Surprising results
    Simplest Case:
    Keys are integers in the range 1, . . . , m, where m = O(n) (n is (as usual)
    the number of elements to be sorted). We can sort in Θ(n) time
    (big deal . . . but will help later).
    Surprising case: (I think)
    For any constant k, the problem of sorting n integers in the range {1, . . . , nk }
    can be done in Θ(n) time.

    ADS: lect 9 – slide 3 – 8th February, 2016


    Counting Sort
    Assumption: Keys (attached to items) are Ints in range 1, . . . , m.

    ADS: lect 9 – slide 4 – 8th February, 2016


    Counting Sort
    Assumption: Keys (attached to items) are Ints in range 1, . . . , m.
    Idea
    1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the input
    array. Store results in an array C .

    ADS: lect 9 – slide 4 – 8th February, 2016


    Counting Sort
    Assumption: Keys (attached to items) are Ints in range 1, . . . , m.
    Idea
    1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the input
    array. Store results in an array C .
    2. The counting information stored in C can be used to determine the
    position of each element in the sorted array. Suppose we modify the
    values of the C [j] so that now
    C [j] = the number of keys less than or equal to j.
    Then we know that the elements with key “j” must be stored at the
    indices C [j − 1] + 1, . . . , C [j] of the final sorted array.

    ADS: lect 9 – slide 4 – 8th February, 2016


    Counting Sort
    Assumption: Keys (attached to items) are Ints in range 1, . . . , m.
    Idea
    1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the input
    array. Store results in an array C .
    2. The counting information stored in C can be used to determine the
    position of each element in the sorted array. Suppose we modify the
    values of the C [j] so that now
    C [j] = the number of keys less than or equal to j.
    Then we know that the elements with key “j” must be stored at the
    indices C [j − 1] + 1, . . . , C [j] of the final sorted array.
    3. We use a “trick” to move the elements to the right position of an
    auxiliary array. Then we copy the sorted auxiliary array back to the
    original one.

    ADS: lect 9 – slide 4 – 8th February, 2016


    Implementation of Counting Sort

    Algorithm Counting Sort(A, m)


    1. n ← A.length
    2. Initialise array C [1 . . . m]
    3. for i ← 1 to n do
    4. j ← A[i].key
    5. C [j] ← C [j] + 1
    6. for j ← 2 to m do
    7. C [j] ← C [j] + C [j − 1] B C [j] stores ] of keys ≤ j
    8. Initialise array B[1 . . . n]
    9. for i ← n downto 1 do
    10. j ← A[i].key B A[i] highest w. key j
    11. B[C [j]] ← A[i] B Insert A[i] into highest free index for j
    12. C [j] ← C [j] − 1
    13. for i ← 1 to n do
    14. A[i] ← B[i]

    ADS: lect 9 – slide 5 – 8th February, 2016


    Analysis of Counting Sort
    I The loops in lines 3–5, 9–12, and 13–14 all require time Θ(n).
    I The loop in lines 6–7 requires time Θ(m).
    I Thus the overall running time is

    O(n + m).

    I This is linear in the number of elements if m = O(n).

    ADS: lect 9 – slide 6 – 8th February, 2016


    Analysis of Counting Sort
    I The loops in lines 3–5, 9–12, and 13–14 all require time Θ(n).
    I The loop in lines 6–7 requires time Θ(m).
    I Thus the overall running time is

    O(n + m).

    I This is linear in the number of elements if m = O(n).

    Note: This does not contradict Theorem 3 from Lecture 7 - that’s a result
    about the general case, where keys have an arbitary size (and need not
    even be numeric).

    ADS: lect 9 – slide 6 – 8th February, 2016


    Analysis of Counting Sort
    I The loops in lines 3–5, 9–12, and 13–14 all require time Θ(n).
    I The loop in lines 6–7 requires time Θ(m).
    I Thus the overall running time is

    O(n + m).

    I This is linear in the number of elements if m = O(n).

    Note: This does not contradict Theorem 3 from Lecture 7 - that’s a result
    about the general case, where keys have an arbitary size (and need not
    even be numeric).
    Note: Counting-Sort is STABLE.
    I (After sorting, 2 items with the same key have their initial relative
    order).

    ADS: lect 9 – slide 6 – 8th February, 2016


    Radix Sort
    Basic Assumption
    Keys are sequences of digits in a fixed range 0, . . . , R − 1,
    all of equal length d.

    Examples of such keys


    I 4 digit hexadecimal numbers (corresponding to 16 bit integers)
    R = 16, d = 4
    I 5 digit decimal numbers (for example, US post codes)
    R = 10, d = 5
    I Fixed length ASCII character sequences
    R = 128
    I Fixed length byte sequences
    R = 256

    ADS: lect 9 – slide 7 – 8th February, 2016


    Stable Sorting Algorithms
    Definition 1
    A sorting algorithm is stable if it always leaves elements with equal keys
    in their original order.

    ADS: lect 9 – slide 8 – 8th February, 2016


    Stable Sorting Algorithms
    Definition 1
    A sorting algorithm is stable if it always leaves elements with equal keys
    in their original order.

    Examples
    I Counting-Sort, Merge-Sort, and Insertion Sort are all
    stable.
    I Quicksort is not stable.
    I If keys and elements are exactly the same thing (in our setting, an
    element is a structure containing the key as a sub-element) then we
    have a much easier (non-stable) version of Counting-Sort.
    (How? ... CLASS?).

    ADS: lect 9 – slide 8 – 8th February, 2016


    Radix Sort (cont’d)
    Idea
    Sort the keys digit by digit, starting with the least
    significant digit.
    Example
    now sob tag ace
    for nob ace bet
    tip ace bet dim
    ilk tag dim for
    dim ilk tip hut
    tag dim sky ilk
    jot tip ilk jot
    sob for sob nob
    nob jot nob now
    sky hut for sky
    hut bet jot sob
    ace now now tag
    bet sky hut tip

    Each of the three sorts is carried out with respect to the digits in that
    column. “Stability” (and having previously sorted digits/suffixes to the
    right), means this achieves a sorting of the suffixes starting at the current
    column.
    ADS: lect 9 – slide 9 – 8th February, 2016
    Radix Sort (cont’d)

    Algorithm Radix-Sort(A, d)
    1. for i ← 0 to d do
    2. use stable sort to sort array A using digit i as key

    Most commonly, Counting Sort is used in line 2 - this means that once
    a set of digits is already in sorted order, then (by stability) performing
    Counting Sort on the next-most significant digits preserves that order,
    within the “blocks” constructed by the new iteration.
    Then each execution of line 2 requires time Θ(n + R).
    Thus the overall time required by Radix-Sort is

    Θ(d(n + R))

    ADS: lect 9 – slide 10 – 8th February, 2016


    Sorting Integers with Radix-Sort
    Theorem 2
    An array of length n whose keys are b-bit numbers can be sorted in time

    Θ(ndb/ lg ne)

    using a suitable version of Radix-Sort.


    Proof: Let the digits be blocks of dlg ne bits. Then R = 2dlg ne = Θ(n)
    and d = db/dlg nee. Using the implementation of Radix-Sort based on
    Counting Sort the integers can be sorted in time

    Θ(d(n + R)) = Θ(ndb/ lg ne).

    Note: If all numbers are at most nk , then b = k lg n . . . ⇒ Radix Sort


    is Θ(n) (assuming k is some constant, eg 3, 10).

    ADS: lect 9 – slide 11 – 8th February, 2016


    Reading Assignment
    [CLRS] Sections 8.2, 8.3

    Problems

    1. Think about the qn. on slide 7 - how do we get a very easy


    (non-stable) version of Counting-Sort if there are no items
    attached to the keys?
    2. Can you come up with another way of achieving counting sort’s
    O(m + n)-time bound and stability (you will need a different data
    structure from an array).
    3. Exercise 8.3-4 of [CLRS].

    ADS: lect 9 – slide 12 – 8th February, 2016

    You might also like