Welcome back, today am going to discuss about a solution I came up when solving a sorting problem given by my colleague. The problem statement is very simple and straight “* Sort an Array of Binary Digits, with O ( n ) complexity (without using extra memory)*”.

Frankly, I just started revising the Data structures and sorting algorithms, which I last heard 6 years back in my college. But, before going and trying to revise the sorting techniques, I wanted to invest some time, and try solving this simple problem on my own. And here is the result of my accomplishment.

“Note : I did implemented this algorithm in java, and you find the details in this repository. ”

##### Algorithm for sorting binary array :

**Input**: Data array of length n **Output**: Sorted array of Data

```
begin
var lastIndexOf_0 <- n-1
loop: index <- n-1 to 0 do
if data[index] = 0 then
lastIndexOf_0 <- index
break Loop
end if
end loop
var startpos <- 0
var endpos <- lastIndexOf_0
Label: Sort
if data[startpos] = 0 then
startpos <- startpos + 1
else
swap data[startpos] , data[endpos]
endpos <- endpos - 1
end if
if startpos < endpos then
goto Sort
else
return sorted data array
end
```

Advertisements