Purchase Solution

sorting an array of integers in linear time

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
Solution Summary

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

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, ...

Purchase this Solution
Free BrainMass Quizzes
Javscript Basics

Quiz on basics of javascript programming language.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Basic Networking Questions

This quiz consists of some basic networking questions.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

View More Free Quizzes
Related BrainMass Solutions

  • Insertion Sort and Selection Sort Using C

    Generate an array of random integers to be sorted using either insertion sort or selection sort. 2. Allow the user to specify the number of integers in the array to be sorted in the main function. 3.

  • Find the Largest and Smallest and Sort values in array C++

    You should be able to use the two functions to achieve what you want including sorting of an array. For sorting, you need to do a little bit more than just finding minimum and maximum from an array.

  • two pointer arrays

    Read ten integers from the keyboard and place them in an array.

  • Design and Analysis of Algorithms

    (a) We can use Merge Sort to sort the given set G of m integers (stored in an array of size m) in increasing order. Merge Sort guarantees O(m*lg(m)) time complexity.

  • Java class creates an array of integers

    205701 Java class creates an array of integers Java Programming - Array Sort Description Write a Java class that creates an array of integers, fills it with values, prints the unsorted values, sorts the values into ascending order, and finally prints

  • Creating a sorting array

    The expert creates a sorting array. Adjacent pairs of elements in an array are determined. The solution is provided in a Java file.

  • Array types

    Two dimensional array is used when one array is needed simultaneously at an instant. e.g., the names of the 100 students. The name of each student is an array of the characters, and there are 100 students.

  • Quick sort

    33266 Median of Three Worst Case Scenario Suppy an array containing integers 1 through 12 such that a quicksort algorithm using median of three will recurse to 6 levels, counting the top level as 0; showing that even with median of three, quicksort has

  • Data Structure in C++

    To support also '0' at the beginning of a phone number, we simply shifted all digits by 1 in the internal representation of phone numbers: 0 -> 1 1 -> 2 2 -> 3 ... 9 -> 10 This would allow easy manipulation (e.g. sorting) of phone numbers as integers

View More Related Solutions