Suppose that n records have keys in the range from 1 to k.
if we use counting sort to we can do it in O(n+k) time and is stable but its not in place.
if k=2 it can be done in place but its not stable (using two variables to maintain the indexes in the array for k=0 and k=1)
but for k>2 i couldnt think of any good algo
We have sorting algorithms that can sort "n" numbers in O (n log n) time. Merge Sort and Heap Sort achieve this upper bound in the worst case, and Quick Sort achieves this on Average Case.
A sorting algorithm is said to be “in-place” if it does not use extra space for operations on the input. It may or may not require some small, non-constant extra space for manipulating the input. Some in-place unstable sorting algorithms can be made stable by altering their implementation to use extra space.
Each pass over n d-digit numbers then takes time (n + k). There are d passes, so the total time for radix sort is (dn + kd). When d is constant and k = O(n), radix sort runs in linear time.
Linear sorting: Radix sort. An important property of counting sort is that it is stable, numbers with the same value, appear in the output in the same order as they do in the input. For instance Heap sort is not stable.
First, let's rehash how counting sort works:
k
.Now the question is how to perform the final step in-place. The standard approach for an in-place permutation is to select the first element and swap it with the element that takes its correct position. This step is repeated with the swapped element until we hit a element that belongs in the first position (a cycle has been completed). Then the whole procedure is repeated for the elements at the second, third, etc. position until the whole array has been processed.
The problem with counting sort is that the final positions are not readily available but are computed by incrementing every bin's starting position in the final loop. In order to never increment the starting position twice for an element, we have to find a way to determine if an element at a certain position has been moved there already. This can be done by keeping track of the original starting position for every bin. If an element lies between the original starting position and the position for the next element of a bin, it has been already touched.
Here's an implementation in C99 that runs in O(n+k)
and requires only two arrays of size k
as extra storage. The final permutation step is not stable.
#include <stdlib.h>
void in_place_counting_sort(int *a, int n, int k)
{
int *start = (int *)calloc(k + 1, sizeof(int));
int *end = (int *)malloc(k * sizeof(int));
// Count.
for (int i = 0; i < n; ++i) {
++start[a[i]];
}
// Compute partial sums.
for (int bin = 0, sum = 0; bin < k; ++bin) {
int tmp = start[bin];
start[bin] = sum;
end[bin] = sum;
sum += tmp;
}
start[k] = n;
// Move elements.
for (int i = 0, cur_bin = 0; i < n; ++i) {
while (i >= start[cur_bin+1]) { ++cur_bin; }
if (i < end[cur_bin]) {
// Element has already been processed.
continue;
}
int bin = a[i];
while (bin != cur_bin) {
int j = end[bin]++;
// Swap bin and a[j]
int tmp = a[j];
a[j] = bin;
bin = tmp;
}
a[i] = bin;
++end[cur_bin];
}
free(start);
free(end);
}
Edit: Here's another version using only a single array of size k
based on Mohit Bhura's approach.
#include <stdlib.h>
void in_place_counting_sort(int *a, int n, int k)
{
int *counts = (int *)calloc(k, sizeof(int));
// Count.
for (int i = 0; i < n; ++i) {
++counts[a[i]];
}
// Compute partial sums.
for (int val = 0, sum = 0; val < k; ++val) {
int tmp = counts[val];
counts[val] = sum;
sum += tmp;
}
// Move elements.
for (int i = n - 1; i >= 0; --i) {
int val = a[i];
int j = counts[val];
if (j < i) {
// Process a fresh cycle. Since the index 'i' moves
// downward and the counts move upward, it is
// guaranteed that a value is never moved twice.
do {
++counts[val];
// Swap val and a[j].
int tmp = val;
val = a[j];
a[j] = tmp;
j = counts[val];
} while (j < i);
// Move final value into place.
a[i] = val;
}
}
free(counts);
}
Here is my code that runs in O(n+k) time and uses only 1 extra array of size k ( apart from the main array of size n)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(int argc, char const *argv[])
{
int n = atoi(argv[1]);
int k = atoi(argv[2]);
printf("%d\t%d",n,k);
int *a,*c;
int num,index,tmp,i;
a = (int*)malloc(n*sizeof(int));
c = (int*)calloc(k,sizeof(int));
srand(time(NULL));
for(i=0;i<n;i++)
{
num = (rand() % (k));
a[i] = num;
c[num]++;
}
printf("\n\nArray is : \n");
for(i=0;i<n;i++)
{
printf("\t%d",a[i]);
if(i%8==7)
printf("\n");
}
printf("\n\nCount Array is : \n");
for(i=0;i<k;i++)
{
printf("\t%d(%d)",c[i],i);
if(i%8==7)
printf("\n");
}
//Indexing count Array
c[0]--;
for(i=1;i<k;i++)
{
c[i] = c[i-1] + c[i];
}
printf("\n\nCount Array After Indexing is : \n");
for(i=0;i<k;i++)
{
printf("\t%d(%d)",c[i],i);
if(i%8==7)
printf("\n");
}
// Swapping Elements in Array
for(i=0;i<n;i++)
{
index = c[a[i]];
//printf("\na[%d] = %d, going to position %d",i,a[i],index);
c[a[i]]--;
if(index > i)
{
tmp = a[i];
a[i] = a[index];
a[index] = tmp;
i--;
}
}
printf("\n\n\tFinal Sorted Array is : \n\n");
for(i=0;i<n;i++)
{
printf("\t%d",a[i]);
if(i%8==7)
printf("\n");
}
printf("\n\n");
return 0;
}
Even this algo is not stable. All elements are in their reverse order.
P.s : keys are in the range 0 to (k-1)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With