#include <iostream>
#include <fstream>
#include <string>
#include <windows.h>
#include <vector>
using namespace std;

struct table
{
	int bilet;// Номер билета
	string marshrut;// Маршрут
	string data; // Дата отправки
	int vagon; // Номер вагона
	int mesto; // Номер места
};

bool StrComp(string s1,string s2)
{
	int d1=0, d2=0,mon1=0,mon2=0,ye1=0,ye2=0;
	string sd1 = s1.substr(0,2);
	d1 = atoi(sd1.c_str());
	string sd2 = s2.substr(0,2);
	d2 = atoi(sd2.c_str());
	string m1 = s1.substr(3,2);
	mon1 = atoi(m1.c_str());
	string m2 = s2.substr(3,2);
	mon2 = atoi(m2.c_str());
	string y1 = s1.substr(6,4);
	ye1 = atoi(y1.c_str());
	string y2 = s2.substr(6,4);
	ye2 = atoi(y2.c_str());
	if(ye1>ye2)
	{
		return 1;
	}
	if(ye1==ye2)
	{
		if(m1>m2)
		{
			return 1;
		}
		if(m1==m2)
		{
			if(d1>=d2) return 1;
		}
	}
	if(ye1<ye2)
	{
		return 0;
	}
}

void BinSortV(vector<table> T)
{
	int i=0,j=0,l=0,r=0,m=0;
	table x;
	for( i=2;i<T.size();i++)
	{
		x=T[i]; l=1; r=i-1;
		while(l<=r)
		{
			m=(l+r)/2;
			if(x.vagon<T[m].vagon)
			{
				r = m-1;
			} else l=m+1;
		}
		for(j=i-1;j>l;j--)
		{
			T[j+1] = T[j];
		}
		T[l]=x;
	}
}

void BinSortD(vector<table> T)
{
	int i=0,j=0,l=0,r=0,m=0;
	table x;
	for( i=2;i<T.size();i++)
	{
		x=T[i]; l=1; r=i-1;
		while(l<=r)
		{
			m=(l+r)/2;
			if(StrComp(x.data,T[m].data)==0)
			{
				r = m-1;
			} else l=m+1;
		}
		for(j=i-1;j>l;j--)
		{
			T[j+1] = T[j];
		}
		T[l]=x;
	}
}

void QuickSortV(vector<table> s_arr, int first, int last)
{
	int i = first, j = last, x = s_arr[(first + last) / 2].vagon;

	do {
		while (s_arr[i].vagon < x) i++;
		while (s_arr[j].vagon > x) j--;

		if(i <= j) {
			if (i < j) swap(s_arr[i], s_arr[j]);
			i++;
			j--;
		}
	} while (i <= j);

	if (i < last)
		QuickSortV(s_arr, i, last);
	if (first < j)
		QuickSortV(s_arr, first,j);
}

void QuickSortD(vector<table> s_arr, int first, int last)
{
	int i = first, j = last; string x = s_arr[(first + last) / 2].data;

	do {
		while (StrComp(s_arr[i].data, x)==0) i++;
		while (StrComp(s_arr[i].data, x)==1) j--;

		if(i <= j) {
			if (i < j) swap(s_arr[i], s_arr[j]);
			i++;
			j--;
		}
	} while (i <= j);

	if (i < last)
		QuickSortD(s_arr, i, last);
	if (first < j)
		QuickSortD(s_arr, first,j);
}

void BubbleV(vector<table> s_arr)
{
  int a, b;
  int t;

  for(a=1; a < s_arr.size(); ++a)
    for(b=s_arr.size()-1; b >= a; --b) {
      if(s_arr[b-1].vagon > s_arr[b].vagon) {
        t = s_arr[b-1].vagon;
        s_arr[b-1] = s_arr[b];
        s_arr[b].vagon = t;
      }
    }
}

void BubbleD(vector<table> s_arr)
{
  int a, b;
  string t;

  for(a=1; a < s_arr.size(); ++a)
    for(b=s_arr.size()-1; b >= a; --b) {
      if(StrComp(s_arr[b-1].data ,s_arr[b].data)) {
        t = s_arr[b-1].data;
        s_arr[b-1] = s_arr[b];
        s_arr[b].data = t;
      }
    }
}

int main()
{
	ifstream in; // Поток in будем использовать для чтения
	ofstream out; // Поток out будем использовать для записи
	out.open("D:\input.txt");
	struct table t;
	setlocale(LC_ALL, "Russian");
	int k,i=1;
	cout<<"Введите количество строк таблицы: ";
	cin>>k;
	while (i<=k)
	{
		cout<<"Введите номер билета:\n";
		cin>>t.bilet;
		out<<t.bilet<<' ';
		cout<<"Введите маршрут:\n";
		SetConsoleCP(1251);
		cin>>t.marshrut;
		out<<t.marshrut<<' ';
		SetConsoleCP(866);
		cout<<"Введите дату отправки:\n";
		SetConsoleCP(1251);
		cin>>t.data;
		out<<t.data<<' ';
		SetConsoleCP(866);
		cout<<"Введите номер вагона:\n";
		cin>>t.vagon;
		out<<t.vagon<<' ';
		cout<<"Введите номер места:\n";
		cin>>t.mesto;
		out<<t.mesto<<'\n';
		i++;
	}
	out.close();
	out.open("D:\output.txt");
	in.open("D:\input.txt");
	int b,v,mes;
	string m,d;
	vector< table > T;
	while (!in.eof())
	{
		in>>b;
		in>>m;
		in>>d;
		in>>v;
		in>>mes;
		t.bilet=b;
		t.marshrut=m;
		t.data=d;
		t.vagon=v;
		t.mesto=mes;
		T.push_back(t);
	}
 int k1,k2;
 cout<<"Ввыберите ключ сортировки 3-Дата 4-Вагон:\n";
 cin>>k1;

 if (k1==3)
	 {	cout<<"Ввыберите тип сортировки 1-Бинарными вставками 2-Быстрая 3-Простого обмена\n";
		 cin>>k2;
		if (k2==1) BinSortD(T);
		if (k2==2) QuickSortD(T, 0, T.size()-1);
		if (k2==3) BubbleD(T);}
 if (k1==4)
	 {	cout<<"Ввыберите тип сортировки 1-Бинарными вставками 2-Быстрая 3-Простого обмена\n";
		 cin>>k2;
		if (k2==1) BinSortV(T);
		if (k2==2) QuickSortV(T, 0, T.size()-1);
		if (k2==3) BubbleV(T);}

 for (int i=0;i<T.size()-1;i++)
    {
     cout<<T[i].bilet<<' ';
	 out<<T[i].bilet<<' ';
     cout<<T[i].marshrut<<' ';
	 out<<T[i].marshrut<<' ';
     cout<<T[i].data<<' ';
	 out<<T[i].data<<' ';
     cout<<T[i].vagon<<' ';
	 out<<T[i].vagon<<' ';
     cout<<T[i].mesto<<'\n';
	 out<<T[i].mesto<<'\n';
    }
 out.close();
 in.close();
	system("PAUSE");

}