Quickdsort

sidt

Hallo Hallo der Anfänger ist wieder da
Ich habe eine frage zum quicksort bzw generell zum sortieren. Ich habe eine Datei die ich Spaltenweise sortieren muss also ungefährso
Vorher:

14, 36, 15
21, 98, 74
65, 354, 12
8, 9, 7
157, 658, 49

soll so sortiert werden

8, 9, 7
14, 36, 12
21, 98, 15
65, 354, 49
157, 658, 74

welchen sortier algorithmus soll man dafür am besten beenutzen und wie sage ich ihm das er in der Datei nur jede spalte sortieren soll.
Kann mann das ich einem Array machen oder muss ich im endeffekt 3 array aufmachen und dann wieder in die datei schreiben
Danke jetzt schon für die wiedereinmal großartige hilfe

hohesC

8, 9, 7
14, 36, 12
21, 98, 15
65, 354, 49
157, 658, 74

so sieht ja die Datei aus!

Könnte die Datei auch so aussehen:

...
1, 10, 4
2, 9, 12
...

oder sind die Zeilen so aufgebaut das immer die kleinsten von jeder Spalte eine Reihe bilden, dann die nächsten usw.?

Du könntest sie dann nämlich infach nach der ersten Zahl der Reihe sortieren.

mfg hohesC

sidt

nein die datei schaut ungefähr so aus

14, 36, 15
21, 98, 74
65, 354, 12
8, 9, 7
157, 658, 49

kann sich aber ändern und auch statt 3 zahlen pro linie 6 oder 7 haben
und das ergebnis soll so ausschauen

8, 9, 7
14, 36, 12
21, 98, 15
65, 354, 49
157, 658, 74

also ich muss von jeder zeile die ersten zahlen nehme und sortiere und dann jeweil die zweite zahl und am ende die dritte zahl

Blue-Tiger

EDIT: ups, hab erst jetzt richtig verstanden was du willst...

IMO wirst du um 3 Arrays, die du getrennt sortierst, nicht herumkommen

Sortieren laesst du dann am besten die Std-Funktion sort(). Kannst unter www.cppreference.com nachschauen was die so an Parametern uebernimmt.
Danach einfach die Datei wieder hinschreiben:

// wenn a[], b[] und c[] deine 3 Arrays sind, in arraylength die Laenge der Arrays
// und file ein gueltiger ofstream ist:
for (int i = 0; i < arraylength; ++i)
{
    file << a[i] << ", " << b[i] << ", " << c[i] << '\n';
}

Konfusius

also da du die zeilen nur nach der ersten zahl sortieren mußt würd ichs so machen.

zeilen als strings einlesen
die strings nach der ersten zahl sortieren. stichwort: sscanf(str,"%d",&i);
sortierte zeilen in zieldatei schreiben

damit wird die ganze speicherverwaltungs-wirtschaft weitestgehend überflüssig

die stdlib-sortierfunktion heißt übrigens qsort()

Konfusius

hatte wieder mal nichts besseres zu tun, als die programme ander leute zu schreiben

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

#define LINELEN_MAX 1024

char  *prgnam,
     **lines     = NULL;
int    num_lines = 0,
       max_lines = 0;

void
fatal (char *msg)
{
  if(!msg) msg=prgnam;
  perror(msg);
}

void
add_line (char *line)
{
  if(num_lines>=max_lines)
  {
    max_lines+=16;

    if(lines)
      lines=(char**)realloc(lines,num_lines*sizeof(char*));
    else
      lines=(char**)malloc(num_lines*sizeof(char*));
  }

  lines[num_lines++]=strdup(line);
}

void
read_lines (char *in_name)
{
  FILE *in;
  char buf[LINELEN_MAX];

  in=fopen(in_name,"r"); if(!in) fatal(in_name);

  while(fgets(buf,LINELEN_MAX,in))
    add_line(buf);

  if(ferror(in)) fatal(in_name);
  if(!feof(in) && buf[strlen(buf)-1]!='\n')
  {
    fprintf(
      stderr,
      "%s: zeile in eingabedatei ueberschreitet die "
      "maximale laenge von %d zeichen\n",
      prgnam,
      LINELEN_MAX);
  }
  fclose(in);
}

void
write_lines (char *out_name)
{
  FILE *out;
  int i;

  out=fopen(out_name,"w"); if(!out) fatal(out_name);

  for(i=0; i<num_lines; i++)
  {
    fputs(lines[i],out);
    if(ferror(out)) fatal(out_name);
  }

  fclose(out);
}

int
cmp_lines (const void *l1, const void *l2)
{
  int x1,x2;

  sscanf(*(char**)l1,"%d",&x1);
  sscanf(*(char**)l2,"%d",&x2);

  return x1-x2;
}

void
sort_file (char *in_name, char *out_name)
{
  read_lines(in_name);
  qsort(lines,num_lines,sizeof(char**),cmp_lines);
  write_lines(out_name);
}

void
main (int argc, char **argv)
{
  prgnam=argv[0];

  sort_file("C:\\in.txt","C:\\out.txt");
}

wie immer getestet mit visual müllhaufen. deshalb ohne gewähr.

sidt

Konfusius schrieb:

also da du die zeilen nur nach der ersten zahl sortieren mußt

Die Sache ist ich muss nicht nur die erste sortieren sondern auch die zweite zahl und die dritte zahl

Hi Konfusius,
hast du keine icq oder msn oder yahoo??? messanger??
ich muss dich mal was fragen, wie ich seh bist du gut im programmieren mit ansi C

c.rackwitz

konfusius:
beim strdup() bräuchtest beim beenden wieder ein free() je pointer.
sonst muss ich sagen, du lieferst ziemlich guten code ab.

sidt:
sortierung könnte für einen anfänger etwas schwierig sein aber doch nicht unüberwindbar.

mach dir doch einfach ne matrix (2d array). das musst du dynamisch mit malloc()s und den obligatorischen free()s aufbauen. da kommen dann die zahlen aus deiner datei rein. mit denen kannst du dann machen was du willst.

Konfusius

sidt schrieb:

Die Sache ist ich muss nicht nur die erste sortieren sondern auch die zweite zahl und die dritte zahl

dazu braucht du nur cmp_lines() anzupassen:

int
cmp_lines (const void *l1, const void *l2)
{
  int   x1,x2;
  char *ll1,*end1p,
       *ll2,*end2p;

  ll1=*(char**)l1;
  ll2=*(char**)l2;

  /* wenn reihen von beliebig vielen zahlen verglichen werden */
  /* sollen, dann gehts leider nicht mehr einfach mit sscanf() */
  do
  {
    x1=strtol(ll1,&end1p,0);
    x2=strtol(ll2,&end2p,0);

    /* abbrechen, wenn keine zahlen mehr vorhanden */
    /* tritt eigentlich nur bei syntaxfehler ein */
    if(end1p==ll1 || end2p==ll2) return 0;

    /* komma überlesen */
    ll1=strchr(end1p,','); if(!ll1) break; /* zeile zu ende */
    ++ll1;
    ll2=strchr(end2p,','); if(!ll2) break;
    ++ll2;
  }
  while(x1==x2);

  return x1-x2;
}

An Konfusius schrieb:

ich muss dich mal was fragen, wie ich seh bist du gut im programmieren mit ansi C

so gut bin ich nicht. ich mach das nur schon so lange. icq etc hab ich nicht. ich bin kein großer chat-fan. wenns was kommerzielles ist, dann muß ich leider passen. ich bin nur hobby-programmierer. spezielle kenntnisse, wie netzwerk/datenbank-programmierung etc, hab ich nicht.