Forum: Knobelecke

Hallo,

im Thread über die Sortierung von Dateinamen wurde die Frage gestellt, wie man Dateinamen mit Versionsnummern in der vom Mensch erwarteten Weise sortieren kann statt wie üblich lexikographisch.

Ein Beispiel: gegeben sind die folgenden Strings:

file3
file24
file2
file7

Lexikographisch geordnet sähe das dann so aus:

file2
file24
file3
file7

Ein Mensch ist aber mit der folgenden Sortierung möglicherweise zufriedener:

file2
file3
file7
file24

Das Rätsel lautet nun: wie muss eine Vergleichsfunktion für einen Sortieralgorithmus aussehen, um die letztgenannte Sortierung zu erzeugen?

Wir nehmen einfach mal an, dass wir ein Array von Strings haben (z.B. argv) und eine Sortierfunktion (z.B. qsort() ). Gesucht ist also eine Funktion, die zwei Strings vergleicht und -1, 0 oder 1 zurückliefert, wenn der erste String entsprechend "kleiner", "gleich" bzw. "größer" als der zweite String ist:

int my_strcmp(const char *s1, const char *s2);

Es wäre natürlich schön, wenn die Vergleichsfunktion auch beispielsweise Kernelversionen ("2.6.31-rc2") vergleichen könnte.

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Eine eigene Lösung habe ich nicht.
Bei meiner Recherche nach Anhaltspunkten bin ich über http://sourcefrog.net/projects/natsort/ gestolpert.

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

Hallo Patrick,

Zitat:

Eine eigene Lösung habe ich nicht.
Bei meiner Recherche nach Anhaltspunkten bin ich über http://sourcefrog.net/projects/natsort/ gestolpert.

jepp, das ist ungefähr das, was ich suche. Die Lösung auf sourcefrog.net ist freilich grauenhaft, das kann man auch deutlich eleganter machen. Ein schönes Beispiel (und ebenfalls Lösung für dieses Rätsel) ist die wenig bekannte C99-Funktion strverscmp(), die die GPL-Bande vernünftigerweise mittels eines DFA implementiert, siehe strverscmp.c .

Beide Lösungen, sourcefrog.net und uClibc, sind allerdings für die Zwecke dieses Rätsels unnötig kompliziert, weil bei beiden führende Nullen berücksichtigt werden. Man muss also jeweils unterscheiden, ob man gerade nur ganze Zahlen (keine führenden Nullen) oder nur Brüche (führende Nullen) oder ganze Zahlen mit Brüchen vergleicht. Ohne diese von mir in weiser Voraussicht unterschlagene Bedingung müsste die Lösung des Rätsels in 3-4 Zeilen zu schaffen sein, exklusive den offensichtlichen Sanity-Checks am Anfang.

Da ich selbst aber noch keine konkrete Lösung für das Rätsel angefertigt habe, ist das eine wilde Spekulation.

Möchte sich noch jemand daran probieren?

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Habe inzwischen selbst eine Lösung gebaut. Habe wie immer viel zu kompliziert gedacht, und jetzt sieht sie doch ziemlich billig aus.

Soll ich auflösen oder bastelt noch jemand?

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Hier also die Lösung. Relevant ist nur die erste Funktion. Der übrige Krempel dient lediglich dazu, die Sortierfunktion mit *argv[] zu testen.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int strverscmp_simple(const char *s1, const char *s2)
{
	if (s1 == s2)
		return 0;

	while (*s1 == *s2) {
		if (*s1 == '\0')
			return 0;

		s1++; s2++;
	}

	if (isdigit(*s1) && !isdigit(*s2))
		return -1;

	if (isdigit(*s2) && !isdigit(*s1))
		return 1;

	return isdigit(*s1) ? atoi(s1) - atoi(s2) : *s1 - *s2;
}

int strverscmp_wrapper(const void *p1, const void *p2)
{
	return strverscmp_simple(* (char * const *) p1, * (char * const *) p2);
}

int main(int argc, char *argv[])
{
	int i;

	if (argc < 2) {
		printf("USAGE: %s <string(s)>\n", argv[0]);
		return -1;
	}

	qsort(&argv[1], argc - 1, sizeof(char *), strverscmp_wrapper);

	for (i = 1; i < argc; i++)
		puts(argv[i]);

	return 0;
}

strverscmp_simple() ist eigentlich ganz einfach: in der Schleife wird zunächst die erste Position ermittelt, an der sich die beiden Strings unterscheiden. Steht in *s1 dann eine Ziffer und in *s2 nicht, ist s1 kleiner als s2 (analog im umgekehrten Fall).

In der letzten Zeile schließlich wird überprüft ob *s1 (und also auch *s2) eine Ziffer ist. Falls ja, werden die Strings zu ints gemacht und miteinander verglichen. Falls nein, werden die beiden "Buchstaben" wie von strcmp() gewohnt miteinander verglichen.


Um von hier zum Verhalten des ursprünglichen strverscmp() zu kommen, müsste man noch eine weitere Unterscheidung einführen: sind *s1 und *s2 beides Ziffern und ist eine davon "0", dann ist dies die kleinere.

Warum man da bei GNU einen vergleichsweise unverständlichen DFA konstruieren musste, ist mir rätselhaft...

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)