there is string of 0 and 1.
The goal is to sort it. 2 pairs can be switched on each step.
For example the mentioned above string can be sorted in following steps:
0. 00010111010
1. 00001111100
2. 00000011111

well say sting of length n (n positive)
you will loop n/2 times
in each time you will compare character i and character i+1 if i > i+1
character '0' is 48 and character '1' is 49
if true then u will swap values (using a temp container)

now the whole thing is in a loop u can add a flag if condition i > i+1 false then stop sorting but only if the end of the loop is reached with no change.

aka Bubble Sort

Just count the # of 1's. Overwrite the trailing characters in the string with that many 1's, and overwire the remining characters with that many 0's. Works in O(n) time. Basically, it's a simplified counting sort.

thanks for kind attention, but
2 pairs can be switched on each step.
help, p.s

this is a roughly written code u will have to modify it .. and optimize it.

``````char[] str = "000101110100"
int str_len = 12;
bool flag =true;
int counter =0;
char temp;

while(flag){
counter =0;
for(int  i=0;i < str_len;i=i+2){
if(str[i]>str[i+1]){

char temp = str[i];
str[i]=str[i+1];
str[i+1]=temp;

}else
counter++;
}

if(counter ==6)
flag = false;
}
``````

if it is not what you were asking i suggest you either re-phrase, or support your problem with examples

two pairs(`11` `00`,result is `00` `11`) switched on each step, in your code switch only 2 symbols,
thanks for kind attention,

Ah, I see.

Start by having a counter that keeps track of how many adjacent 1's you have at the back of the string.
Ie, `00110101111` => adjacent 1's = 4.

Try to find a pair that is `11`. Swap that in front of the adjacent 1's and increment the counter by 2.
Ie, `100110101111` => `100100111111`. Do this until there are non remaining.

Try to find a pair that is `01`. Swap that in front of the adjacent 1's and increment the counter by 1. If the `01` is one character away from the adjacent 1's, you'll need to swap it forwards first.
Ie, `100010111111` => `101000111111` => `100001111111`. Do this until there are non remaining.

If the string starts with a `10`, swap it backwards, and move the resulting `01` in front of the adjacent 1's and increment the counter by 1. Ie, `100001111111` => `001001111111` => `000011111111`.

This run's in O(n^2) operations average I beleive. I think there exists an algorithm that runs in O(n) operations however.

GuruJin, have you ever heard the saying "give a man a fish, feed him for a day; teach a man how to fish, feed him for a life time"? Giving away code will rarely help people understand programming, as most of them will just copy it and not bother understanding it

``````#include <iostream>
#include <string>
using namespace std;
int main()
{
string str, str0="", str1="";
cin >> str;
for(int i=0; i<str.size(); ++i){
if(str[i] == '0') str0 += str[i];
else str1 += str[i];
}
cout << str0 + str1 << endl;
}
``````

in such case u would read them four by four ...

``````char a1, a2 , b1, b2;
str new_str ="";
a1 <- i
a2 <- i+1
b1 <- i+2
b2 <- i+3

if (a1 > b1)
then new_str = b1,b2,a1,a2

else if (a1 == b2 && a2>b2)
then new_str = b1,b2,a1,a2

else
new_str = a1,a2,b1,b2

add 4 to i and move forward till you reach the end
``````

That algorithm won't work. Simple counter example:
`11110000`
Your algorithm will read the `1111`, say it's sorted, then read the `0000` and say it's sorted.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.