Подсчет сортировки для входного файла
У меня есть мой счетчик для работы с массивом, который я заполнил числами. Теперь я хочу сделать это, поэтому я беру информацию из входного файла. У меня будут входные файлы с очень большим количеством цифр (от 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;
Решение
Если вы имеете дело с целыми числами, и вы уверены в диапазоне, который составляет 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.
Для простых целых чисел стабильность вряд ли требуется. Таким образом, вы можете выбрать вышеупомянутую технику, чтобы быстро отсортировать ваши данные.
Другие решения
Других решений пока нет …