Question

You are given an array of integers, each with an unknown number of digits. You are also told the total number of digits of all the integers in the array is n. Provide an algorithm that will sort the array in O(n) time no matter how the digits are distributed among the elements in the array. (e.g. there might be one element with n digits, or n/2 elements with 2 digits, or the elements might be of all different lengths, etc. Be sure to justify in detail the run time of your algorithm.

Answer 1

Answer:

Explanation:

Since all of the items in the array would be integers sorting them would not be a problem regardless of the difference in integers. O(n) time would be impossible unless the array is already sorted, otherwise, the best runtime we can hope for would be such a method like the one below with a runtime of O(n^2)

static void sortingMethod(int arr[], int n)  

   {  

       int x, y, temp;  

       boolean swapped;  

       for (x = 0; x < n - 1; x++)  

       {  

           swapped = false;  

           for (y = 0; y < n - x - 1; y++)  

           {  

               if (arr[y] > arr[y + 1])  

               {  

                   temp = arr[y];  

                   arr[y] = arr[y + 1];  

                   arr[y + 1] = temp;  

                   swapped = true;  

               }  

           }  

           if (swapped == false)  

               break;  

       }  

   }