We should use counting sort.
There are only 256 key value, so aux array will have only 256 values, and in O(n) time and 2 passes we will be able to sort in efficient way.
Finding an integer that repeats odd number of times in an array of positive integers
Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?
Solutions
Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0.
[Read More]
Sorting Array of Three Kinds or The Dutch National Flag Problem OR three color sort
Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c). This problem is also called three color sort.
Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors.
[Read More]
Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .
for(int j=arrIndex/2 ; j < arrIndex;j++) …
shanky - Nov 0, 2014
for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}
This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i
Hi Shanky, you are right. That’s what I have done :)
Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .
Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach.
Approach 2 : Club binary search approach and array’s random access property
Since the array is infinitely increasing i.e. we don’t know array size in advance, so we can’t directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach).
[Read More]
Counting sort
Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.
It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
Example
For simplicity, consider the data in the range 0 to 9.
[Read More]
Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort
in your Pseudocode, the if condition should be if …
RM - May 3, 2014
in your Pseudocode, the if condition should be if (low < high).
Thanks Rish. I have made the change a[low] > a[high] rather than low < low. :). Thanks for correcting me.
Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort
Problem Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort.
Example Input - Binary unsorted array
A = {0,1,1,0,0,1};
Output - binary sorted array
B = {0,0,0,1,1,1}
Solution This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n).
[Read More]