sort string of 0 and 1

[Dan_3]

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
help please....

[GuruJin]

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.

[vmanes]

aka Bubble Sort

[Hiroshe]

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.

[Dan_3]

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

[GuruJin]

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

[Dan_3]

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

[Hiroshe]

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

[Ilia_1]

#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;
}

[GuruJin]

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 

[Hiroshe]

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.