Hey guys, while in my algorithm and data structure class, we where learning about sorting algotithm, and this one just poped in my head, and i want ur opinion on it.
We have an array of numbers from 0 to n, and there are no gaps between numbers like "1, 2, 7, 50...".
lets assume we have an array of these numbers in this order:
4 7 1 3 2 5 8 9 6
OK, now we make another array of the same size and put the number 4 in the fouth place of the new array, number 7 in the seventh place, number 1 in the first place etc.
Now, because of the glory of the C++ language, we can use pointers to make all arrays, so when we are done sorting, we can delete the first array to save memory.
The complexity of the algorith is O(n) in the BigO notation.
This method CAN be used whit arrays whit the said gap, but then we need to find the biggest number, make a new array with mex elements as that number, and do as i said above, but we will have an surplus in elements of that array, so we make a new array, and put the elements from the second array in in as they come, ater that we delete the previous 2 arrays and we are done.
The problem is that if we have lets say this:
1 4 6 10000...
then the second array needs to be 10000 ellements long, and thats not very good.
Each number may occur more than once when also counting the number of occurrences:
1 2 3 4 5 6 7
int array[]={4,7,1,3,2,5,8,9,6,4,8,5,3,4,5,3,1,4,1,5,9,2};
constint arraySize=sizeof(array)/sizeof(*array);
constint numberLimit=10;
int occurrences[numberLimit]={0};
for (int i=0;i<arraySize;i++)occurrences[array[i]]++;
int cpos=0;
for (int i=0;i<numberLimit;i++)for (int c=0;c<occurrences[i];c++)array[cpos++]=i;
Each number may occur more than once when also counting the number of occurrences:
1
2
3
4
5
6
7
int array[]={4,7,1,3,2,5,8,9,6,4,8,5,3,4,5,3,1,4,1,5,9,2};
const int arraySize=sizeof(array)/sizeof(*array);
const int numberLimit=10;
int occurrences[numberLimit]={0};
for (int i=0;i<arraySize;i++)occurrences[array[i]]++;
int cpos=0;
for (int i=0;i<numberLimit;i++)for (int c=0;c<occurrences[i];c++)array[cpos++]=i;
hmmm... my way wont work for numbers that occure more than once, i guess