Count sort in C could only sort first 4 numbers

Question

I am just working for a C programm using counting sort to sort numbers, here is my code, and I am using a external txt file for input. and the library arrayio.h is a given code for input.

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

int MAX_LAENGE = 1000;
int MAX_VALUE = 100;
int i,j,k;

void count_sort_calculate_counts(int input_array[], int len, int count_array[]) {
    for (i=0; i<len;i++) {
        count_array[i] = 0;
    }
    for (j=0; j<len;j++) {
        count_array[input_array[j]] = count_array[input_array[j]] + 1;
    }
}

void count_sort_write_output_array(int output_array[], int len, int count_array[]) {
    k=0;
    for (j=0;j<len;j++) {
        for (i=0; i<count_array[j]; i++) {
            output_array[k] = j;
            k = k + 1;
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc < 2){
        printf("Aufruf: %s <Dateiname>\n", argv[0]);
        printf("Beispiel: %s zahlen.txt\n", argv[0]);
        exit(1);
    }
    char *filename = argv[1];

    int input_array[MAX_LAENGE];
    int len = read_array_from_file(input_array, MAX_LAENGE, filename);

    printf("Unsortiertes Array:");
    print_array(input_array, len);

    int count_array[MAX_LAENGE];
    int output_array[MAX_LAENGE];
    count_sort_calculate_counts(input_array, len, count_array);
    count_sort_write_output_array(output_array, len, count_array);

    printf("Sortiertes Array:");
    print_array(output_array, len);
    return 0;
}

My problem is that when I run this program, it returns only the first 4 numbers. for example, when I input:

90 38 42 34 8 0 77 1 84 5 25 72 44 42 90 63 23

It returns:

0 1 5 8 0 0 0 0 0 0 0 0 0 0 0 0 0

Also, note that the count_array only needs MAX_VALUE items — Antti Haapala
– Antti Haapala, Commented Nov 15, 2017 at 22:47

Sergey Kalinichenko · Accepted Answer · 2017-11-15 19:45:09Z

1

The error is in the code that distributes the counts back to the output array. You end iterations of counts upon reaching the length of the original array, while you should be ending it when you reach the max value:

void count_sort_write_output_array(int output_array[], int len, int count_array[]){
    k=0;
    for (j=0;j<MAX_LAENGE;j++)
    {
        for (i=0; i<count_array[j]; i++)
        {
            output_array[k++] = j;
        }
    }
}

Demo.

To earn some "points for style" consider hiding the array of counts inside a single sorting function that computes counts and distributes the values back to the output array. After all, counts is an intermediate result that should be of no interest to users of your code, so you should not ask users of your sorting function to allocate it.

answered Nov 15, 2017 at 19:45

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Count sort in C could only sort first 4 numbers

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related