prove that a binary string can always be sorted using the above operation finite number of times

Question

Blockquote

I came across this problem on a competitive programming site : 'CodeChef'. I was given a binary string and I had to sort it using the following operation : "I could take any substring and reverse it". I solved the problem using my code but I am unable to prove that the string can always be sorted using the above operation finite number of times.

Problem : https://www.codechef.com/START46C/problems/SRTARR

Can anyone help me with it?

Answer 1

A bubble sort is proven to finish in a finite number of steps, and using the rule it is possible to swap two elements.

Answer 2

While the string is not sorted, at each step, reverse the part of the string from the leftmost $1$ to the rightmost $0$.

Example:
$00\underline{11010100100}\to 0000\underline{1001010}11 \to 00000\underline{10100}111\to 0000000\underline{10}1111\to 0000000011111$

This will take as many flips as there are blocks of $1$s initially not in place.