اولین بار است که به این وب‌سایت می‌آیید. راهنما را مطالعه کنید!
x
موسسه خیریه محک

شهر ریاضی بازی-ریاضی

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

+1 امتیاز
694 نمایش

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

هیچ پژوهش انسانی نمی‌تواند ادعای علمی بودن داشته باشد، مگر این‌که از برهان ریاضی برخوردار باشد (لئوناردو داوینچی)
پرسیده شده جمعه ۲۵ مرداد ۱۳۹۲ در C++ توسط prodo  

1 پاسخ

0 امتیاز

کد زیر این کار و انجام می‌ده و مرتبه‌ی زمانی‌ش هم 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;
}
هیچ پژوهش انسانی نمی‌تواند ادعای علمی بودن داشته باشد، مگر این‌که از برهان ریاضی برخوردار باشد (لئوناردو داوینچی)
پاسخ داده شده جمعه ۲۵ مرداد ۱۳۹۲ توسط prodo  
ویرایش شده جمعه ۲۵ مرداد ۱۳۹۲ توسط prodo