Finding K largest numbers using counting sort in unsorted array

S

Sam Beray

Guest
I am learning how to implement counting sort properly by doing some small online tasks. I wrote the code but it gives me segmentation fault for some reason. There is one testing input which can be seen:
n=6, k=4
8 9 5 1 4 2
n = number of prices
k = number of prices which I want to make sum of
So output for this case will be 26 (because 9+8+5+4)
But there is also one secret test where I dont see the input and when I try to test it, it gives "segmentation fault".

I tried to use malloc so I dont have to define MAX_BUFFER, but it did not help me.

int *countings;
int *sorted;

max = price[0];

for (i=1; i<n; i++) {
if (max < price) {
max = price;
}
}
countings = (int*)malloc(max * sizeof(int));
sorted = (int*)malloc(n * sizeof(int));


This is the full code

#include <stdio.h>
#include <stdlib.h>

#define MAX_BUFFER 100

long sum_of_k_biggest_numbers(int price[], int n, int k)
{
int max;
int i;
int countings[MAX_BUFFER];
int sorted[MAX_BUFFER];
int final_price = 0;

max = price[0];

for (i=1; i<n; i++) {
if (max < price) {
max = price;
}
}
for (i=0; i<n; i++) {
countings[price]++;
}
for (i=1; i<(max+1); i++) {
countings += countings[i - 1];
}
for (i=(n-1); i>=0; i--) {
sorted[--countings[price]] = price;
}
for (i=(n-1); i>=(n-k); i--) {
final_price += sorted;
}

return final_price;
}

int main(void)
{
int i, *x, n, k;

scanf("%d %d", &n, &k);
x = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++)
scanf("%d", &x);

printf("%ld\n", sum_of_k_biggest_numbers(x, n, k));
return 0;
}


Can anybody give me a hint or tell me, where might be the problem?

Continue reading...
 
Top