какая сортировка лучше и почему?

[Petruha-nsk]

Доброго времени суток!

В своей бакалаврской работе столкнулся с такой проблемой: у меня есть структура

struct lineL{
	double T;
	int V;
	int C;
};

и есть массив-структуры: lineL *Table = new lineL[N];

Мне нужно отсортировать Table по возрастанию полей T (приоритет 1) и C (приоритет 2).

Например дано:
Table[0]: T=1.2, C=0
Table[1]: T=1.2, C=1
Table[2]: T=0.1, C=0
Table[3]: T=3.9, C=1

в отсортированном виде,мне нужно получить:
Table[0]: T=0.1, C=0
Table[1]: T=1.2, C=1
Table[2]: T=1.2, C=0
Table[3]: T=3.9, C=1

Рассматривал два способа сортировки:
1. Переопределил операцию сравнение для struct:

bool lineL::operator> (lineL temp){
		if(fabs(T-temp.T)<10e-14)
		{
			if(C > temp.C)
				return 0;
			else return 1;
		}
		else
			if(T > temp.T)
				return 1;
			else
				return 0;
	};

2. Использовал ДВАЖДЫ сортировку с включениями, сортируя сперва по значениям С,а потом по Т:

int i,j,G;
	lineL x;
	double c;

	for(i=1; i<N; i++){
		x = Table[i];
		G = Table[i].C;
		j = i-1;
		while(j>=0 && Table[j].C>G)
		{
			Table[j+1] = Table[j];
			j = j-1;
		}
		Table[j+1] = x;
	}

	for(i=1; i<N; i++){
		x = Table[i];
		c = Table[i].T;
		j = i-1;
		while(j>=0 && Table[j].T>c)
		{
			Table[j+1] = Table[j];
			j = j-1;
		}
		Table[j+1] = x;
	}

Два раза подряд сортировать одну и ту же таблицу - как-то бредово,а для переопределенного оператора сравнения скорость ниже,чем для двойного сравнения. Подскажите пожалуйста, как можно разрешить данную проблему.

---
Спасибо за внимание!

[EUGY]

А стандартно через qsort?
И вместо оператора определить функцию сравнения compare(void * elem1, void * elem2);

[Petruha-nsk]

А можно, пожалуйста, по подробнее об указанном Вами способе?

[EUGY]

Условно так:

#include <math.h>
#include <float.h>
#include <stdlib.h> 

struct lineL
{
	double T;
	int V;
	int C;
};


int lineLcompare (const void* arg1, const void* arg2)
{
	lineL * pLeft = (lineL *) arg1;
	lineL * pRight = (lineL *) arg2;

	if (fabs(pLeft->T - pRight->T) <= DBL_EPSILON)
	{
		if (pLeft->C > pRight->C)
			return 1;
		else if (pLeft->C < pRight->C)
			return -1;
	}
	else if(pLeft->T > pRight->T)
		return 1;
	else if(pLeft->T < pRight->T)
		return -1;

	return 0;
}


int main()
{
	const N = 10;
	lineL * Table = new lineL[N];
	//как-то рандомно заполнить
	//....
	//....

	// и отсортировать
	qsort(Table, N, sizeof(lineL), lineLcompare);
}

[Petruha-nsk]

Спасибо большое!

[Rififi]

Petruha-nsk

Мне нужно отсортировать Table по возрастанию полей T (приоритет 1) и C (приоритет 2).

Например дано:
Table[0]: T=1.2, C=0
Table[1]: T=1.2, C=1
Table[2]: T=0.1, C=0
Table[3]: T=3.9, C=1

в отсортированном виде,мне нужно получить:
Table[0]: T=0.1, C=0
Table[1]: T=1.2, C=1
Table[2]: T=1.2, C=0
Table[3]: T=3.9, C=1

какая-то странная сортировка.. в результирующем массиве элементы 1 и 2 имеют одинаковое значение T=1.2, а сортировка по полю "C" не соответствует тому, что было озвучено в условии.

если все это нужно не более, чем для какой-нибудь студенческой поделки, то можно воспользоваться способом выше - сортировка через qsort. А если все по-сурьёзному, тогда лучше выбирать профессиональные инструменты - как-то так:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/member.hpp>

namespace mi = boost::multi_index;

struct key {};

struct line
{
	line(double t, int v, int c) : T(t), V(v), C(c) {}

	double T;
	int V;
	int C;

	friend std::ostream& operator << (std::ostream& os, const line& l)
	{
		return os << "{ T:" << l.T << ", V:" << l.V << ", C:" << l.C << " }";
	}
};

typedef mi::multi_index_container<
	line,
	mi::indexed_by<
		mi::sequenced<>,
		mi::ordered_non_unique<
			mi::tag<key>,
			mi::composite_key<
				line,
				BOOST_MULTI_INDEX_MEMBER(line, double, T),
				BOOST_MULTI_INDEX_MEMBER(line, int, C)
	> > > > Container;

int main()
{
	Container v;

	v.push_back(Container::value_type(1.2, 0, 0));
	v.push_back(Container::value_type(1.2, 0, 1));
	v.push_back(Container::value_type(0.1, 0, 0));
	v.push_back(Container::value_type(3.9, 0, 1));

	typedef Container::index<key>::type Index;

	const Index& arr = v.get<key>();
	for (Index::const_iterator it = arr.cbegin(); it != arr.cend(); ++it)
	{
		std::cout << *it << std::endl;
	}	

	return 0;
}

проверка работы: http://liveworkspace.org/code/9f08b4...edabd6dac83b54

[SergeyCh]

Если без дополнительных библиотек -

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

struct MyStruct
{
        double T;
	int C;
	int V;

       MyStruct(double _T, int _C, int _V) : T(_T), C(_C),V(_V) {}
	
};

struct less_than_TandC
{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2)
    {
        return ((struct1.T == struct2.T)?(struct1.C < struct2.C):(struct1.T < struct2.T));
    }
};


int _tmain(int argc, _TCHAR* argv[])
{
	std::vector < MyStruct > vec;

	vec.push_back(MyStruct(1.2, 0, 0));
	vec.push_back(MyStruct(1.2, 1, 0));
	vec.push_back(MyStruct(0.1, 0, 0));
	vec.push_back(MyStruct(0.1, 1, 7));
	vec.push_back(MyStruct(3.9, 1, 8));
	vec.push_back(MyStruct(3.9, 0, 0));
	vec.push_back(MyStruct(3.9, 1, 5));
	vec.push_back(MyStruct(3.9, 0, 3));

	sort(vec.begin(), vec.end(), less_than_TandC());
	for (auto i=vec.begin(); i != vec.end(); ++i)
	{
             cout<<i->T<<endl;
	     cout<<i->C<<"\n"<<endl;
        }

	return 0;
}
}

[Petruha-nsk]

Вау. За такое отдельное огромное спасибо!