insertion sort . Was soll da noch falsch sein ?

void insert(int* x,int length)
{
    for(int i=1;i<length;i++){

      int z,tmp;
      tmp=x[i];
      for( z=i-1;(x[z]>x[i]) && z>=0;z--)
	   {
          x[z+1]=x[z];  
       }

       x[z+1]=tmp;
     }
}

unsortiertes array: int x[]={5,1,3,2,9,6,8};

sortiert: 1 3 2 5 6 8 9 //die 2 sollte vor der 3 kommen

so lief es bei mir

void insert(int* x,int length)
{
	int i,z,tmp;
    for(i=1;i<length;i++){
      tmp=x[i];
      for(z=i-1;z>=0 && (x[z]>tmp);z--)
       {
          x[z+1]=x[z];
       }
       x[z+1]=tmp;
     }
}

es sollte aber ausreichen wenn du
x[i] mit tmp tauscht

lg lolo

ohhhh danke,

war schon kurz vor der Verzweifelung.

hab jetzt x[i] durch tmp ersetzt.

Aber wo ist der Unterschied . Ist doch dasselbe ??

SeppJ

blurry333 schrieb:

Aber wo ist der Unterschied . Ist doch dasselbe ??

Nein, denn der Wert an der Stelle i kann sich bei der Zuweisung

x[z+1]=x[z];

ändern.

bin mir jetzt nicht ganz sicher, aber der erste ausdruck also

(x[z]>x[i])

wird doch auch ausgewertet wenn z == -1 also hast ein buffer underflow da z>=0 erst danach getestet wird

btw. hab um das mal durch zu gehen wiki's structogramm zur hilfe genommen
http://de.wikipedia.org/wiki/Insertionsort
evtl. ist das ja ein blick wert

ok . danke

Kennt einer den insertion sort mit sentinel.
Man soll dadurch nur noch den halben Aufwand beim Testen haben.

http://www.igtfy.com/?q=sentinel+programmierung
ach ja es ist sofort der erste link da wird das super erklärt, ich denke nicht das es eine sortierungs function mit sentinel geben kann außer es ist sicher gestellt das die sequenz keine lücken hat?

kann das bitte einer auflären?

lg lolo

noobLolo schrieb:

http://www.igtfy.com/?q=sentinel+programmierung
ach ja es ist sofort der erste link da wird das super erklärt, ich denke nicht das es eine sortierungs function mit sentinel geben kann außer es ist sicher gestellt das die sequenz keine lücken hat?

kann das bitte einer auflären?

lg lolo

also das war jetzt mal geistiger dünn pfiff, bis auf den link...

SeppJ

Das geht sogar noch genauer:
http://www.igtfy.com/?q=sentinel+sorting
Genaue Anleitung.

void insert(int* x,int length)
{
  int i,z,tmp;
  for(i=2;i<length;i++){
    tmp=x[i];
    x[0] = tmp-1;
    for( z=i-1;x[z]>tmp;z--)
    {
      if(z!=0){
        x[z+1]=x[z];
      }
    }
    x[z+1]=tmp;
  }
}

so könnt das evtl. stimmen, denk der sentinel muß an den anfang und nicht ans ende

void insert(int* x,int length)
{
	int i,z,tmp;
    for(i=2;i<length;i++){
      tmp=x[i];
      x[0] = tmp-1;
      for( z=i-1;x[z]>tmp;z--)
      {
    	  if(z==0){
    		  z++;
    		  break;
    	  }
          x[z+1]=x[z];
      }
      x[z+1]=tmp;
    }
}

so schaut mein versuch jetzt aus

Wie könnte man denn hier ein Sentinel einbaun ?

void insert(int* x,int length)
{
    for(int i=1;i<length;i++){

      int z,tmp;
      tmp=x[i];
      for( z=i-1;z>=0 && x[z]>tmp;z--)  //Kann sich ja nur um z>=0 handeln
	   {                           //an das x[z] ein INT_MAX anhängen ?
          x[z+1]=x[z];  
       }

       x[z+1]=tmp;
     }
}

evtl. reicht es auch so

void insert(int* x,int length)
{
    int i,z,tmp;
    if(length<3)
    	return;
    for(i=2;i<length;i++)
    {
      tmp=x[i];
      x[0] = tmp-1;
      for( z=i-1;x[z]>tmp;z--)
      {
          x[z+1]=x[z];
      }
      printf("%d\n",z);
      x[z+1]=tmp;
    }
}
#define SENTINEL 0
int main(void) {
	int arr[] = {SENTINEL,3,2,1};
	int l = 4;

	insert(arr,l);

	return 0;
}

hmm.

aber muss man denn nicht immer das übergebene Array umkopieren und z.b. an letzter Stelle ein int_max sag ich jetzt mal einfügen. Da steckt ja erstmal
schon aufwand dahinter.

Dein Beispiel hab ich leider noch nicht ganz verstanden. Muss ich mir nochmal anschaun

Und SENTINEL 0 ist auch problematisch oder. Schließlich kann 0 auch ganz
normal im array vorkommen

wenn dann müßtest du am anfang dein array einmal um kopieren, um den sentinel vorne einzufügen, insertionsort läuft von hinten nach vorne, daher auch den sentinel an anfang, der sentinel wird in z.9 bei jedem schleifen durchlauf neu gesetzt, daher ist das define SENTINEL 0 egal da kann man nehmen was man will, sry für das "igtfy" aber ich find das immer wieder schön anzuschauen

man kann sicher auch den algo drehen so dass er in die andere richtung läuft dann tuts evtl. auch ein realloc um den sentinel anzuhängen

aha. hab grade was gelesen von wegen der Sentinel muss mindestens so klein
sein wie das kleinste element im array. Dieses müßte man ja auch erst finden.
Würde ja auch wieder Aufwand bedeuten.

Was soll eigentlich in deinem Code

if (length<3) return ? 2 elementige menge muss doch auch sortiert werden

ich hab jetzt keine lust mehr, such dir nen anderen oder versuch deine fragen selbst zu lösen... so schwer ist das alles nicht
vor allem sowas

if (length<3) return

sollte sich schon lösen lassen

naja schon ok.

ich verstehs trotzdem nicht. Wenn die Länge 2 ist.

wird die funktion ohne etwas zu sortieren wieder verlassen.

Was soll das ?