• 1

Linear time algorithm to sort an array of two distinct elements
  • lineartime
  • sorting
  • basicsorting
  • array
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (5958)

Suppose you are given an array of n elements containing two distinct keys - 0 and 1. How will you design a linear time algorithm to sort the array.


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

(Method 1) :: Using constant storage


  • Take an integer countZero set to 0 .
  • Iterate through the array from the beginning to end. If the value at the current index is 0 , increment countZero by 1 .
  • Print 0 from array[0] to array[countZero - 1] and 1 from array[countZero] to the end.

Calculating countZero and printing the array both takes \( O(n) \) time.
Therefore, time complexity of the algorithm = \( O(n) + O(n) = O(n) \).

public static void sortZeroAndOne(int[] array, int n){
      int countZero = 0;
      /* Counting the zero's */
      for(int i = 0;i  <  n;i++){
           if(array[i] == 0)
           countZero++;
      }
      /* Printing the sorted array */
      for(int i = 0; i  <  countZero; i++)
            array[i] = 0;
      for(int i = countZero; i  <  n; i++)
            array[i] = 1;
}



(Method 2) :: Without using storage

  • Take two pointers low and high .
  • Move low from the beginning of the array and high from the end of the array until they encounter 1 and 0 respectively. If encountered, swap the elements at the two pointers.
  • Repeat last step until the two pointers cross each other.

Since the two pointers move towards each other from the two end points and the algorithm ends when they cross, running time of the algorithm = \( O(n) \).

public static void sortZeroAndOne(int[] array){
    int low = 0;
    int high = array.length -1;
    while(low  <  high){
      if(array[low] == 0)
       low++;
      elseif(array[high] == 1)
       high--;
      else{
       swap(array, low, high);
       low++;
       high--;
      }
    }
		
}

public static void swap(int[] arr, int l, int h){
    int temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
}
You need to Sign In to post your solution.