Sortieren

Hallo !
Ich hab hier 2 funktionen zum sortieren eines 1dimensionalen Integer-Array.

void sort(int *array, int size)
{
	for(int i = 0; i < size; ++i)
	{
		for(int iCounter = 0; iCounter < size-1; ++iCounter)
		{
			if(array[iCounter] > array[iCounter+1])
			{
				int temp = array[iCounter];
				array[iCounter] = array[iCounter+1];
				array[iCounter+1] = temp;
			}
		}
	}
}

void sort2(int *array, int size)
{
	int *sortarray = new int[size];

	for(int counter = 0; counter <= size; ++counter)
	{
		int max = 0;
		int temp = 0;

		for(int i = 0; i < size; ++i)
		{
			if(array[i] > max)
			{
				max = array[i];
				temp = i;
			}
		}

		sortarray[size-counter] = max;
		array[temp] = 0;
	}

	for(int counter = 0; counter < size; ++counter)
	{
		array[counter] = sortarray[counter];
	}
}

Die erste Funktion funktioniert auch, bei der 2ten hab ich allerdings ein Problem...wahrscheinlcih ein logik-fehler.
und zwar steht an stelle array[0] der wert 0 was falsch ist. Der grösste wert aus dem array wird nicht einsortiert sondern gelöscht.
Ausserdem wuerd mich interessieren welche Funktion von beiden schneller/geschickter ist.
Danke schonmal im voraus !

Chew-Z

Schneller ist bestimmt std::sort, das man ja bekanntermassen auch auf
handelsübliche arrays anwenden kann.

Ixtana

Steigert aber nicht gerade den Lerneffekt

leo aka qsch

kein_name schrieb:

Ausserdem wuerd mich interessieren welche Funktion von beiden schneller/geschickter ist.
Danke schonmal im voraus !

das kann man so einfach nicht sagen, das kommt auf
- die groesse des zu sortierenden Arrays
- den worst bzw best case an (d.h. ob sich die Elemente schon im sortierten Zustand befinden oder nicht)

weiters wuerde ich dir empfehlen, zeiger-arithmetik anzuwenden, da der Zugriff ueber Zeiger eine bessere Performance bietet als der Zugriff per Index-Operator

btw: welches Sortierverfahren wendest du eigentlich bei der funktion sort2 an?

leo aka qsch schrieb:

das kann man so einfach nicht sagen, das kommt auf
- die groesse des zu sortierenden Arrays
- den worst bzw best case an (d.h. ob sich die Elemente schon im sortierten Zustand befinden oder nicht)

weiters wuerde ich dir empfehlen, zeiger-arithmetik anzuwenden, da der Zugriff ueber Zeiger eine bessere Performance bietet als der Zugriff per Index-Operator

btw: welches Sortierverfahren wendest du eigentlich bei der funktion sort2 an?

als test hab ich meistens eine array grösse von 10 benutzt...mit zeigern werd ich mal ausprobieren. Wie die Sortierverfahren heissen, weiss ich nicht...hab mir die selber überlegt...der erste ist bubble-sort oder?
Vielleicht löst sich mein Problem ja auch, wenn ich Zeiger anwende..mal sehen.
Danke schonmal.

fletscher

wie meinst du das mit zeiger-arithmetik?

so etwa

int array[] = "1,2,3,4,5,6,7,8,9,0";
int* ptr = array;

....
...

//if(array[iCounter] > array[iCounter+1])
//einfach ein
if(ptr[iCounter] > ptr[iCounter+1])

// oder gar ein

int* iCounter;
....

if(ptr[iCounter] > ptr[iCounter+1])

Shade Of Mine

leo aka qsch schrieb:

weiters wuerde ich dir empfehlen, zeiger-arithmetik anzuwenden, da der Zugriff ueber Zeiger eine bessere Performance bietet als der Zugriff per Index-Operator

[/quote]

Wir leben nicht mehr in der Steinzeit

leo aka qsch

fletscher schrieb:

wie meinst du das mit zeiger-arithmetik?

zb:

int array[] = {1,2,3,4,5,6,7,8,9,0};
int* ptr = array;
uint count = 4;

if(*ptr < *ptr+count)
	std::cout << *ptr << " < " << *ptr+count;

es ist zwar schwerer lessbar, doch bei der Implementation von Sortieralgorithmen sollte die Performance doch weit im Vordergrund stehen.

@shade: was hast du den gegen zeiger?

mata

leo aka qsch schrieb:

@shade: was hast du den gegen zeiger?

der compiler wirds schon richten, dadurch das du zeiger in deinen sourcecode schreibst, wirds wohl kaum schneller

evilissimo

leo aka qsch schrieb:

@shade: was hast du den gegen zeiger?

Shade wird bestimmt nix gegen Zeiger haben, aber das Optimierung auf die man heutzutage auch verzichten kann.

Oder willst du mir erzählen das du auf nem 3 GHz Boliden den unterschied bemerkst, ob er Zeigerarimethik benutzt hat um performance heraus zukitzeln oder nicht?

Ich glaub es nicht.

MfG

//Edit: NEIN und ich bin nicht gegen Optimierung. Alles schön und gut, nur an der richtigen stelle bitte.

ness

Ich würde sagen, dass ist geschmackssache und hat nichts mit optimierung zu tun...
Ich mag Zeigerarithmetik auch mehr...