C-programmerings fråga. Hur fungerar denna loop?

[tokfan]

Tjenare!
Ursäkta att jag tränger mig in under microprocessorer-fliken, men jag visste inte riktigt vart min fråga hörde.
Och här lär det ju finnas tusentals C-programmerare.
Dettar är ett program som skriver in 10 värden och sorterar dom i nrordning. Jag fattar inte riktigt hur sorteringsloopen fungerar.

double xdata[10], temp;
int i, j;
/* läs in data */
for (i = 0; i < 10; i++)
{
printf("xdata[%d] = ", i);
scanf("%lf", &xdata);
}
/* sortera data */
for (i = 0; i < 9; i++)
for (j = i + 1; j < 10; j++)
if (xdata[j] < xdata) {
/* byt plats */
temp = xdata;
xdata = xdata[j];
xdata[j] = temp;
}
/* skriv data */
for (i = 0; i < 10 ; i++)
{
if (i % 5 == 0)
printf("\n");
else
printf(" ");
printf("%f", xdata);
}
printf("\n");
return 0;
}
Någon som är sugen på att göra ett försök att förklara?

[Nerre]

För varje värde jämför du med de andra (i tur och ordning) och om det ena är större än det andra byter de plats.

Det är väl mer eller mindre en vanlig bubble sort.

[sodjan]

Vad mer specifikt är oklart ? Kör en "simulering" med papper och penna så ser du hur det fungerar...

[TomasL]

Men skrivet på ett mycket dåligt sätt.

[AndersG]

Håller med, ren brute-force.. Nu vet vi inte avsikten, men annars så innehåller ju de flesta C-bibliotek en implementation av quicksort.

[snigelen]

Här har du en "pappers-simulering" för en vektor med fyra element, 4 1 3 2.

Kod: Markera allt

i=0, j=1   4 1 3 2
           | |

	   Byt plats -> 1 4 3 2

i=0, j=2   1 4 3 2
           |   |

	   Låt stå

i=0, j=3   1 4 3 2
           |     |

	   Låt stå

i=1, j=2   1 4 3 2
             | |

	   byt plats -> 1 3 4 2

i=1, j=3   1 3 4 2
             |   |

	   Byt plats -> 1 2 4 3

i=2, j=3   1 2 4 3
               | |

	   Byt plats -> 1 2 3 4

Färdigt.

[LHelge]

Det är som andra säger en bubble-sort men skriven på ett riktigt uselt sätt.

Kul sätt att illustrera sorteringsalgoritmer för övrigt:
http://www.youtube.com/user/AlgoRythmics

[tokfan]

Man tackar!
Jag visste inte riktigt vart jag skulle sätta fingret på problemet.
försökte tidigare skriva ut det på papper men visste inte riktigt vad jag höll på med.
Nu trillade poletten ner tillslut. tack snigelen för ett förbaskat bra exempel och att du tog dig tiden att skriva det!

skitschysst!!!!

har börjat en nybörjarkurs i C-programmering förra veckan, så allt är lite lurigt nu i början innan man kommer in i det rätta tänkandet tror jag.

Ha det bra!!

[Swech]

Vad är det som är så uselt?

Funktion?
kommentering?
kodning?

Swech (som inte kör C)

[bit96]

Det är som andra säger en bubble-sort men skriven på ett riktigt uselt sätt.

Kul sätt att illustrera sorteringsalgoritmer för övrigt:
http://www.youtube.com/user/AlgoRythmics

Den skulle man sett för 20 år sen då man försökte förstå quicksort.

[TomasL]

Vad är det som är så uselt?

Funktion?
kommentering?
kodning?

Swech (som inte kör C)

Det här:

Kod: Markera allt

for (i = 0; i < 9; i++)
for (j = i + 1; j < 10; j++)
if (xdata[j] < xdata[i]) {
/* byt plats */
temp = xdata[i];
xdata[i] = xdata[j];
xdata[j] = temp;
}

Koden skriven på detta sätt skall straffas med nackskott, ungefär.

Minsta kravet är så här:

Kod: Markera allt

for (i = 0; i < 9; i++){
	for (j = i + 1; j < 10; j++){
		if (xdata[j] < xdata[i]) {
				/* byt plats */
				temp = xdata[i];
				xdata[i] = xdata[j];
				xdata[j] = temp;
		}
	}
}

Jag föredrar.

Kod: Markera allt

for (i = 0; i < 9; i++)
	{ 
		for (j = i + 1; j < 10; j++)
		{
			if (xdata[j] < xdata[i]) 
			{
				/* byt plats */
				temp = xdata[i];
				xdata[i] = xdata[j];
				xdata[j] = temp;
			}
		}
	}

Även om det är tillåtet att ge fasiken att klamra, så SKALL man klamra allt, god programteknik.
Visserligen var exempelkoden inklistrad utan taggar, så formateringen giått förlorad.
Tittar man på MISRA så ser man att det är en dödssynd att skriva kod som orginalet.
Det handlar om att vara övertydlig, då är risken för fel mindre.
Även en sån har rad är tillåten

Kod: Markera allt

for (i = 0; i < 9; i++)for (j = i + 1; j < 10; j++)if (xdata[j] < xdata[i]){temp = xdata[i];xdata[i] = xdata[j];xdata[j] = temp;}

Men........

[Nerre]

Loopar den inte onödigt många gånger också?

Om alla värden är i ordning från början så kommer den ju ändå att loopa igenom alla. Med en klassisk bubble sort avbryter man väl om det inte blev nåt byte?

[LHelge]

I normalfallet brukar den yttre loopen vara en while som fortsätter så länge en förflyttning gjorts precis som nerre säger. Men å andra sidan är det väl lite som att sminka en gris när man optimerar en bubble-sort.

[pbgp]

Är det inte så att det kan vara snabbare med en bubblesort än quicksort för små input och t.om. så att vissa implementationer går över till bubblesort när man kommit tillräckligt långt i rekursionen?

10 element som i koden ovan är ganska kort.

bubblesort är dessutom lätt att implementera (jag har implementerat min egen qsort).. så om prestanda inte är viktigt kan den vara att föredra

[LHelge]

Det känns som att diskussionen ballar ut lite nu, alla sorteringsalgoritmer har sin plats och i en första C-kurs kan väl vara en av de bättre för just bubble-sort precis som pbgp säger. Vill du se tydligt hur den jobbar så titta på folkdansarna.