مرتب‌سازی در حین خواندن از فایل

Question

یه فایل دارم که شامل تعدای عدد صحیح هست. می‌خوام در همون حالی که عددها رو از فایل می‌خونم در یک بردار (vector) بریزم ولی به صورت مرتب. نمی‌خوام مرتب‌سازی بعد از ریختن همه‌ی مقادیر به بردار انجام بشه.

هیچ پژوهش انسانی نمی‌تواند ادعای علمی بودن داشته باشد، مگر این‌که از برهان ریاضی برخوردار باشد (لئوناردو داوینچی)

Answer 1

کد زیر این کار و انجام می‌ده و مرتبه‌ی زمانی‌ش هم O(n^2) هست.

#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  vector<int> ordered;
  ifstream file("numbers.txt");
  int x; 
  while(file>>x)
    ordered.insert(lower_bound(ordered.begin(), ordered.end(), x), x);
  return 0;
}

در صورتی که بدونیم عنصر تکراری نداریم می‌تونیم از set استفاده کنیم.

#include <set>
using namespace std;

int main()
{
  set<int> ordered;
  ifstream file("numbers.txt");
  int x; 
  while(file>>x)
    ordered.insert(x);
  return 0;
}

اگه کد بالا رو به جای set با multiset بنویسیم مشکل تکراری‌ها هم حل می‌شه

#include <set>
using namespace std;

int main()
{
  multiset<int> ordered;
  ifstream file("numbers.txt");
  int x; 
  while(file>>x)
    ordered.insert(x);
  return 0;
}

استفاده از priority_queu به صورت زیر می‌شه این کار و کرد.

#include <queue>
using namespace std;

int main()
{
  priority_queue<int> ordered;
  ifstream file("numbers.txt");
  int x; 
  while(file>>x)
    ordered.push(x);
  return 0;
}

هیچ پژوهش انسانی نمی‌تواند ادعای علمی بودن داشته باشد، مگر این‌که از برهان ریاضی برخوردار باشد (لئوناردو داوینچی)