pramod wrote:
> Can we change counting sort to sort inplace only using O(k) space where
> the numbers range from 1...k?
> The problem precisely is to design a sorting algorithm to sort 'n'
> records whose keys range from 1...k in O(n) time using only an
> auxiliary array of size k. The algorithm should sort be stable and
> should sort in-place. Remember that the original array is an array of
> records with integer keys. So simply copying the numbers won't do, we
> need to indeed swap the records.
> I know one place algo based on counting sort but it's not stable.
> Any solutions ?
Here is an unstable solution:
void sort(int *array, int n, int *aux, int k)
{
int i, s, s2;
for (i = 0; i < k; i++)
aux[i] = 0;
/* Set aux[i] to number of array entries equal to i.
** Negate each array entry as an "unprocessed" flag. */
for (i = 0; i < n; i++)
{
if (array[i] < k)
aux[array[i]]++;
array[i] = -array[i];
}
/* Set aux[i - 1] to index of first entry in sorted array
** equal to i. */
for (i = 2; i < k; i++)
aux[i] += aux[i - 1];
for (i = 0; i < n; i++)
{
s = array[i];
if (s > 0)
/* s is already in the right place */
continue;
s = -s;
/* Process one cycle of the permutation of the unsorted
** array to one of mutiple possible sorted arrays. */
while (i != aux[s - 1])
{
s2 = -array[aux[s - 1]];
array[aux[s - 1]++] = s;
s = s2;
}
array[i] = s;
aux[s - 1]++;
}
}
Here is a stable solution:
void sort(int *array, int n, int *aux, int k)
{
int i, s, s2, pos;
for (i = 0; i < k; i++)
aux[i] = 0;
/* Set aux[i - 1] to number of array entries equal to i.
** Negate each array entry as an "unprocessed" flag, and encode
** its position relative to other entries of the same key value.
*/
for (i = 0; i < n; i++)
array[i] = -(array[i] + (k + 1) * aux[array[i] - 1]++);
/* Set aux[i - 1] to index of first entry in sorted array
** equal to i. */
s = 0;
s2 = 0;
for (i = 0; i < k; i++)
{
s += aux[i];
aux[i] = s2;
s2 = s;
}
for (i = 0; i < n; i++)
{
s = array[i];
if (s > 0)
/* s is already in the right place */
continue;
/* Extract relative position and recover original key value. */
s = -s;
pos = s / (k + 1);
s %= (k + 1);
/* Process one cycle of the permutation of the unsorted
** array to the sorted array. */
while (i != (aux[s - 1] + pos))
{
s2 = -array[aux[s - 1] + pos];
array[aux[s - 1] + pos] = s;
s = s2;
pos = s / (k + 1);
s %= (k + 1);
}
array[i] = s;
}
}
I'd have a hard time formally proving that these algorithms are O(n),
but I'm pretty sure they are. They move each entry at most one
time.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
