Counting Sort for input file

Question

I've got my counting sort to work with an array that I filled with numbers. Now I want to make it so I am taking the information from an input file. I will have input files with very large amounts of numbers (ranging from 0 - 4000). I will also have the number of items in that file given to me. How would I adjust this code to work for any input file?

    int array[10]={5,5,5,5,5,5,1,2,5,7};
    int count_array[10]={0};
    int sum=0;
    int new_array[10];
    int i;

    for(i=0;i<10;i++)
        count_array[array[i]]++;

    for(i=0;i<10;i++)
    {
        count_array[i]=count_array[i]+sum;
        sum=count_array[i];
    }

    for(i=0;i<10;i++)
    {
        new_array[count_array[array[i]]]=array[i];
        count_array[array[i]]--;
    }

    for(i=1;i<=10;i++)
    {
        cout<<new_array[i]<<" ";               
    }
    cout<<endl;

I do know that I will be using cin<< num_items to get the number of items in the file. But I wasn't sure on how to fill the array with the numbers from the file. I was thinking about using a while loop, however, I'm not entirely sure that would be correct — S. James, Nov 04 '15 at 03:56
Possible duplicate of [Read file line by line](http://stackoverflow.com/questions/7868936/read-file-line-by-line) — Greg, Nov 04 '15 at 04:11
The logic would be the same, except that the size of count_array would be 4001 (since the range is 0 to 4000). Also rather than move the numbers from array to new_array, the sum loop could be skipped and a double loop used to fill in new_array, writing count_array[i] instances of i for each element in count_array. — rcgldr, Nov 04 '15 at 06:47
And decision should be taken on the basis of expected data, if Input Size >> 4000(i.e. input size very large compared to 4000) counting sort is a viable option, otherwise quick sort is way to go — g-217, Nov 04 '15 at 09:56
Also see http://stackoverflow.com/questions/25001800/why-we-can-not-apply-counting-sort-to-general-arrays before you go ahead with implementations — g-217, Nov 04 '15 at 10:45

score 1 · Answer 1 · answered Nov 04 '15 at 11:11

If you are dealing with integers and you are sure about the range which is 0-4000 in your case.

Then you can safely ignore counting sort, and do something like counting the frequencies and you will end up sorting integers in file.

See following code, which sorts the input in constant space(4001*siz4eof(int)) and theta(N) time

#include <fstream>
#include <iostream>
#include <string>
#include <cstring>
#include <cassert>

#define MAX_VALUE 4001

int main()
{
    std::ifstream in("D:\\cprog\\file.txt");
    std::string line;
    int arr[MAX_VALUE];
    memset(arr,0,sizeof(arr));
    while(std::getline(in,line))
    {
        int a = std::stoi(line);
        assert(a<MAX_VALUE);
        arr[a] += 1; // counting frequency of a number
    }
    std::cout<<"Sorted result"<<'\n';
    for(int i = 0; i < MAX_VALUE ; ++i)
    {
        for(int j = 0 ; j < arr[i] ; ++j)
            std::cout<<i<<'\n';
    }
    return 0;
}

Counting sort is a stable sorting technique and provides base for sorting algorithm like Redix Sort algorithms.

For plain integers stability is hardly solicited. So you can choose above technique to quickly sort your input.

Counting Sort for input file

1 Answers1