Sorting without comparing elements

Question

given size of array 5, with five numbers in it, sort them from smallest to largest without comparing.(hint, access time O(n)

I tried to search a lot but didnt knew, how it can be done. O(n), means which algo/data structure.i am unaware.

Answer 1

I suppose you need Counting sort, it has linear time, but takes some memory and depends on min/max value of your initial array

Answer 2

The Counting Sort will do this for you, although if I were in an interview and on the spot I'd probably do something like the below which is vaguely similar as I can never remember these "classic" algorithms off the top of my head!

The key idea here is to use the each actual unsorted integer value as an index into a target array that contains N elements where N is the max. of the values to be sorted.

I am using a simple class to record both the value and the number of times it occurred so you can reconstruct an actual array from it if you need to keep discrete values that occurred multiple times in the original array.

So all you need to do is walk the unsorted array once, putting each value into the corresponding index in the target array, and (ignoring empty elements) your values are already sorted from smallest to largest without having ever compared them to one another.

(I personally am not a fan of interview questions like this where the answer is "oh, use Counting Sort" or whatever - I would hope that the interviewer asking this question would be genuinely interested to see what approach you took to solving a new problem, regardless of if you got a strictly correct answer or not)

The performance of the below is O(n) meaning it runs in linear time (1 element takes X amount of time, 10 elements takes 10X,etc) but it can use a lot of memory if the max element is large,cannot do in place sorting, will only work with primitives and it's not something I'd hope to ever see in production code :)

void Main()
{
   //create unsorted list of random numbers
    var unsorted = new List<int>();
    Random rand = new Random();
    for(int x=0;x<10;x++)
    {
     unsorted.Add(rand.Next(1,10));
    }
    //create array big enough to hold unsorted.Max() elements
    //note this is indirectly performing a comparison of the elements of the array
    //but not for the sorting, so I guess that is allowable :)
    var sorted = new NumberCount[unsorted.Max()+1];
    //loop the unsorted array 
    for (int index=0;index<unsorted.Count;index++)
    {
   //get the value at the current index and use as an index to the target array
        var value = unsorted[index];
        //if the sorted array contains the value at the current index, just increment the count
        if (sorted[value]!=null && sorted[value].Value!=0)
        {
           sorted[value].Count++;
        }
        else
        {
        //insert the current value in it's index position
         sorted[value]=new NumberCount{Value=value,Count=1};          
        }
    }
    //ignore all elements in sorted that are null because they were not part of the original list of numbers.
    foreach (var r in sorted.Where(r=>r!=null))
    {
       Console.WriteLine("{0}, occurs {1} times",r.Value,r.Count);
    }
}

//just a poco to hold the numbers and the number of times they occurred.
public class NumberCount
{
  public int Value{get;set;}
  public int Count{get;set;}
}