InsertSort

freakC++

Hallo zusammen,
ich habe folgenden Code, der auch funktioniert. Der Einfachhalt halber istt "arr" ein globales Array mit fünft Elementen. Es geht darum, diese zu sortieren, aber ich verstehe nicht so ganz, warum der Code funzt:

void insertionSort(void)
{
  int temp=0,j=0;

  for (int i = 0; i < 5; ++i)
  {
    temp = arr[i]; // arr[5]={5,4,3,2,1};
    for (j = i; j > 0 && arr[j - 1] > temp; --j) //arr[j-1] = -1 
    {
      arr[j] = arr[j - 1];
    }
    arr[j] = temp;
  }
}

Ein Element -1 gibt es doch gar nicht? Wenn ich bei der äußeren Schleife i mit 1 starte, funktioniert die Funktion auch.

Wo liegt mein Denkfehler?

Vielen Dank für eure Hilfe!
lg, freakC++

volkard

bei
j > 0 && arr[j - 1]
wird
arr[j - 1]
nur angefaßt, wenn j>0

http://de.wikipedia.org/wiki/Kurzschlussauswertung

freakC++

Hallo,
ahh...wie konnte ich das übersehen *schäm*. Danke trotzdem. Dennoch habe ich ein anderes Problem. Damit ich den Algorithmus besser verstehe, habe ich mir mal systematisch die Schritte aufgeschrieben, doch an einer Stelle hänge ich. Also, ich habe das folgende Array, das zu sortieren ist:

int arr[5]={5,4,3,2,1}; //global nur aus Einfachkeit)
void insertionSort(void) //keine Parameter --> ich weiß ;)
{
  int temp=0,j=0;

  for (int i = 0; i < 5; ++i)
  {
    temp = arr[i]; // arr[5]={5,4,3,2,1};
    for (j = i; j > 0 && arr[j - 1] > temp; --j)
    {
      arr[j] = arr[j - 1];
    }
	if (i==2) cout <<arr[1] << endl;arr[j] = temp;
  }
}

Folgende Schritte habe ich mir dazu aufgeschrieben:

i=0:
temp=5;
keine Schleife
arr[0]=5 //keine Veränderung

i=1
temp=4
Schleifenbedingung erfüllt(5>4)
arr[1]=5 //arr[1]=arr[0]
arr[0]=4

i=2
temp=3
Schleifenbedingung erfüllt(5>3)
arr[2]=5 //arr[2]=arr[1]
arr[0]=temp //und was passiert mit der 4

Zwischenstand:
arr[3,

Ich wollte nun den Zwischenstand aufschreiben,also wie das Array jetzt aussieht, doch sieht es für mich aus, als ob die 4 (arr[0] aus i==2) einfach überschrieben wird. Tatsächlich wird sie aber in arr[1] geschrieben. Warum?? Wo steht dieser Schritt?

Könnt ihr mir helfen?

Vielen Dank
lg, freakC++

SeppJ

freakC++ schrieb:

i=2
temp=3
Schleifenbedingung erfüllt(5>3)
arr[2]=5 //arr[2]=arr[1]
arr[0]=temp //und was passiert mit der 4

Zwischenstand:
arr[3,

Ich wollte nun den Zwischenstand aufschreiben,also wie das Array jetzt aussieht, doch sieht es für mich aus, als ob die 4 (arr[0] aus i==2) einfach überschrieben wird. Tatsächlich wird sie aber in arr[1] geschrieben. Warum?? Wo steht dieser Schritt?

Könnt ihr mir helfen?

Vielen Dank
lg, freakC++

Du hast den zweiten Durchlauf der Schleife vergessen.

freakC++

Ahhh ......
Danke!

lg, freakC++