insertion sort

lupara

hi miteinander,
ich suche infos oder eine kleine erklärung _/ anleitung zum insertion sort.
das scheint ja etwas sehr gängiges zu sein. bekomm ich vielleicht den code schon fertig irendwo her. wobei ich es schon lieber selber machen würde. aufgabe ist x zahlen zu sortieren.....
buble sort verstehe ich...
hoffe ihr könnt mir helfen.
bye und danke

c.rackwitz

http://en.wikipedia.org/wiki/Insertion_sort
http://web.engr.oregonstate.edu/~minoura/cs162/javaProgs/sort/InsertSort.html

reicht das vorerst?

ist quasi sehr verwandt mit bubblesort. das array wird durchgelaufen und jedes element so oft nach links getauscht, bis es an seinem platz ist. deswegen $O(n^2)$

hi
danke für die antwort.
mhh naja auf die site bin auch schon gesstoßen, so arg viel hilft mir die nicht weiter. ich bräuchte ein paar hinweise, wie ich es praktisch in c umsetzte. die idee dahinter versteh ich schon. was ich mir zum beispiel nicht so ganz vorstellen kann ist wie das programm die werte die größer sind nach rechtsverschiebt. indem ich ein paar zeilen schreibe und damit die werte vertausche(mit einer variablen temp zb)? und das für jeden wert einzeln oder prüft es erst welche verschoben werden müssen und verschiebt dann alle auf einmal. denke nicht, geht bestimmt mit ner schleife.
?
bye und danke!
lupara

c.rackwitz

ob du immer zwei tauschst und dann pruefst oder erst die position findest und dann alle auf einmal verschiebst, ist an sich egal.

zeig doch mal, was du schon hast.

hi also die größte zahl sortiert er mir schon bis ganz ans ende. die anderen läßt er aber noch so in ihrer reihenfolge. ich vermute ein kleiner fehler in der schleife?

bye und danke

#include <stdio.h>
#include <conio.h>

int main()
{
    int iAFeld[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    int i = 0, j = 0, itemp = 0;

    printf("\n***10 Zahlen sortieren***\n");
    printf("\n10 Zahlen eingeben \n");
    for (i = 0; i < 10; i++)
    {
        printf("iAFeld[%d]?", i + 1);
        scanf(" %d", &iAFeld[i]);
    }

    for (i = 0; i < 10; i++)
    {
        j = i;
        itemp = iAFeld[j];
        if ((j > 0) && (iAFeld[j - 1] > itemp))
        {
            iAFeld[j] = iAFeld[j - 1];
            j--;
        }
        iAFeld[j] = itemp;
    }

    for (i = 0; i < 10; i++)

    {
        printf("[ %d]\n", iAFeld[i]);

    }
    return 0;
}

Edit by c.rackwitz: indent und cpp-Tags

c.rackwitz

du hast keine innere schleife.

#include <stdio.h>
#include <conio.h>
int main ()
{
	int iAFeld[10]={0,0,0,0,0,0,0,0,0,0};
	int i=0,j=0,itemp=0;

printf("\n***10 Zahlen sortieren***\n");
printf("\n10 Zahlen eingeben \n");
for (i=0;i<10;i++)
	{printf("iAFeld[%d]?",i+1);
	scanf (" %d",&iAFeld[i]);
	}

for (i=0;i<10;i++)
{j=i;
itemp=iAFeld[j];
while ((j>0)&&(iAFeld[j-1]>itemp))
{iAFeld[j]=iAFeld[j-1];
j--;
}
iAFeld[j]=itemp;
}

for(i=0;i<10;i++)

{
	printf("[ %d]\n",iAFeld[i]);

}
return 0;
}

Edit by c.rackwitz: wuerdest du bitte cpp-Tags benutzen? danke.