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

2 Years
Discussion Span
Last Post by Hiroshe

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.

Edited by GuruJin


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

Edited by Dan_3


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;

    counter =0;
    for(int  i=0;i < str_len;i=i+2){

            char temp = str[i];


    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

Edited by GuruJin


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.

Edited by Dan_3


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;

Edited by Ilia_1


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

        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:
Your algorithm will read the 1111, say it's sorted, then read the 0000 and say it's sorted.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.