Insertionsort typenlos?

Hallo,

nachdem ich mal versucht habe die klassischen Sortieralgorithmen in C mit
void* Zeigern zu programmieren, also mit der gleichen Schnittstelle wie den
qsort. Wer die nicht kennt:

qsort(void* base, size_t count, size_t size, int (*)(const void*, const void*);

Der klassische Insertionsort funktioniert ja folgendermaßen

isort(int a[], int length)
{
    int i, j, vergleich;
    for(i = 2; i <= length; ++i) {
        vergleich = a[i];
        j = i;
        while(a[j-1] > vergleich) {
            a[j] = a[j-1];
            --j;
        }
        a[j] = v;
    }
}

Das Problem ist ja nun, das das Element vergleich variabel groß sein kann, und
ein malloc in einem sort einfach unakzeptabel ist. Gehe ich recht in der Annahme, dass der klassische isort einfach nicht so implementierbar ist, oder bin ich einfach blind?

Gruß Tobias

PAD

Das ist wohl eher was für C++ und die STL,

oder liege ich da falsch.

mady

Selbstverständlich geht das auch in C. Dazu muss man nur einen passenden Prototyp nehmen, der alle Informationen bereithält (so wie qsort). Dann sollte das überhaupt kein Problem sein.

Mit memcpy() kann die Zuweisung implementiert werden und mit der Vergleichsfunktion wird die while-Schleife gesteuert.

Ich habe hier (@work) nur keinen C-Compiler (und keine Lust), um das schnell zu coden... :))

PAD schrieb:

Das ist wohl eher was für C++ und die STL,

oder liege ich da falsch.

Mit C++ geht es einfacher - da stimme ich Dir zu.

volkard

Das Problem ist ja nun, das das Element vergleich variabel groß sein kann, und ein malloc in einem sort einfach unakzeptabel ist.

malloc ist sehr wohl akzeptabel. der sort dauert so lange, ein kleines malloc davor kostet fast keine zeit.
und in dem falle, daß kein swap genommen wird, was so klasse für templates ist (swap ist in c++ gerne exceptionfrei und schnell), sondern memcpy, würd ich lieber ein kleines malloc neh...
oder mal in C99 nachgucken wie da mit den arrays war.

isort(int a[], int length) 
{ 
    for(int i = 2; i <= length; ++i) { 
        j = i;
        while(j>0 && a[j-1] > a[j]) {
            swap(a[j],a[j-1]);
            --j;
        } 
    } 
}

aber so versteh ich den code ja gar nicht.

void letztenEinsortieren(double* a,size_t len)
{
    size_t i=len-1;
    while(i>=1 && a[i-1]>a[i])
        swap(a[i-1],a[i])
}
void isort(double* a,size_t len)
{
    for(int i=2;i<len;++i)
        letzenEinsortieren(a,i);
}

Danke für die Antworten, aber ich habe mal ein bisschen Google Groups bemüht und was schönes ohne malloc gefunden. Meiner Meinung ist ein malloc einfach bloat, weil es einfach nicht konstant arbeitet. Je nachdem wie fragmentiert der Speicher ist ...

Hier mal mein Code

static void
swap(void* first, void* second, size_t size)
{
	char* a = first;
	char* b = second;
	char temp;

	++size;
	while(--size) {
		temp = *a;
		*a = *b;
		*b = temp;
		++a, ++b;
	}
}

void
insertionsort(void* ptr, size_t count, size_t elem_size, cmp_fct compare)
{
	char* x = (char*)ptr + elem_size; /* Zeiger auf das zweite Element des Feldes */
	char* y;
	char temp;
	size_t i, j, k, l;

	for(i = 2; i <= count; ++i) {
		y = x;
		j = i - 1;

		while(j > 0 && compare(x, y - elem_size) < 0) { /* Solange wir im Feld sind und *x < *y */
			--j;
			y -= elem_size; /* Ein Feld weiter zurück */
		}

		if( (i - j - 1) == 0) { /* Der Schleifenrumpf wurde nicht betreten, x ist größer als der direkte Vorgänger */
			x += elem_size;
			continue;
		}

		for(k = 0; k < elem_size; ++k) { /* Vom ersten Feld größer als *x, das (i-j)*elem_size hinter x liegt, werden alle
										  * Felder byteweise um eins nach vorne verschoben und jeweils ein Byte von x an dies
										  * Stelle geschoben
										  */
			y = x;
			temp = *x++;

			for(l = 0; l < (i - j - 1); ++l) {
				*y = *(y - elem_size);
				y -= elem_size;
			}
			*y = temp;
		}
	}
}

Das ist auch sehr nahe am ursprünglichen isort udn recht elegant finde ich.

Gruß Tobias

volkard

da hacke ich nen eklig großen 5-zeiler auf in nen 3-zeiler und nen 2-zeiler und er nennt nen 20-zeiler "elegant".
ich glaub' ich mag kein c.

edit: schau trotzdem mal nach, was der C99-Standard zu arrays sagt. da hat sich was geändert, was die deine argumente wegnimmt. brauchst nämlich kein malloc für.
kann c inszwischen inline? dann könnte man was zerleen. zur not tuns auch makros. aber ein 20-zeiler für sowas einfaches mag mit nicht in den sinn.

RTC

volkard schrieb:

da hacke ich nen eklig großen 5-zeiler auf in nen 3-zeiler und nen 2-zeiler und er nennt nen 20-zeiler "elegant".
ich glaub' ich mag kein c.

Was soll sich denn in C99 mit den Arrays geändert haben?? Und welcher C-Compiler unterstützt C99 komplett und ist inline jetzt C99 Schlüsselwort.
Wenn ich es in GNU C schreiben würde, dann könnte ich auch mehr inlinen.
Von den 20 Zeilen ist halt auch was Kommentar dabei. Ich nutze nur Stack-Speicher und Speicher reservieren kann halt Zeit kosten. Zudem kann ich nicht garantieren, dass mein sort immer funktioniert. Gibt malloc NULL zurück ist alles im Eimer.

Gruß Tobias

Noch mal richtig und ohne Vertipper:

Habe mich mal über C99 informiert. Ich glaube du redest von VLA(Variabe Length Arrays). Aber die Frage ist: Ist das schneller, funktioniert das plattformübergreifend, ist es schon sehr weit verbreitet? Welchen Compiler kennst du, der VLA unterstützt?

Gruß Tobias Bell