Zweidimensionales Array (Strings) sortieren

Ich habe ein 2D Array mit Strings (dynamisch) und muss dieses
nun nach einer bestimmten Spalte sortieren (absteigend und aufsteigend).

Nun weiss ich nicht so recht, wie ich anfangen soll. Es gibt ja verschiedene
Algorithmen und ich habe gelesen, das Quicksort der beste wäre. Kann man diesen auch auf ein 2D Array anwenden?
Ich hab auch von der Funktion qsort() aus der stdlib gehört, kann man diese auch dafür nutzen? Also ist es damit möglich, nach einer bestimmten Spalte zu sortieren?

Würde mich über eine Antwort echt freuen!!!

Gruß,
Der Ingo

Wutz

Ja.

Also ja zu:

Ich hab auch von der Funktion qsort() aus der stdlib gehört, kann man diese auch dafür nutzen? Also ist es damit möglich, nach einer bestimmten Spalte zu sortieren?

scimansix

Ja, mit qsort() geht das, wenn man die Vergleichsfunktion entsprechend schreibt.

Ok, ich hab mich ein wenig mit qsort() auseinandergesetzt und ich komm noch nicht ganz drauf. Die Bedeutung der Parameter ist mir fast klar, aber wie ich mein col_cnt (also die zu sortierende Spalte) mit einbringen soll, ist mir ein Rätsel.

In der Vergleichsfunktion muss ich ja die Zeilen vergleichen, aber wie mache das jetzt, das bspw. nur Spalte 3 betrachtet werden soll?

deiner vergleichsfunktion werden 2 const void * zeiger übergeben. diese castest du in der funktion auf den typ deiner structs. dann vergleichst du die werte und gibst den wert zurück.

zeig doch mal bischen code dann ist das leichter

hehe, es ist schon bischen spät;)

die zu sortierende spalte bringst du durch die vergleichsfunktion rein. andere spalte andere funktion.

Also, mein Aufruf von qsort() sieht folgendermaßen aus:

qsort(values, rows, sizeof(values), compare);

values: 2D-String-Array
rows: Anzahl der Zeilen

Meine compare-Funktion:

int
compare(const void *ptr1, const void *ptr2) 
{
	const char* p1 = *(char**)ptr1;
	const char* p2 = *(char**)ptr2;

	return strcmp(*(char**)p1,*(char**)p2);
}

Also die erste Spalte wird so schon mal sortiert, aber wie bring ich da nun die variable Spalte ein?

Wutz

Du redest in Bezug auf Strings immer von Spalten. Strings haben zunächst mal keine Spalten. Definiere mal, was du unter Spalten verstehst.

Also mein Array ist ja so aufgebaut:

[0][0] [0][1] [0][2]
[1][0] [1][1] [1][2]
[2][0] [2][1] [2][2]

Dort stehen die Strings drin.

Mit Spalte meine ich halt beispielsweise [0][1],[1][1],[2][1]. Anhand dieser "Spalte" will ich mein Array sortieren. Wenn der String, der in [2][1] steht, lexikografisch kleiner ist als [1][1] und [0][1], rückt dann die Zeile nach ganz oben.

_--

evtl. hilft das ein bischen

typedef enum{
 SC_A
,SC_B
,SC_C
}sortable_cols;

typedef int (*cmp_t)(const void *a,const void *b);

typedef struct{
 char *name;
 char *pass;
 char *firstname;
 char *lastname;
}obj_t;

int cmp_a(const void *a,const void *b){
 const obj_t *A = a;
 const obj_t *B = b;
 return strcmp(A->name,B->name);
}

int cmp_b(const void *a,const void *b){
 const obj_t *A = a;
 const obj_t *B = b;
 return strcmp(A->pass,B->pass);
}

int cmp_c(const void *a,const void *b){
 const obj_t *A = a;
 const obj_t *B = b;
 int ret;
 if((ret = strcmp(A->name,B->name))==0){
  return strcmp(A->pass,B->pass);
 }
 return ret;
}

cmp_t get_cmp_fn(sortable_cols col){
 cmp_t cmp;
 switch(col){
  default:
  case SC_A:cmp = cmp_a;break;
  case SC_B:cmp = cmp_b;break;
  case SC_C:cmp = cmp_c;break;
 }
 return cmp;
}

...

qsort(values, rows, sizeof(values), get_cmp_fn(SC_A));

@edit falls du viel sortierst und dir keine eigene sort funktion schreiben willst, wär c++ evtl. die bessere wahl. volkard hat mal aufgezeigt, dass c++ dank der templates schneller sortieren kann als qsort in c

Leider muss ich das in ANSI-C umsetzen.

Hm, ich schau mal was ich damit anfangen kann - ich muss halt den Index der Spalte übergeben können, da Anzahl und Bezeichnung der Spalte variabel ist.

volkard

Ing0 schrieb:

ich muss halt den Index der Spalte übergeben können, da Anzahl und Bezeichnung der Spalte variabel ist.

Das ist nicht vorgesehen.
Du kannst die Anzahl der Spalten begrenzen auf sagen wir mal weniger als 15 und machst 15 Funktionen, oder Du machst eine globale Variable (pro Thread), die Du vor dem Sortieren setzt und in der Vergleichsfunktion benutzt.

_--

man könnte auch einen index auf die spalte(n) erstellen, aber das ist ein anderes thema

Hm, dann ist die vordefinierte Funktion qsort() vielleicht doch nicht das Mittel der Wahl.

_--

wenn du alles in einer sortierfunktion verwurstest, wirds leider auch nicht schneller

In einer Sortierfunktion möchte ich das ja gar nicht verwursten, aber
das Ding ist: ich kann nicht einfach die Anzahl der Spalten auf <= 15
beschränken und 15 Funktionen implementieren (naja, können schon, aber
das ist aufgrund von einzuhalten Vorgaben nicht gegeben).

Wutz

Was du anscheinend brauchst, ist eine parametrisierbare Vergleichsfunktion, dass leistet die Standardbibliothek mit qsort (ohne häßliche Hacks) nicht, es gibt aber ausreichend Alternativen mit ANSI C, z.B. libavl von Ben Pfaff (GNU-Lizenz), dort ist z.B. solche eine Parametrisierbarkeit enthalten (im Gegensatz zu qsort):

int rb_comparison_func (const void *rb_a, const void *rb_b ,void *rb_param);

_--

nimm doch einfach ne db z.b. sqlite, oder ist das auf euerem vorgabenzettel unter verboten gelistet

@ _-- ich muss das schon programmieren, sei es mit Hilfe eines qsort() oder ähnlichem.

Man kann doch sicherlich den Quicksort-Algo selber implementieren und auf seine Anforderungen umstellen?