Ringtausch, Kreuztausch ohne Datenverlust

[Horst]

hi 0xffffFFFF,

gegeben sind:
min, posmin
max, posmax

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? Das muss doch mit so einer Art Ringtausch gemacht werden oder so. Bitte mal helfe...

Viele Grüße,
Horst Haselhuhn

[Vinzenz Mai]

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.

Freundliche Grüße

Vinzenz

[Horst]

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).

[Vinzenz Mai]

Hallo Horst,

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
}
}

ein typisches MaxSort (auch wenn es hier eher ein MinSort ist).
Rekursiv macht man sowas natürlich nicht, sondern nutzt Iteration :-)

Ein Tauschen ist so ungefähr die erste Funktion, die man bei C schreibt, wenn man den Umgang mit Pointern lernt. Schau mal in Deine alten Unterlagen.

Sinngemäß:

nichts zurückgebende Funktion tauschen(Zeiger auf Zahl a, Zeiger auf Zahl b) {
    Wir brauchen einen Merker
    Schreibe den Inhalt, der an der Adresse von a steht, in den Merker
    Schreibe den Inhalt, der an der Adresse von b steht an die Adresse von a
    Schreibe den Inhalt des Merkers an die Adresse von b
}

Kriegste bestimmt hin ...

Und Effizienz kann bei einem nicht effizienten Algorithmus kein Argument sein. Das heißt es gibt _keinen_ Grund, keine Funktion dafür zu nehmen sondern Inline-Code. Ich persönlich fand HeapSort einen wundervoll eleganten und zugleich effizienten Sortieralgorithmus ...

Viel Spass bei Deinen Sortierfunktionen.

Freundliche Grüße

Vinzenz

[Horst]

Tja lieber Vinzenz,

es gibt zwei Möglichkleiten, entwerder hab ich hier zuviel geschrieben oder zuwenig, egal, schade, das wir hier nicht weiter kommen,

Hotte,

[Vinzenz Mai]

Hallo

es gibt zwei Möglichkleiten, entwerder hab ich hier zuviel geschrieben oder zuwenig, egal, schade, das wir hier nicht weiter kommen,

Hä?

Kannst Du Dich wirklich an solch elementare Dinge nicht mehr erinnern

void tauschen (int* a, int* b) {
    int merker;

/* Schreibe den Inhalt, auf den a zeigt, in den Merker */
    merker = *a;

/* Schreibe den Inhalt, auf den b zeigt, dorthin, worauf a zeigt */
    *a     = *b;

/* Schreibe den Inhalt des Merkers an die Stelle, auf die b zeigt */
    *b     = merker;

/* Nun sind die Inhalte von a und b vertauscht */
}

Du solltest vermeiden, nicht initialisierte Zeiger zu übergeben :-)
Ach so, nach dem gleichen Prinzip kannst Du inline tauschen:

int a = 5;
int b = 7;
int merker;

merker = a;
a      = b;
b      = merker;

Ja, das geht auch mit Arrayelementen. Wo ist das Problem?
C-Anfänger-Kurs!

Verständnislose Grüße

Vinzenz

[Horst]

Hallo

Ja, das geht auch mit Arrayelementen. Wo ist das Problem?
C-Anfänger-Kurs!

Du hast meine Posts nicht verstanden, das finde ich schade: Für _zwei_ Zahlen die Plätze tauschen, ist  keine Kunst, das zeigt meine Funktion weiter oben.

Verständnislose Grüße

Dito

[Vinzenz Mai]

Hallo Horst,

Du hast meine Posts nicht verstanden, das finde ich schade: Für _zwei_ Zahlen die Plätze tauschen, ist  keine Kunst, das zeigt meine Funktion weiter oben.

dann formuliere doch endlich verständlich, was Du überhaupt willst.
Ich habe doch in meiner ersten Antwort extra nachgefragt.

Du hast, soweit ich das sehe, zwei Tauschvorgänge:

Erstes Element des zu betrachtenden Bereiches mit dem kleinsten Element.
Letztes Element des zu betrachtenden Bereiches mit dem größten Element.

Für jeden einzelnen der Tauschvorgänge benötigst Du die drei Einzelschritte. Nein, Du kommst _nicht_ mit fünf Wertzuweisungen aus.

Freundliche Grüße

Vinzenz

[Horst]

hi 255.255.255.255

im Falle, dass hier eine Lösung herauskommt, ist das ein neuer Algorithmus für die Open-Source-Gemeinde und ein Fakt weniger für die Kollegen der Software-Patent-Fraktion.

--Hotte

[Vinzenz Mai]

Lieber optimistischer Hotte,

im Falle, dass hier eine Lösung herauskommt, ist das ein neuer Algorithmus für die Open-Source-Gemeinde und ein Fakt weniger für die Kollegen der Software-Patent-Fraktion.

Du hast in beiden Fällen n Durchläufe
Merkst Du Dir nur das Minimum, so hast Du je
Durchlauf im Mittel etwa n/2 weitere Aufrufe. Somit kommst Du auf O(n^2).
Merkst Du Dir Maximum und Minimum, so hast Du je Durchlauf im Mittel n/4 weitere Aufrufe. Somit kommst Du ebenfalls auf O(n^2).

Außerdem darfst Du Dir gerne sowas wie min-max-sort ansehen ...

Sei bitte nicht frustriert.

Tröstende Grüße

Vinzenz

[Vinzenz Mai]

Hallo Hotte,

im Falle, dass hier eine Lösung herauskommt, ist das ein neuer Algorithmus für die Open-Source-Gemeinde

diese Variante von SelectionSort hättest Du auch in Wikipedia finden können - nur eben nicht rekursiv, sondern sinnvollerweise iterativ implementiert, um den zusätzlichen Speicherbedarf auf dem Stack zu vermeiden.

Freundliche Grüße

Vinzenz

[Horst]

hi Vinzenz,

[..] nur eben nicht rekursiv, sondern sinnvollerweise iterativ implementiert, um den zusätzlichen Speicherbedarf auf dem Stack zu vermeiden.

Für diesen Hinweis danke ich Dir!! Klar, ich kann das auch iterativ machen...

Hotte

[Horst]

Mahlzeit,

Das ganze Geheimnis besteht in folgender Anweisung (hier in Perl, auch wenn ich mit c immer besser klarkomme, manchmal teste ich meine Funktionen zuerst in Perl):

posmax ist posmin, wenn max auf start stand

if($posmax == $start){$posmax = $posmin;}

damit gibts auch keinen Datenverlust ;-)

Viele Grüße an 255.255.255.255
Hotte

[Vinzenz Mai]

Hallo Horst,

Das ganze Geheimnis besteht in folgender Anweisung (hier in Perl, auch wenn ich mit c immer besser klarkomme, manchmal teste ich meine Funktionen zuerst in Perl):

posmax ist posmin, wenn max auf start stand

if($posmax == $start){$posmax = $posmin;}

könntest Du bitte erläutern, was diese Anweisung hier mit Deiner Fragestellung zu tun hat? Ich kann keinen Zusammenhang erkennen.

Freundliche Grüße

Vinzenz

[Horst]

hi Vinzenz,

Das ganze Geheimnis besteht in folgender Anweisung (hier in Perl, auch wenn ich mit c immer besser klarkomme, manchmal teste ich meine Funktionen zuerst in Perl):

posmax ist posmin, wenn max auf start stand

if($posmax == $start){$posmax = $posmin;}

könntest Du bitte erläutern, was diese Anweisung hier mit Deiner Fragestellung zu tun hat? Ich kann keinen Zusammenhang erkennen.

Gerne ;-)

Gaaanz von vorn:
gegeben sind:
min, posmin
max, posmax

min, max sind Ganzzahlen
posmin, posmax sind die Positionen von min, max in einem ZahlenArray [0], [1],...[n]

min soll auf die Position [start] und max auf die Position [ende] geschrieben werden. Wie kriege ich das ohne Datenverlust hin? ....

Also: Wenn ich min nach [start] schreibe, die Zahl, die auf [start] stand an posmin, passt alles noch.

Wenn ich danach jedoch das max nach [ende] schreibe und das was auf [ende] stand an posmax, krachts in dem Fall wo das max auf [start] stand. Hierbei wird [start], wo ich schon das min habe überschrieben.

Deswegen ist genau das zu prüfen:
if(posmax == start){posmax = posmin;}

Viele Grüße,
Hotte

Hier alles zusammen in c. Praktisch ein erweiterter Selection-Sort. Die Funktion wird nicht rekursiv, sondern iterativ aufgerufen. Das Array wird praktisch nur noch halbsovielmal durchlaufen.

/*************************************************************************/
// wie nSort, hier jedoch wird min UND max ermittelt, also performater
// keine Rekursion, Funktion muss iterativ aufgerufen werden!
void xSort(int * p, int start, int stop){
 int min = 2147483647; // oder 0xFFFFFFFF
 int max = -2147483647; // oder 0

int posmin;
 int posmax;

int i;
 for(i = start; i < stop; i++){
  if( p[i] < min ) {
   min = p[i];
   posmin = i;
  }
  if( p[i] > max ) {
   max = p[i];
   posmax = i;
  }
 }

// nun die Zahlen auf den richtigen Positionen ablegen
 // merke wert auf p[start]
 int wsta = p[start];
 p[start] = min;
 p[posmin] = wsta;

// posmax ist posmin, wenn max auf start stand
 if(posmax == start){posmax = posmin;}

// merke wert auf p[stop-1]
 int wsto = p[stop-1];

p[stop-1] = max;
 p[posmax] = wsto;

}
/*************************************************************************/
int main(){
 int i;
 int zn[] = {1,2,3,4,5,0,-1,-2};

int size = sizeof(zn)/sizeof(int);
 printf("zn hat %d Zahlen\n", size);

// iteration über xSort
 for(i = 0; i < size - i; i++){
  xSort(zn, i, size - i);
 }

for(i = 0; i < size; i++){
  printf ("%d\n", zn[i]);
 }

return 0;
}

[Horst]

Guggst Du was!?

mir doch egal. Falls es das schon gibt, mir auch egal. Ich für meinen Teil freue mich, dass ich den Algorithmus selbst hingekriegt habe. Unabhängig von dem, was es evntl. vorher schon gab.

Deswegen ist es legitim, das was ich gefunden habe, zu veröffentlichen.

Die Kollegen der Software-Patent-Fraktion sollten sich das heutige Datum vorsichtshalber mal merken :)

Hotte

[Henryk Plötz]

Moin,

void xSort(int * p, int start, int stop){
int min = 2147483647; // oder 0xFFFFFFFF
int max = -2147483647; // oder 0

Der kleinste Integer (wenn man von 4 Byte signed ints ausgeht) ist übrigens -2147483648. (Die Zahl hat auch die faszinierende Eigenschaft dass -((int)-2147483648) == -2147483648). Um solche Fallen zu vermeiden verwende doch einfach die Makros INT_MAX und INT_MIN aus limits.h.