Сортировка подсчетом входного файла

У меня есть сортировка подсчета для работы с массивом, который я заполнил числами. Теперь я хочу сделать так, чтобы я брал информацию из входного файла. У меня будут входные файлы с очень большим количеством чисел (от 0 до 4000). Мне также будет предоставлено количество элементов в этом файле. Как мне настроить этот код для работы с любым входным файлом?

    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;

c++ file-io sorting counting-sort
person S. James    schedule 04.11.2015    source источник
comment
Пытались ли вы вообще узнать, как читать из файла?   -  person Scott Hunter    schedule 04.11.2015
comment
Я знаю, что буду использовать cin‹‹ num_items для получения количества элементов в файле. Но я не знал, как заполнить массив числами из файла. Я думал об использовании цикла while, однако я не совсем уверен, что это будет правильно   -  person S. James    schedule 04.11.2015
comment
Возможный дубликат Читать файл построчно   -  person Greg    schedule 04.11.2015
comment
Логика будет такой же, за исключением того, что размер count_array будет 4001 (поскольку диапазон от 0 до 4000). Кроме того, вместо того, чтобы перемещать числа из массива в новый_массив, можно пропустить цикл суммирования и использовать двойной цикл для заполнения нового_массива, записывая экземпляры count_array[i] i для каждого элемента в count_array.   -  person rcgldr    schedule 04.11.2015
comment
И решение должно быть принято на основе ожидаемых данных, если размер ввода ›› 4000 (т. е. размер ввода очень велик по сравнению с 4000), сортировка подсчетом является жизнеспособным вариантом, в противном случае можно использовать быструю сортировку.   -  person jha-G    schedule 04.11.2015
comment
Также см. stackoverflow.com/questions/25001800/, прежде чем приступить к реализации   -  person jha-G    schedule 04.11.2015

Ответы (1)


arrow_upward
1
arrow_downward

Если вы имеете дело с целыми числами и уверены в диапазоне, который в вашем случае составляет 0-4000.

Затем вы можете спокойно игнорировать сортировку подсчета и делать что-то вроде подсчета частот, и вы закончите сортировку целых чисел в файле.

См. следующий код, который сортирует ввод по времени constant space(4001*siz4eof(int)) и theta(N).

#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;
}

Сортировка подсчетом представляет собой stable sorting technique и обеспечивает основу для алгоритма сортировки, такого как алгоритмы сортировки Redix.

Для простых целых чисел стабильность вряд ли требуется. Таким образом, вы можете выбрать описанную выше технику для быстрой сортировки ввода.

person jha-G    schedule 04.11.2015