therajat08

o and 1 segregation with single scan

Oct 12th, 2019
23
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C++ program to sort a binary array in one pass  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. /*Function to put all 0s on left and all 1s on right*/
  6. void segregate0and1(int arr[], int size)  
  7. {  
  8.     /* Initialize left and right indexes */
  9.     int left = 0, right = size-1;  
  10.  
  11.     while (left < right)  
  12.     {  
  13.         /* Increment left index while we see 0 at left */
  14.         while (arr[left] == 0 && left < right)  
  15.             left++;  
  16.  
  17.         /* Decrement right index while we see 1 at right */
  18.         while (arr[right] == 1 && left < right)  
  19.             right--;  
  20.  
  21.         /* If left is smaller than right then there is a 1 at left  
  22.         and a 0 at right. Exchange arr[left] and arr[right]*/
  23.         if (left < right)  
  24.         {  
  25.             arr[left] = 0;  
  26.             arr[right] = 1;  
  27.             left++;  
  28.             right--;  
  29.         }  
  30.     }  
  31. }  
  32.  
  33. /* Driver code */
  34. int main()  
  35. {  
  36.     int arr[] = {0, 1, 0, 1, 1, 1};  
  37.     int i, arr_size = sizeof(arr)/sizeof(arr[0]);  
  38.  
  39.     segregate0and1(arr, arr_size);  
  40.  
  41.     cout << "Array after segregation ";  
  42.     for (i = 0; i < 6; i++)  
  43.         cout << arr[i] << " ";  
  44.     return 0;  
  45. }
RAW Paste Data