Problem
Sort an array which only has 0's and 1's. Do not use count sort.(Microsoft)
Solution
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using namespace std;
int* CreateOneZeroArray(int len)
{
int* arr = new int[len];
for(int i = 0; i < len; ++i){
arr[i] = rand() % 2;
}
return arr;
}
void SortOneZeroArray(int* arr, int len)
{
int i = 0;
int j = len;
while(i < j){
if(arr[i] == 0){
i ++;
}
else{
arr[i] = arr[--j];
arr[j] = 1;
}
}
}
int main(int argc, char* argv[])
{
srand(2);
for(int i = 1; i < 15; ++i){
int* arr = CreateOneZeroArray(i);
cout << "The array before sorting: " << endl;
copy(arr, arr + i, ostream_iterator<int>(cout, " "));
cout << endl;
SortOneZeroArray(arr, i);
cout << "The array after sorting: " << endl;
copy(arr, arr + i, ostream_iterator<int>(cout, " "));
cout << endl << endl;
}
return 0;
}
Output
The array before sorting:
1
The array after sorting:
1
The array before sorting:
0 0
The array after sorting:
0 0
The array before sorting:
1 0 0
The array after sorting:
0 0 1
The array before sorting:
0 1 1 0
The array after sorting:
0 0 1 1
The array before sorting:
1 1 0 0 1
The array after sorting:
0 0 1 1 1
The array before sorting:
1 1 1 0 1 1
The array after sorting:
0 1 1 1 1 1
The array before sorting:
1 1 1 1 0 0 0
The array after sorting:
0 0 0 1 1 1 1
The array before sorting:
1 0 0 1 0 1 1 0
The array after sorting:
0 0 0 0 1 1 1 1
The array before sorting:
1 0 0 1 0 0 0 0 1
The array after sorting:
0 0 0 0 0 0 1 1 1
The array before sorting:
0 1 1 1 0 0 0 1 0 0
The array after sorting:
0 0 0 0 0 0 1 1 1 1
The array before sorting:
1 0 1 1 1 1 0 0 1 0 0
The array after sorting:
0 0 0 0 0 1 1 1 1 1 1
The array before sorting:
0 0 1 0 1 1 1 1 1 0 1 0
The array after sorting:
0 0 0 0 0 1 1 1 1 1 1 1
The array before sorting:
0 0 1 1 1 0 0 0 1 0 0 1 0
The array after sorting:
0 0 0 0 0 0 0 0 1 1 1 1 1
The array before sorting:
1 1 1 1 1 1 0 0 0 1 0 1 1 1
The array after sorting:
0 0 0 0 1 1 1 1 1 1 1 1 1 1
Press any key to continue . . .