Applied Test Series

Question

Consider an array contains n integers, each integer belongs to {0, 1, 2}. What is the best case time complexity to sort an array? 

 

Answer 1

Apply one pass to count a number of  $0, 1, 2$. Then in the second pass do filling $0$ first then $1$ then $2$.

So $O(n)$ time.

void sort(int arr[], int size)
{
    int count[3]; // count[0] for count number of 0's similarly count[1] for 1's and count[2] for 2's
    int i;
    
    for(i=0; i<size; i++) // O(n)
    {
        if (arr[i] == 0) count[0]++;
        else if (arr[i] == 1) count[1]++;
        else count[2]++;
    }
  
  i = 0;
  // insert element in sorted order
  while (count[0])
  {
      arr[i] = 0;
      count[0]--;
      i++;
  }
   while (count[1])
  {
      arr[i] = 1;
      count[1]--
      i++;
  }
   while (count[2])
  {
      arr[i] = 2;
      count[2]--;
      i++;
  }
}

 

Comments

If it is mentioned that you can not use any extra space then?

---

Here extra space is constant

---

yes

Answer 2

...an array containing N elements and each element can either be 0 or 1 or 2 and in the question its mentioned that they want the best case time complexity, so can we assume that all the elements are 0’s or all the elements are 1’s or all elements are 2’s if soo then simply apply Insertion sort.

because in best case insetion sort takes o(n) time complexity because we just need to do n comparisons and no need of shift operation .