my sorting algorith

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.
Congrats on discovering a variation of the Insertion Sort!
http://en.wikipedia.org/wiki/Insertion_sort

-Albatross
Last edited on
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;
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

Congrats on discovering a variation of the Insertion Sort!
http://en.wikipedia.org/wiki/Insertion_sort

-Albatross


but still, u got to admit that it is pretty efficient for arrays i desrcibed (and numbers occure only once)
but still, u got to admit that it is pretty efficient for arrays i desrcibed

Indeed its worst and best case complexity appear to be O(n). However, it's quite limited.

Upon further investigation, I found something similar that uses the same principle and is not limited to said arrays.
http://en.wikipedia.org/wiki/Counting_sort

Sorry. :)

-Albatross
Last edited on
On that wikipedia page, what does the constant k refer to? Obviously n is the amount of inputs... but what is k?
The length of the array C (the counting array).

-Albatross
Sorry. :)

well, but i still came up with that algorith like on hour or so before we learned about insertion sort, wierd ^^

Indeed its worst and best case complexity appear to be O(n). However, it's quite limited.

what do u mean quite limited, u mean like those limitations that i mentioned or new ones?
Topic archived. No new replies allowed.