CODEWITHSUNDEEP
algorithmlistsortingbinary
letter Q
letter Q

Reputation: 15405

sorting a bivalued list

If I have a list of just binary values containing 0's and 1's like the following 000111010110 and I want to sort it to the following 000000111111 what would be the most efficient way to do this if you also know the list size? Right now I am thinking to have one counter where I just count the number of 0's as I traverse the list from beginning to end. Then if I divide the listSize by numberOfZeros I get numberOfOnes. Then I was thinking instead of reordering the list starting with zeros, I would just create a new list. Would you agree this is the most efficient method?

Upvotes: 1

Views: 381

Answers (3)

stratis bellos
stratis bellos

Reputation: 41

Bucket sort is a sorting algorithm as it seems.

I dont think there is a need for such operations.As we know there is no Sorting algorithm faster than N*logN . So by default it is wrong.

And all that because all you got to do is what you said in the very beginning.Just traverse the list and count the Zero's or the One's that will give you O(n) complexity.Then just create a new array with the counted zero's in the beginning followed by the One's.Then you have a total of N+N complexity that gives you O(n) complexity.

And thats only because you have only two values.So neither quick sort or any other sort can do this faster.There is no faster sorting than NLog(n)

Upvotes: 0

Tyler Durden
Tyler Durden

Reputation: 11562

If you have numeric values, you can use the assembly instruction bitscan (BSF in x86 assembly) to count the number of bits. To create the "sorted" value you would set the n+1 bit, then subtract one. This will set all the bits to the right of the n+1 bit.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726919

Your algorithm implements the most primitive version of the classic bucket sort algorithm (its counting sort implementation). It is the fastest possible way to sort numbers when their range is known, and is (relatively) small. Since zeros and ones is all you have, you do not need an array of counters that are present in the bucket sort: a single counter is sufficient.

Upvotes: 1

Related Questions