Suppose you are given an unsorted array where each element i

Suppose you are given an unsorted array where each element is either a 0 or 1. What is the asymptotic order of the number of comparisons done by Quicksort in the worst case? (describe the worst case input) Give a more efficient algorithm for sorting an array of n elements which are all 0\'s or 1\'s. Analyze the worst case time complexity of your algorithm.

Solution

1)  
   Worst case of Quick Sort: O(n^2)

   Worst case occurs in Qiick Sort , we always pick largest (or smallest) element as pivot elment.
   So, in this case, array is divided in two parts : one part contains one element and other part contains (n-1) elements.

2)
   given arr[0...n-1] => contains 0 or 1
   Use two indexes to traverse
   Maintain two indexes. Initialize first index left as 0 and second index right as n-1.

   Do following while left < right
   a) Keep incrementing index left while there are 0s at it
   b) Keep decrementing index right while there are 1s at it
   c) If left < right then exchange arr[left] and arr[right]

      
   /*Function to put all 0s on left and all 1s on right*/
   void segregate0and1(int arr[], int size)
   {
   /* Initialize left and right indexes */
   int left = 0, right = size-1;
     
   while (left < right)
   {
   /* Increment left index while we see 0 at left */
   while (arr[left] == 0 && left < right)
   left++;
     
   /* Decrement right index while we see 1 at right */
   while (arr[right] == 1 && left < right)
   right--;
     
   /* If left is smaller than right then there is a 1 at left
   and a 0 at right. Exchange arr[left] and arr[right]*/
   if (left < right)
   {
   arr[left] = 0;
   arr[right] = 1;
   left++;
   right--;
   }
   }
   }