nicht angemeldet
Hallo,
min, max sind Ganzzahlen
posmin, posmax sind die Positionen von min, max in einem ZahlenArray [0], [1],...[n]min soll auf die Position [0] und max auf die Position [n] geschrieben werden. Wie kriege ich das ohne Datenverlust hin?
Und wohin sollen die Zahlen von Position [0] und [n] geschrieben werden.
Spezifiziere Dein Problem bitte etwas genauer.Gegebenenfalls benötigst Du einen Merker.
Genau das ist ja meine Frage ;-)
Idee??
--Hotte
PS: Es geht um einen Sortier-Algorithmus. Ich habe einen solchen entwickelt, wo ein Zahlen-Array der Größe n lediglich (n-1) mal durchlaufen werden muss. Dabei wird jeder Durchlauf (rekursiv) jeweils um (n-1) kürzer.
Um das mal in c auszudrücken:
/*************************************************************************/
// hier die Sortierfunktion
// Die Funktion durchläuft das Zahlenarray
// im ersten Durchlauf ab 0, im Zweiten ab 1 usw.
// Bei jedem Durchlauf wird das Minimum ermttelt
// Das Minimum kommt auf Pos.0 und das was auf Pos.0 stand auf die Pos. wo das Minimum stand
void nSort(int * ar, int start, int stop){
unsigned long min = 0xFFFFffff; // größter anzunehmender Wert
int posmin;
int i;
for(i = start; i < stop; i++){
if( ar[i] < min ) {
min = ar[i];
posmin = i;
}
}
// Plätze tauschen ;-)
unsigned long meta = ar[start];
ar[start] = min;
ar[posmin] = meta;
start++;
if( (stop - start) > 0){
nSort(ar, start, stop); // Rekursiver Aufruf
}
}
/*************************************************************************/
Die Funktion geht richtig gut, aber warum nur nach dem Minimum schauen?
Die Rekusion macht
nSort(*a, 0, size);
nSort(*a, 1, size);
usw.
Ich habe o.g. Funktion umgeschrieben, so dass vom Maximum her sortiert wird, das geht auch.
Also könnte es doch einen Performance-Schwung geben wenn statt
nSort(*a, 0, size);
nSort(*a, 1, size);
usw.
die Rekursion nach
nSort(*a, 0, size);
nSort(*a, 1, size-1);
usw.
geht. Bei jeder Rekursion also, wird das Array nicht nur um (n-1) durchlaufen, sondern um (n-2).