Sorting Binary Array with O(n) complexity

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

About Sharath

I am a passionate technologist, I have varied interests in Development, Testing and Maintenance phases of PDLC / SDLC. In my leisure I love to play with my daughter. I love eating out, hanging out with friends and reading blogs/articles.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s