✔ C: Zweidimensionales Array nach 3. Spaltenwert sortieren

[mc_gulasch]

Hallo zusammen,

mich hält seit einiger Zeit folgendes Problem wach:

Ich habe ein 2-dim Array, das nach dem 3. Spaltenwert zeilenweise Sortiert werden soll.

unsigned int t[4][5]={{1,2,4,2,1},
                              {1,3,2,1,1},
                              {1,2,4,5,5},
                              {1,1,1,1,1}};

Ich versuche es gerade mit qsort() und der Vergleichsfunktion:

int cmp(const void *ptr1, const void *ptr2) 
{
	const int* p_1 = (int*)ptr1;
	const int* p_2 = (int*)ptr2;
	return (*p_2 - *p_1);
}

Leider hat es nicht den gewünschten Effekt und dem geübten Auge fällt vielleicht auf, dass ich noch recht neu bin auf dem Gebiet der C-Programmierung

Ich wüsste zwar ungefähr, wie man es in Java macht, aber bei C hab ich keine Chance. Der Vergleichsalgo läuft ja subba, nur leider zeilenweise.

Kann mir wer weiterhelfen?

Greetz
Gulasch

 

[deepthroat]

Hi.

Um das Array zeilenweise zu sortieren mußt du das mit qsort zeilenweise durchgehen und jeweils eine Zeile mit einer anderen Zeile vergleichen.

Die Vergleichsfunktion würde dann z.B. so aussehen:

int comp(const void* a, const void* b) {
  int* av = (int*) a;
  int* bv = (int*) b;

  return (av[2] - bv[2]);
}

Den Aufruf der qsort Funktion kriegst du ja dann bestimmt selber raus... ;-)

Gruß

 

[RedWing]

Hallo,

also mein naiver Ansatz waere die Spaltenelemente in ein temporaeres Array zu schreiben,
dieses mit qsort zu sortieren, und danach die Werte wieder zurueck in das Original Array zu schreiben.

Aussehen koennte das so:

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

#define XSIZE 5
#define YSIZE 4

int cmp(const void *ptr1, const void *ptr2){
	const int* p_1 = (int*)ptr1;
	const int* p_2 = (int*)ptr2;
	return (*p_2 - *p_1);
}

int sort_column(unsigned int array[YSIZE][XSIZE], unsigned int column_number){
	unsigned int to_sort[YSIZE];
	int i = 0;
	if(column_number >= YSIZE)
		return -1;
	for(i = 0; i < YSIZE; i++)
		to_sort[i] = array[i][column_number];
	qsort(to_sort, YSIZE, YSIZE, cmp);
	for(i = 0; i < YSIZE; i++)
		array[i][column_number] = to_sort[i];
	return 0;
}

int print_column(unsigned int array[YSIZE][XSIZE], unsigned int column_number){
	int i = 0;
	if(column_number >= YSIZE)
		return -1;
	for(i = 0; i < YSIZE; i++)
		printf("%d\t", array[i][column_number]);
	printf("\n");
	return 0;
}

int main(){
	unsigned int t[YSIZE][XSIZE] = {
		{1,2,4,2,1},
		{1,3,2,1,1},
        {1,2,4,5,5},
		{1,1,1,1,1}
	};
	print_column(t, 2);
	sort_column(t, 2);
	print_column(t, 2);
	return 0;
}

Gruß,

RedWing

 

[deepthroat]

Hi.

Hallo,

also mein naiver Ansatz waere die Spaltenelemente in ein temporaeres Array zu schreiben,
dieses mit qsort zu sortieren, und danach die Werte wieder zurueck in das Original Array zu schreiben.

So wie ich das verstanden habe möchte er das 2 dimensionale Array sortieren und als Sortierkriterium die 3. Spalte nehmen und nicht nur die 3. Spalte sortieren.

Es scheint dein Ansatz war nicht naiv genug

PS: Ich seh gerade, du hast da noch einen Fehler drin:

qsort(to_sort, YSIZE, YSIZE, cmp);

Sollte wohl heißen

qsort(to_sort, YSIZE, sizeof(to_sort[0]), cmp);

Gruß

 

[RedWing]

Achso,
dann hab ich das wohl falsch verstanden
Werde mich in Naivitaet wohl noch ein bisschen ueben muessen

//edit: Ja, streu nur Salz in meine Wunden

Gruß,

RedWing

 

[mc_gulasch]

Hallo,
leider hilft mir das nicht weiter. Noch etwas genauer mein Problem:

also ich habe wie bereits erwähnt

unsigned int t[4][5]={{1,2,4,2,1},
                              {1,3,2,1,1},
                              {1,2,4,5,5},
                              {1,1,1,1,1}};

//edit: Sorry, alte Version

Wenn ich mir jetzt die Adresse von "t" ausgebe krieg ich "t[0][0]", wenn ich mir die von "t+1" ausgeben lasse, krieg ich "t[1][0]" ...soweit so gut. Also geb ich dem qsort() einfach mal "t" mit, in der Hoffnung, dass er "t" und "t+1" als Pointer für die Vergleichsfunktion nimmt.

int cmp(const void *ptr1, const void *ptr2) 
{
const int* p_1 = (int*)ptr1;
const int* p_2 = (int*)ptr2;
return (*p_2 - *p_1);
}

Leider tut er das nicht, sondern gibt mir für ptr1 t[0][1] und für ptr2 t[0][0] .... warum?

Eigentlich ist doch mein Ziel, den qsort auf t[0] bis t[4] (Zeilen) anzuwenden und die Vergleichsfunktion auf jeweiligen Zeilenelemente. Oder nicht?

Ach ja, mein qsort Aufruf:

qsort(t,4,sizeof(unsigned int*),cmp);

Hilfe?

 

[deepthroat]

Eigentlich ist doch mein Ziel, den qsort auf t[0] bis t[4] (Zeilen) anzuwenden und die Vergleichsfunktion auf jeweiligen Zeilenelemente. Oder nicht?

Nein. Das geht ja nicht. Die qsort Funktion ruft die Vergleichsfunktion immer für die Elemente das Arrays auf die du sortieren möchtest - und du möchtest ja schließlich auch die Zeilen sortieren. Dann mußt du eben auch die Zeilen verarbeiten.

Ach ja, mein qsort Aufruf:

qsort(t,4,sizeof(unsigned int*),cmp);

Versuch's mal so

qsort(t, sizeof (t) / sizeof(t[0]) /* == 4 */ ,
      sizeof(t[0]), comp);

Gruß

 

[mc_gulasch]

Versuch's mal so

qsort(t, sizeof (t) / sizeof(t[0]) /* == 4 */ ,
      sizeof(t[0]), comp);

Gruß

Du Genie Sauber. So gehts.... aber mal ganz ehrlich: Warum?

 

[deepthroat]

Naja, ganz so falsch war das was du hattest ja nicht. Allerdings gibt es einen Unterschied zwischen statischen Arrays und Arrays die man zur Laufzeit anlegt.

Bei einem statischen Array (auch bei einem mehrdimensionalen) wird die ganze Chose nur mit Arithmetik von der Adresse des Arrays aus geregelt. Bei einem dynamsichen, mehrdimensionalen Array sind die Unterarrays Zeiger - was eben bei einem statischen Array nicht der Fall ist; da liegen alle Elemente des (mehrdimensionalen) Arrays hintereinander.

Also,

int m[3][5]; /* ein 2-dimensionales Array 3x5 */
/* m bezeichnet eine Adresse. (man kann übrigens von einer
   solchen Array-Variablen nicht die Adresse bestimmen) */
m[2][1] == *( m + 2 * sizeof(m[0]) + 1 * sizeof(int) );

/* --------------------  */

int **m = (int**) calloc (3, sizeof(int*));
m[0] = (int*) calloc (5, sizeof(int));
m[1] = (int*) calloc (5, sizeof(int));
m[2] = (int*) calloc (5, sizeof(int));

/* auch ein 2-dim. Array Größe 3x5 */
/* Aber: */
m[2][1] == *(*(m + 2) + 1);

Am besten versteht man das glaub ich wenn man das visuell vor sich sieht. Du kannst ja mal versuchen das aufzumalen wie das ganze dann im Speicher aussieht.

Gruß

 

[mc_gulasch]

Cool, vielen Dank. Das passt so, habs verstanden, ist halt echt ein bisschen hart am Anfang, aber ich glaub man gewöhnt sich dran.