Explore BrainMass

Explore BrainMass

    sorting an array of integers in linear time

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    How can I sort an array of integers in O(n) time, where different integers may have different numbers of digits, but the total number of digits over ALL the integers in the array is n?

    My assumption is that radix sort is somehow involved.

    © BrainMass Inc. brainmass.com December 15, 2022, 5:15 pm ad1c9bdddf
    https://brainmass.com/computer-science/arrays/70840

    Solution Preview

    The result is also in the attached file, which is of the same content as the follows:

    Let us use the following example to facilitate the explanation:

    329
    457
    1086
    8791
    1978
    2006
    12469
    12
    518
    9
    178902
    985730
    234567
    985
    8943

    In this example, the number of digits is 56, i.e., n = 56
    Let m be the number of numbers, i.e., m = 15 in this example, then m < n

    Let n1, n2, ... nk are the possible number of digits of each number in the array, so in this example,
    n1 = 1, n2=2, n3 = 3, n4 = 4, n5 = 5, n6 = 6, ...

    Solution Summary

    This job targets sorting an array of integers in linear time.

    $2.49

    ADVERTISEMENT