Сортировка при чтении в вектор - PullRequest
Новая
       23

Сортировка при чтении в вектор

1 голос
/ 25 апреля 2011

Мне нужно прочитать список из 10000 целых чисел и поместить их в вектор в порядке возрастания.Обратите внимание, что я не читаю , затем сортирую, я сортирую , а читаю.

Я делаю это как учебное упражнение.Я понимаю, что сортировка при чтении - это O (n ^ 2), а при чтении, тогда сортировка может быть O (n + (n log (n)) с быстрой сортировкой или аналогичной.

Я сделал это вC Массив, но у меня проблемы с этим с вектором. Любой совет, как это сделать?

Заранее спасибо!

РЕДАКТИРОВАТЬ: Код массива C:

Чтобы полностью объяснить, у меня есть два класса: ArrayIntStorage и VectorIntStorage.

Весь смысл в том, что это учебное упражнение.

Каждый из этих классов имеетпеременная-член _data, один тип int [], а другой вектор.
Каждый класс имеет метод чтения и записи, это метод чтения для ArrayIntStorage 

void ArrayIntStorage::read(istream &sin)
{
string x;
sin >> x >> _numberOfInts;

_data = new int[_numberOfInts];

if(_sortRead)
{
    int i, j, index;
    sin >> _data[0];

    for(i = 1; i < _numberOfInts; i++)
    {
        sin >> index;

        j = i;
        while((j > 0) && (_data[j-1] > index))
        {
            _data[j] = _data[j - 1];
            --j;

        }
        _data[j] = index;
    }
}
else
{
    for(int i = 0; i < _numberOfInts; ++i)
    {
        sin >> _data[i];
    }
}   
}

Ответы [ 3 ]

5 голосов
/ 25 апреля 2011

пример времени: 

std::vector<int> target;

// reading
std::ifstream file("integers.txt");
int number; 
while (file >> number) 
{
  target.insert(std::lower_bound(target.begin(), target.end(), number), number);
}
1 голос
/ 25 апреля 2011

Я бы использовал multiset, чтобы сделать сортировку для меня: 

void VectorIntStorage::read(istream &sin) {
    multiset<int> ms;
    copy(istream_iterator<int>(sin), istream_iterator<int>(),
        inserter(ms, ms.end()));
    vector<int>(ms.begin(), ms.end()).swap(_data); 
}
1 голос
/ 25 апреля 2011

Я не скомпилировал его, но использование очереди приоритетов также возможно 

#include <queue>
#include <iostream>

    priority_queue<int> pq;
    // reading
    std::ifstream file("integers.txt");
    string line;
    while (getline(file, line))
    {
          int number = boost::lexical_cast<int>(line);

        pq.push (number);
    }

Согласно этот вопрос push () - O (log (N)), а pop - O(2 * log (N))

...