C till C++

Ehm.. C++ är en utökning av C, så kod i C fungerar även i C++ (nästan alltid)

Snälla, int main inte void main! http://www.research.att.com/~bs/bs_faq2.html#void-main

Main ska vara int om man ska vara petig.

Edit: late

Om man vill göra det till ett "riktigt" C++-program så kan man använda STL:

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

void display(int d) { cout << d << ' '; }

int main(int argc, char * argv[])
{
        int     n;
        cout << "Ange antalet värden som skall sorteras: ";
        cin >> n;

        vector<int>     data(n);

        for (int i = 0; i < n; i++)
        {
                cout << "Ange värde nr: " << i << ' ';
                cin >> data.at(i);
        }

        sort(data.begin(), data.end());

        for_each(data.begin(), data.end(), display);
        cout << endl;

        return 0;
}

perga, bra initiativ med stl

Men jag tycker inte att det är fel bara för att man använder en vanlig array...

den är förövrigt snabbare än vector också...
vector är ju mer motiverad då man ska förändra listan, vid exempelvis sortering, push, pop, erase mm....
jag anser inte att det är mer "riktig" c++ bara för att man använder vector... bara lite smidigare
Men iofs, det är min åsikt...

Förövrigt, du var inte sugen på att köra for_each istället för din vanliga for-loop också? Iofs, hade kanske inte vart helt bra...

Du hade väl iaf kunnat använda en iterator?

Hur som helst, stl snyggade ju till koden rätt ordentligt

Om man använder vector utan att lägga till massor med push_back så det måste skapas mer utrymme, så är vector lika snabb som en vanlig array, tex att loopa igenom den osv.

Edit: cbd.setzer, om du kan c hyffsat bra kan du tex skaffa accelerated c++ så lär du dig använda c++ på ett bra sätt.

Direktåtkomst i en std::vector är lika snabb som i en vanlig array, om man använder sig av operatorn [ ]. Om man i stället använder sig av medlemsfunktionen .at() går det långsammare, men å andra sidan kontrollerar funktionen att man håller sig inom det allokerade minnesutrymmet. Man slipper m.a.o. segmenteringsfel.

Funktionen std::sort() använder sig av en optimerad quicksort-algoritm som är långt snabbare än något "hemma-bygge". Den bör alltså användas i alla sammanhang då något skall sorteras.

totoo: Jag använder iteratorerna .begin() och .end()! F.ö. ger det väl inte så mycket att använda en särskild iterator i en std::vector. Det hade säkert varit möjligt att använda en inmatningsfunktion också i for_each(), men jag orkade inte skriva den extra funktionen...

syftade på for-satsen bara...
aja, skitsamma, mer smaksak...

men visst ska man köra stl alltid... menade inget om det, ifall det var mig du skrev till

Nej. Jag benchmarkade precis matricks sort3 med std::sort. sort3 var väldigt mycket snabbare på att sortera 3 heltal. Så std::sort är inte alltid bäst.

http://forum.sweclockers.com/showthread.php?s=&postid=3984992...

hmm... är det så?
Lite oväntat...

Jaja, men oftast så sorterar man inte så jättemycket grejjer varje mainloop i sitt prog...

Är inte mycket jag gör varje frame i vårt nuvarande spelprojekt... Är väl bara alphasortering vad jag kommer på nu...

Jepp, STL är bra grejer. På det hela taget blir det ofta riktigt snygg kod med modern C++.

Bättre att omformulera till, använd std::sort i de flesta fall, men är det en flaskhals tex, så använder man något snabbare

Men när är den generellt långsam då?
Är det vid små listor såsom tre heltal?
Låt säga att den är snabbare på alla listor > 10 element så e det ju inget att gnälla över, då är ju koden grym...

Men om det finns många situationer då den inte är snabbast, då börjar jag allt bli lite nervös

Men ang om det är heltal eller flyttal eller nåt annat så spelar det knappast någon roll för mig, för jag tar alltid en funktion som parameteter som gör en viss jämförelse.
Så detta är ju väldigt individuellt...

Dom gör ju inte samma sak så...
Men det finns säkerligen snabbare algoritmer än std::sort ändå.

Nepp. Det jag ville visa var att std::sort inte är svaret på alla sorteringsfrågor. Den är generellt bra, men ska man göra något väldigt specifikt är det nog bättre att skriva en egen funktion.

Hehe, quicksort är inte bra på små mängder. Quicksort på tre element? Huh? Testa på 500 000 element så kommer merge och quick vara bäst (eller kanske radix som är O(n) med vissa krav).

Fast måste std::sort vara quicksort då? I tex vc 7.1 så används quicksort, heap sort eller insertion sort, beroende på storleken på listan.

Aha, jo, jag trodde du använde sort3 som ett exempel på en sorteringsalgoritm som är snabbare, iofs är den den, men gör en (nästan) helt annan sak.

Nä, det har du ju helt rätt i. Det finns bara ett krav om tidskomplexiteten [ANSI C++ Standard, 25.3.1.1].

Vad jag förstår så använder de flesta STL-implementationer av std::sort en quicksort-algoritm som är rekursiv ner till en viss nivå, och under den nivån används en insert-sort.

Om nu MS har kommit på en effektivare algoritm i sin implementering är de väl bara att gratulera.

Från algorithm som följer med vc 7.1

template<class _RanIt,
	class _Diff> inline
	void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
	{	// order [_First, _Last), using operator<
	_Diff _Count;
	for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
		{	// divide and conquer by quicksort
		pair<_RanIt, _RanIt> _Mid = _Unguarded_partition(_First, _Last);
		_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), _First = _Mid.second;
		else
			_Sort(_Mid.second, _Last, _Ideal), _Last = _Mid.first;
		}

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

template<class _RanIt> inline
	void sort(_RanIt _First, _RanIt _Last)
	{	// order [_First, _Last), using operator<
	_Sort(_First, _Last, _Last - _First);
	}

Combsort11 är snabb på många element, men inte snabbare än std::sort.

då jag tittar på Ereinions så blir man ju bara underbart påmind om den väldigt speciella kodstandard som används i sådana där syften...
Så jäkla skoj att spana runt i alla fina headers som följer med exempelvis msvc och titta hur koden är uppbygd, vad alla objekt heter osv