4. 2D Array sortieren

2D Array sortieren

  • Mod

    Kannst du denn irgendetwas mit qsort sortieren? Wenn ja: Wo ist das Problem hier? Wenn nein: Da liegt das Problem! Dann musst du erst einmal lernen, wie man Datentypen über void* abstrahiert. Hast du dir denn in den letzten 8 Stunden mal ein paar Beispiele zu qsort angesehen?

    0
  • S

    Hallo SeppJ,

    Ja, ich habe schon mit qsort sortiert, aber nur 1D Arrays.

    Mit 2D Arrays habe ich da Schwierigkeiten, weil ich nicht ganz genau weiß, wie die 'Vergleichsfunktion' aussehen soll,
    dass wenn doppelte x-Einträge vorkommen, dann die doppelten x-Einträge nach der y-Spalte sortiert werden sollen
    (entweder absteigend oder aufsteigend).

    Ich hatte mir heute früh noch mal dein Code zum Einlesen angeguckt. Dazu habe ich noch zwei Fragen:

    In deiner insert_dpa() Funktion hast du eine Zeile mit

    size_t new_size = (old_size + 1) * 1.5;

    stehen. Wieso multiplizierst du noch mit 1.5?

    Dann noch eine Frage zum

    typedef struct
{
  double_pair *begin;
  double_pair *end;
  double_pair *end_reserved;
} dynamic_pair_array;

    Sollen *begin, *end und *end_reserved die Indizes des Array's sein?
    Falls ja, warum verwendet man nicht lieber "int" dafür?

    Vielen Dank schonmal für Deine Hilfe.

    Grüße,
    simsa

    0
  • ?

    simsa schrieb:

    Mit 2D Arrays habe ich da Schwierigkeiten, weil ich nicht ganz genau weiß, wie die 'Vergleichsfunktion' aussehen soll,
    dass wenn doppelte x-Einträge vorkommen, dann die doppelten x-Einträge nach der y-Spalte sortiert werden sollen
    (entweder absteigend oder aufsteigend).

    Wie Vergleichst du denn Wörter? Wenn der erste Buchstabe unterschiedlich ist, kannst du schon entscheiden. Was machst du aber wenn die gleich sind?

    Du musst doch eh eine eigene Vergleichsfunktion schreiben.

    Wenn du weißt wie ein Array in C aufgebaut ist, ist es kein Problem mehr.
    Der ganz rechte Index wechselt am häufigsten. Also stehen x- und y-Werte immer paarweise im Speicher.
    Somit hast du eigentlich auch nur noch ein 1D-Array

    0
  • S

    Hallo,

    ich habe vorhin wieder mit dem sortieren von einem 2D array gekämpft.

    Diesmal habe ich nicht direkt eine Datei eingelesen, sondern mir ein kleines
    Array mit 'sinnlosen' Zahlen erstellt.

    Mein Code sieht so aus:

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

typedef struct {
	double x;
	double y;
} data2d;

int
comp (const void *p1, const void *p2)
{
	if (*(data2d*)p1.x <  *(data2d*)p2.x) return -1;
	if (*(data2d*)p1.x == *(data2d*)p2.x)
	{
		if (*(data2d*)p1.y <  *(data2d*)p2.y) return -1;
		if (*(data2d*)p1.y == *(data2d*)p2.y) return 0;
		if (*(data2d*)p1.y >  *(data2d*)p2.y) return 1;
	}
	if (*(data2d*)p1.x >  *(data2d*)p2.x) return 1;
}

int
main (int argn, char *argv[])
{

	int i = 0;
	data2d *xy = NULL;
	xy = (data2d *) calloc(10, sizeof(data2d));

	xy[0].x = 1.2;		xy[0].y = 1.019;
	xy[1].x = 2.02;		xy[1].y = 33.98;
	xy[2].x = 3.25;		xy[2].y = 321.2;
	xy[3].x = 6.8;		xy[3].y = 105.1;
	xy[4].x = 5.11;		xy[4].y = 78.77;
	xy[5].x = 3.42;		xy[5].y = 658.5;
	xy[6].x = 3.12;		xy[6].y = 688.8;
	xy[7].x = 21.2;		xy[7].y = 1.081;
	xy[8].x = 100.2;	xy[8].y = 132.4;
	xy[9].x = 19.2;		xy[9].y = 1.157;

	printf("before qsort()\n");
	printf("==============\n");
	for (i=0; i<10; i++)
		printf("xy[%d].x = %.3f   xy[%d].y = %.3f\n", i, xy[i].x, i, xy[i].y);

	qsort(xy, 10, sizeof(data2d), comp);

	printf("after qsort()\n");
	printf("==============\n");
	for (i=0; i<10; i++)
		printf("xy[%d].x = %.3f   xy[%d].y = %.3f\n", i, xy[i].x, i, xy[i].y);

	return 0;

}

    Leider funktioniert da was nicht ganz. Wäre euch sehr dankbar, wenn ihr
    drüber gucken könntet.

    Beste Grüße,
    simsa

    0

  • Niemals double-Werte mittels == auf Gleichheit prüfen, das bringt nur Unglück.

    http://ideone.com/EGXyKE

    0
  • Mod

    Was heißt denn, "funktioniert nicht ganz"? Bitte präzise Fragen stellen und präzise Problembeschreibungen geben!

    Compiliert das überhaupt? In Zeile 13 ff. hast du lauter Syntaxfehler, weil du den Zeiger nicht richtig dereferenzierst:
    http://en.wikipedia.org/wiki/C_operator_precedence#Operator_precedence
    Also entweder richtig klammern oder besser gleich den Operator -> benutzen.

    Weiter habe ich jetzt nicht geguckt.

    Noch ein alter Trick für die Vergleichsfunktion, um dir die tausend Casts zu sparen (die du übrigens auch nicht const-korrekt durchgeführt hast 👎 ):

    int comp_mein_datentyp(const void* left, const void *right)
{
  const mein_datentyp *lhs = left, *rhs = right;

  // Hier ganz entspannt mit lhs und rhs arbeiten.
}

    P.S.: Außerdem hast du eventuell undefiniertes Verhalten, da es keinen Rückgabewert deiner Funktion gibt, wenn keine der Bedingungen zutrifft. Dieser Fall kann bei dir eintreten! Beispiel: NaN.

    0
  • S

    @SeppJ: danke danke danke 😉

    @Wutz: danke danke danke danke 😉

    Beste Grüße,
    simsa

    0
  • S

    Hallo Wutz,

    eine kleine Frage noch zu deinem sehr hilfreichen Link:

    Ich habe noch eine Frage bzgl. deiner Vergleichsfunktion:

    int
comp (const void *p1, const void *p2)
{
    const data2d d1 = *(const data2d*)p1;
    const data2d d2 = *(const data2d*)p2;
    double x1 = d1.x,y1 = d1.y,x2 = d2.x, y2 = d2.y;

    if( x1 < x2 ) return -1;  // Bedingung 1
    if( x1 > x2 ) return 1;   // Bedingung 2
    if( y1 < y2 ) return -1;  // Bedingung 3
    if( y1 > y2 ) return 1;   // Bedingung 4
    return 0;                 // Bedingung 5
}

    Kann man die Bedingungen 1 bis 5 auch so schreiben:

    if( x1 < x2 ) return -1;       // Bedingung 1
    else if( x1 > x2 ) return 1;   // Bedingung 2
    else if( y1 < y2 ) return -1;  // Bedingung 3
    else if( y1 > y2 ) return 1;   // Bedingung 4
    else return 0;                 // Bedingung 5

    Wäre für mich einfacher, wenn ich mein Code wieder nach drei Jahren angucke ;).

    Beste Grüße,
    simsa

    P.S. ich bin gerade unterwegs und habe keinen Compiler zur Hand 😢

    0

  • Ja.

    0
  • S

    danke und einen schönen abend.

    grüße,
    simsa

    0
Anmelden zum Antworten