I'm trying to understand sorting algorithms. And I'm thinking about a totally different way to tackle sorting: Use array indexes to sort a given set of integers.
Suppose We want to sort a list of positive integers (for now). Let's call it toSortArray
- Create a boolean array that has a length equal to maximum integer in
toSortArray
+ 1. Lets call itboolArray
. All items in the array arefalse
initially. - Loop through
toSortArray
and for each integer item, set the boolean at index itemtrue
:boolArraty[toSortArray[i]] = true;
- Loop through
boolArray
and ifboolArray[i]
istrue
, set the first element oftoSortArray
toi
Here is the pseudo-code if the algorithm is not clear:
var boolArray = new bool[toSortArray.Max() + 1];
for (int i = 0; i < toSortArray.Length; i++)
{
boolArray[toSortArray[i]] = true;
}
var index = 0;
for (int i = 0; i < boolArray.Length; i++)
{
if (boolArray[i])
{
toSortArray[index] = i;
index++;
}
}
First, Does every body agree that time complexity is O(N)?
Second, Am I missing something about this algorithm (As I don't think I'm the first one thinking about it)?