Laufzeit von STL vector sort()

Hallo!!

Habe da mal eine Frage. Was ist der Worst Case für vector sort und welcher Algorithmus wird da verwendet?

Merci

Caipi

http://www.cppreference.com/cppalgorithm/sort.html.

Btw: std::vector besitzt keine sort-methode.

Gruß Caipi

vector hat keine eigene sort-Funktion, ich nehme also an du meinst sort() aus
<algorithm>.
Für sort() schreibt der Standard eine AV-Komplexität von:
- O(n*log(n))
vor, aber nicht welcher Algorithmus verwendet werden MUSS. Die WC-Komplexität
kann daher nur für jede Implementierung extra angegeben werden.

ich denke mal es ist fast immer quick-sort.

Ich denke, es ist meistens ein Quicksort, der bei einer bestimmten Kleinheit des Teilintervalls dann einen anderen Algorithmus bemüht, z.B. InsertionSort.

volkard

warum glaubt ihr nicht wie im link angegeben an intro-sort?

Was schreiben die denn da für einen Müll auf cppreference.com? Das ist doch gar nicht im Standard vereinbart.

algorithm aus visual c++ 7.1 nutzt quicksort

sorry stimmt nicht so ganz. so weit ich sehe quicksort, heap sort und insertion sort

template<class _RanIt,
	class _Diff,
	class _Pr> inline
	void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
	{	// order [_First, _Last), using _Pred
	_Diff _Count;
	for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
		{	// divide and conquer by quicksort
		pair<_RanIt, _RanIt> _Mid =
			_Unguarded_partition(_First, _Last, _Pred);
		_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisions

		if (_Mid.first - _First < _Last - _Mid.second)	// loop on larger half
			_Sort(_First, _Mid.first, _Ideal, _Pred), _First = _Mid.second;
		else
			_Sort(_Mid.second, _Last, _Ideal, _Pred), _Last = _Mid.first;
		}

	if (_ISORT_MAX < _Count)
		{	// heap sort if too many divisions
		std::make_heap(_First, _Last, _Pred);
		std::sort_heap(_First, _Last, _Pred);
		}
	else if (1 < _Count)
		_Insertion_sort(_First, _Last, _Pred);	// small, insertion sort
	}

............ schrieb:

Was schreiben die denn da für einen Müll auf cppreference.com? Das ist doch gar nicht im Standard vereinbart.

Nochmal, der Standard gibt Komplexitätsgarantien, schreibt aber keine Implementierung vor.

volkard

.......... schrieb:

sorry stimmt nicht so ganz. so weit ich sehe quicksort, heap sort und insertion sort

schau mal ganz genau, ob es nicht doch introsort ist. introsort benutzt nämlich normalerweise quicksort, heap sort und insertion sort.

edit: naja, schau einfach nur auf die schleife

for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )

ja, der standfard definiert nur komplexitätsgarantien, aber das ändert nichts daran, daß man als user ruhig von introsort ausgehen sollte.

Jester

Jo, deswegen hat sich ...... ja auch gewundert, was da bei cppreference steht. Aber gut, daß Du dein nochmal Fett gesetzt hast.