Mehrdimensionalen Array sortieren

[Hans Thomas Vogler]

Problem: eine DB wird in einem mehrdimensionalen Array gespeichert.

Alles bestens, sogar die Suchmaschine flutscht wie Glatteis.

Nur: wie sortiere ich? Einen mehrdimensionalen Array kann ich nicht direkt sortieren, sondern muß die jeweilige Instanz aus allen Datensätzen auslesen und einem neuen Vektor übergeben. Aus der ermittelten Reihenfolge kann ich den Array kopieren und sortiert zurückgeben.

Das größte Problem: Mehrfachnennungen. Ich muß beim Kopieren des DB-Arrays also erst mal feststellen, ob der entsprechende Wert schon mal vorkommt, wenn ja wie oft, und dann den richtigen Vektor aus dem Original-Array saugen.

Bislang stehe ich im Wald. Mehrere Lösungsansätze habe ich wieder verworfen, weil alles nur so lala fungste und eine Veränderung der Anzahl der Datensätze im DB-Array fatale Auswirkungen hatte.

Hoffe, es kann mir jemand weiterhelfen

cu
HTV

[Harry]

Hoi !

Problem: eine DB wird in einem mehrdimensionalen Array gespeichert.

// as: array zum sortieren

temparray = new array();

function asort(spalte)
{
   for(i=0; i<as.length; i++)
   { ta(i);
     for(j=i+1; j<as.length; j++)
     { if(temparray[i][spalte]>as[i][spalte])
        ta(j); }
     at(i);
}

function ta(i)
{ for(j=0; j<as[i].length; j++)
   temparray[i][j] = as[i][j]; }

function at(i)
{ for(j=0; j<temparray.length; j++)
   as[i][j] = temparray[i][j]; }

Diese funktion würde das zweidimensionale Array "as" alphabetisch nach dem Inhalt von "spalte" sortieren. Keine Ahnung ob's geht,ich kann's hier leider nicht ausprobieren.

Ciao,

Harry

[Harry]

Oh mann ...

eindeutig überarbeitet, soviel Mist wie ich heute produziere ... (ich sollte aufhörn für heute)

// as: array zum sortieren

temparray = new array();

function asort(spalte)
{
   for(i=0; i<as.length; i++)
   { ta(i);
     for(j=i+1; j<as.length; j++)
     { if(temparray[i][spalte]>as[i][spalte])
        ta(j); }
     at(i);
}

function ta(i)
{ for(j=0; j<as[i].length; j++)
   temparray[i][j] = as[i][j]; }

Was ein Käse ...

temparray[j] = as[i][j]; }

... ist richtig

function at(i)
{ for(j=0; j<temparray.length; j++)
   as[i][j] = temparray[i][j]; }

Und der gleiche Käse nochmal:

as[i][j] = temparray[j]; }

... ist richtig.

Ciao,

Harry
(übermüdet)

[Lutz T.]

Hoi !

Hallo,
ich schätze mal, das wird nicht gehen.

Problem: eine DB wird in einem mehrdimensionalen Array gespeichert.

// as: array zum sortieren

temparray = new array();

function asort(spalte)
{
   for(i=0; i<as.length; i++)
   { ta(i);

danach ist temparray[i]=as[i]

for(j=i+1; j<as.length; j++)
     { if(temparray[i][spalte]>as[i][spalte])

ist stets gleich, da temparray[i]=as[i]

ta(j); }

wird nie ausgeführt

at(i);

schreibt temparray[i] wieder nach as[i]

}

-> Array hat hinterher die gleiche Reihenfolge, wie vorneweg

function ta(i)
{ for(j=0; j<as[i].length; j++)
   temparray[i][j] = as[i][j]; }

function at(i)
{ for(j=0; j<temparray.length; j++)
   as[i][j] = temparray[i][j]; }

Diese funktion würde das zweidimensionale Array "as" alphabetisch nach dem Inhalt von "spalte" sortieren. Keine Ahnung ob's geht,ich kann's hier leider nicht ausprobieren.

Ciao,

Harry

Ich würde die Arrays auch nicht direkt sortieren, denn wenn viele Spalten da sind, wird das ziemlich langsam, sondern ein zusätzliches eindimensionales Reihenfolge- oder Rank-Array erzeugen. Es ist noch zu beachten, daß es verschiedene Sortieralgorithmen gibt und die schnellsten sind dabei nicht unbedingt die _besten_. Für deine Zwecke ist es sicherlich sinnvoll, einen Sortieralgorithmus zu verwenden, bei dessen Anwendung die bisherige Sortierung beim Auftreten gleicher Werte erhaltenbleibt. Das brauchst Du z.B. wenn Du nach geburtstag sortieren willst, und die drei Spalten Jahr, Monat und Tag hast. Dann sortiere zuerst das Array nach Tag. Danach nimm das Array von neuem und sortiere nach Monat und dann sortiere wieder von neuem nach Jahr, und heraus kommt ein Array das nach Geburtstag sortiert ist. Bei den schnellsten Algorithmen Quicksort und Mergesort würde das nicht klappen, weil die die Reihenfolge beim Sortieren bei gleichen Werten nicht unverändert lassen, deshalb wäre da einer von den _klassischen_ Algorithmen Insertion- Selection- oder Bubble-Sort vorzuziehen. Ich weiß jetzt nicht genau, welcher Algorithmus wie heißt (verwechsle das immer und bin jetzt zu faul um aufzustehen und in einem Buch nachzugucken), im folgenden ist jedenfalls mal der Code des Alg's, den ich empfehlen würde:

var i,j,t,len=Array2D.length
Rank=new Array(len)
for (i=0; i<len; i++) Rank[i]=i;

function SortAsc(spalte)
{ for (i=0; i<len-1; i++)
  { for (j=len-1; j>i; j--)
    { if (Array2D[Rank[j-1]][spalte]>Array2D[Rank[j]][spalte])
      { t=Rank[j-1];
        Rank[j-1]=Rank[j];
        Rank[j]=t;
      }
    }
  }
}
function SortDesc(spalte)
{ for (i=0; i<len-1; i++)
  { for (j=len-1; j>i; j--)
    { if (Array2D[Rank[j-1]][spalte]<Array2D[Rank[j]][spalte])
      { t=Rank[j-1];
        Rank[j-1]=Rank[j];
        Rank[j]=t;
      }
    }
  }
}

Wenn Du ein Array zur Hand hast, kannst Du das gleich mal testen mit
SortAsc(0);
for (i=0; i<len; i++) alert(i+": "+Array2D[Rank[i]][0]);
SortDesc(0);
for (i=0; i<len; i++) alert(i+": "+Array2D[Rank[i]][0]);

Die Werte müßten dann zuerst steigend und dann fallend geordnet sein, wenn ich mich nicht vertan habe.

Gruß, Lutz.

[Harry]

Hoi

ich schätze mal, das wird nicht gehen.

Stimmt. Da haben sich leider noch mehr Fehler eingeschlichen (ich sollte es mir abgewöhnen, derartigen Code zu posten wenn ich ihn nicht ausprobieren kann) ...

// as: array zum sortieren

temparray = new array();

function asort(spalte)
{
   for(i=0; i<as.length; i++)
   { ta(i);
danach ist temparray[i]=as[i]

Ne (siehe auch erste Nachtrag (<?m=31481&t=5641>)

temparray bekommt die Werte aus as[i] zugewiesen

for(j=i+1; j<as.length; j++)
     { if(temparray[i][spalte]>as[i][spalte])
ist stets gleich, da temparray[i]=as[i]

Käse freilich.

die Zeile muß auch ...

{ if(temparray[spalte]>as[j][spalte])

heißen.

ta(j); }
wird nie ausgeführt

jetzt schon.

at(i);
schreibt temparray[i] wieder nach as[i]

jetzt nimmer. Jetzt wird der garantiert kleinste Wert, der nun in Temparray steht, in das Array as[i] geschrieben. Nun fehlt da aber noch eine Zeile, die den Wert aus as[i] sichert und an die Stelle schreibt, wo vorher der jetzige Wert für as[i] stand.

}
-> Array hat hinterher die gleiche Reihenfolge, wie vorneweg

Nochmal der ganze Käse im Überblick:

// as: array zum sortieren

var temparray = new array();
var lastchangedj = "";

function asort(spalte)
{
  for(i=0; i<as.length; i++)
  { ta(i);
    lastchangedj=i;
    for(j=i+1; j<as.length; j++)
    { if(temparray[spalte]>as[j][spalte])
      { lastchangedj = j;
         ta(j); }
    }
    if(i!=lastchangedj) ch(i, lastchangedj);
    at(i);
  }
}

function ta(i)
{ for(j=0; j<as[i].length; j++)
    temparray[j] = as[i][j]; }

function at(i)
{ for(j=0; j<temparray.length; j++)
   as[i][j] = temparray[j]; }

function ch(i,j)
{ for(k=0; k<as[i].length; k++)
   as[j][k] = as[i][k]; }

Jetzt sollte es funktionieren (ich hab leider immer noch keine Möglichkeit, das richtig auszuprobieren)

[...] Code des Alg's, den ich empfehlen würde:

var i,j,t,len=Array2D.length
Rank=new Array(len)
for (i=0; i<len; i++) Rank[i]=i;

function SortDesc(spalte)
{ for (i=0; i<len-1; i++)
  { for (j=len-1; j>i; j--)
    { if (Array2D[Rank[j-1]][spalte]<Array2D[Rank[j]][spalte])
      { t=Rank[j-1];
        Rank[j-1]=Rank[j];
        Rank[j]=t;
      }
    }
  }
}

Schaut mir auf den ersten Blick so ein bißl nach einer abgekürzten Schreibweise von meinem Ding aus ... Werd's bei Gelgenheit mal ausprobieren :-)

Ciao,

Harry

[Lutz T.]

Hallo Harry,

Nochmal der ganze Käse im Überblick:

[snip]

Jetzt sollte es funktionieren (ich hab leider immer noch keine Möglichkeit, das richtig auszuprobieren)

Hast Du doch, siehe unten.

[...] Code des Alg's, den ich empfehlen würde:

[snip]

Schaut mir auf den ersten Blick so ein bißl nach einer abgekürzten Schreibweise von meinem Ding aus ... Werd's bei Gelgenheit mal ausprobieren :-)

Isses nich, siehe Beispiel. Dein Code is ne Variante von Selection-Sort, und meiner is ne Variante von Bubble-Sort (hab extra noch mal nachgeguckt). Außerdem wird bei Dir das Array direkt sortiert (da die Positionen der Einträge geändert werden), und bei mir indirekt (die Einträge bleiben an ihren Positionen stehen und die Reihenfolge wird durch ein zusätzliches 1D-Rank-Feld definiert).
Der Selection-Sort hat die (für eineige Anwendungsfälle)unangenehme Nebenwirkung, daß bei Gleichheit von Werten die bisherige Reihenfolge teilweise verändert wird.

Gruß, Lutz

<HTML><HEAD></HEAD><BODY>
<script language="JavaScript">

var as=new Array(10);

//Algorithmus ala Lutz T.

var i,j,t,len=as.length
Rank=new Array(len)
for (i=0; i<len; i++) Rank[i]=i;

function SortAsc(spalte)
{ for (i=0; i<len-1; i++)
  { for (j=len-1; j>i; j--)
    { if (as[Rank[j-1]][spalte]>as[Rank[j]][spalte])
      { t=Rank[j-1];
        Rank[j-1]=Rank[j];
        Rank[j]=t;
      }
    }
  }
}

function SortDesc(spalte)
{ for (i=0; i<len-1; i++)
  { for (j=len-1; j>i; j--)
    { if (as[Rank[j-1]][spalte]<as[Rank[j]][spalte])
      { t=Rank[j-1];
        Rank[j-1]=Rank[j];
        Rank[j]=t;
      }
    }
  }
}

function Init()
{ for(i=0; i<as.length; i++)
  { as[i]=new Array(3);
    as[i][0]=Math.floor(Math.random()*3)+1970;//Jahr
    as[i][1]=Math.floor(Math.random()*6)+3;//Monat
    as[i][2]=Math.floor(Math.random()*10)+10;//Tag
  }
}

//Algorithmus ala Harry

var temparray = new Array();
var lastchangedj = "";

function asort(spalte)
{
  for(i=0; i<as.length; i++)
  { ta(i);
    lastchangedj=i;
    for(j=i+1; j<as.length; j++)
    { if(temparray[spalte]>as[j][spalte])
      { lastchangedj = j;
         ta(j); }
    }
    if(i!=lastchangedj) ch(i, lastchangedj);
    at(i);
  }
}

function ta(i)
{ for(j=0; j<as[i].length; j++)
    temparray[j] = as[i][j]; }

function at(i)
{ for(j=0; j<temparray.length; j++)
   as[i][j] = temparray[j]; }

function ch(i,j)
{ for(k=0; k<as[i].length; k++)
   as[j][k] = as[i][k]; }

//Aufruf und Ausgabe
zn=new Array("Jahr","Monat","Tag");
document.open();
Init();
document.writeln("10 Geburtstage ungeordnet:<table border cellspacing=0>");
for (j=0; j<3; j++)
{ document.writeln("<tr><td>"+zn[j]+"</td>");
  for (i=0; i<as.length; i++)
    document.writeln("<td>"+as[i][j]+"</td>");
  document.writeln("</tr>");
}
document.writeln("</table>");
SortAsc(2);
SortAsc(1);
SortAsc(0);
document.writeln("10 Geburtstage geordnet nach Lutz T. (2,1,0) mittels Bubble-Sort:<table border cellspacing=0>");
for (j=0; j<3; j++)
{ document.writeln("<tr><td>"+zn[j]+"</td>");
  for (i=0; i<as.length; i++)
    document.writeln("<td>"+as[Rank[i]][j]+"</td>");
  document.writeln("</tr>");
}
document.writeln("</table>");
asort(2);
asort(1);
asort(0);
document.writeln("10 Geburtstage geordnet nach Harry (2,1,0) mittels Selection-Sort:<table border cellspacing=0>");
for (j=0; j<3; j++)
{ document.writeln("<tr><td>"+zn[j]+"</td>");
  for (i=0; i<as.length; i++)
    document.writeln("<td>"+as[i][j]+"</td>");
  document.writeln("</tr>");
}
document.writeln("</table>");
document.close();
</script>
</BODY></HTML>

[Harry]

Hoi !

Jetzt sollte es funktionieren (ich hab leider immer noch keine Möglichkeit, das richtig auszuprobieren)
Hast Du doch, siehe unten.

Ne :-) Ich sitz nämlich an einem Internetterminal, von dem aus ich zur Zeit keine Seiten editieren kann, und von dem aus ich auch lokal keinen Zugriff auf die Platte hab (ohne mich durch irgendwelche Tricks unbeliebt zu machen ;-)

Aber vielen Dank für den Code, werd ich dann mal ausprobieren. Aus welchem Buch hast Du den, das klingt nämlich recht interessant :-)

Ciao,

Harry

[Lutz T.]

Hoi !

Hallo Harry,

Jetzt sollte es funktionieren (ich hab leider immer noch keine Möglichkeit, das richtig auszuprobieren)
Hast Du doch, siehe unten.

Ne :-) Ich sitz nämlich an einem Internetterminal, von dem aus ich zur Zeit keine Seiten editieren kann, und von dem aus ich auch lokal keinen Zugriff auf die Platte hab (ohne mich durch irgendwelche Tricks unbeliebt zu machen ;-)

Ich hab da mal was programmiert, nämlich einen online-code-tester, aufrufbar unter < www.tu-chemnitz.de/~luta/codetest.html> da kannst Du den folgenden code unten reinpacken und ausprobieren.
Ich denke, das Progrämmchen könnte man eigentlich auch auf den SELFHTML-Server stellen, für Leute wie Dich ohne lokalen Plattenzugriff wäre das bestimmt eine Hilfe.

Aber vielen Dank für den Code, werd ich dann mal ausprobieren. Aus welchem Buch hast Du den, das klingt nämlich recht interessant :-)

Das Buch heißt 'Kopf', da sind so einige Codes drin, und das allerbeste: da kommen auch abundzu Codes raus, die vorneweg gar nicht reingesteckt wurden.
Bei den Bezeichnungen der Algorithmen hab ich mir ein bißchen von Google helfen lassen(Suchbegriff: 'Insertion Selection Bubble Sort')

Ciao,

Harry

Gruß Lutz

Hier noch der JavaScript-Code zum Online-Testen:
-------------------------------------------------

var as=new Array(10);

//Algorithmus von Lutz T.

var i,j,t,len=as.length
Rank=new Array(len)
for (i=0; i<len; i++) Rank[i]=i;

function SortAsc(spalte)
{ for (i=0; i<len-1; i++)
  { for (j=len-1; j>i; j--)
    { if (as[Rank[j-1]][spalte]>as[Rank[j]][spalte])
      { t=Rank[j-1];
        Rank[j-1]=Rank[j];
        Rank[j]=t;
      }
    }
  }
}

function SortDesc(spalte)
{ for (i=0; i<len-1; i++)
  { for (j=len-1; j>i; j--)
    { if (as[Rank[j-1]][spalte]<as[Rank[j]][spalte])
      { t=Rank[j-1];
        Rank[j-1]=Rank[j];
        Rank[j]=t;
      }
    }
  }
}

function Init()
{ for(i=0; i<as.length; i++)
  { as[i]=new Array(3);
    as[i][0]=Math.floor(Math.random()*3)+1970;//Jahr
    as[i][1]=Math.floor(Math.random()*6)+3;//Monat
    as[i][2]=Math.floor(Math.random()*10)+10;//Tag
  }
}

//Algorithmus von Harry

var temparray = new Array();
var lastchangedj = "";

function asort(spalte)
{
  for(i=0; i<as.length; i++)
  { ta(i);
    lastchangedj=i;
    for(j=i+1; j<as.length; j++)
    { if(temparray[spalte]>as[j][spalte])
      { lastchangedj = j;
         ta(j); }
    }
    if(i!=lastchangedj) ch(i, lastchangedj);
    at(i);
  }
}

function ta(i)
{ for(j=0; j<as[i].length; j++)
    temparray[j] = as[i][j]; }

function at(i)
{ for(j=0; j<temparray.length; j++)
   as[i][j] = temparray[j]; }

function ch(i,j)
{ for(k=0; k<as[i].length; k++)
   as[j][k] = as[i][k]; }

//Aufruf und Ausgabe
zn=new Array("Jahr","Monat","Tag");
var win=window.open('','');
win.document.open();
win.document.write("<html><head></head><body>");
Init();
win.document.writeln("10 Geburtstage ungeordnet:<table border cellspacing=0>");
for (j=0; j<3; j++)
{ win.document.writeln("<tr><td>"+zn[j]+"</td>");
  for (i=0; i<as.length; i++)
    win.document.writeln("<td>"+as[i][j]+"</td>");
  win.document.writeln("</tr>");
}
win.document.writeln("</table>");
SortAsc(2);
SortAsc(1);
SortAsc(0);
win.document.writeln("10 Geburtstage geordnet nach Lutz T. (2,1,0) mittels Bubble-Sort:<table border cellspacing=0>");
for (j=0; j<3; j++)
{ win.document.writeln("<tr><td>"+zn[j]+"</td>");
  for (i=0; i<as.length; i++)
    win.document.writeln("<td>"+as[Rank[i]][j]+"</td>");
  win.document.writeln("</tr>");
}
win.document.writeln("</table>");
asort(2);
asort(1);
asort(0);
win.document.writeln("10 Geburtstage geordnet nach Harry (2,1,0) mittels Selection-Sort:<table border cellspacing=0>");
for (j=0; j<3; j++)
{ win.document.writeln("<tr><td>"+zn[j]+"</td>");
  for (i=0; i<as.length; i++)
    win.document.writeln("<td>"+as[i][j]+"</td>");
  win.document.writeln("</tr>");
}
win.document.writeln("</table>");
win.document.writeln("</body></html>");
win.document.close();

[Harry]

Hi Lutz :-)

Jetzt konnte ich das endlich ausprobieren, und jetzt hab ich auch verstanden, wo das Mißverständnis zumindest auf meiner Seite lag :-)
Ich dachte, es geht darum, das Array nur anhand einer einzigen Spalte zu sortieren und dabei die Assoziationen zu erhalten wohingegen Dein Algorithmus die anderen Spalten auch noch mit sortiert.

Ich glaube, das hast Du mir auch die ganze Zeit sagen wollen, aber irgendwie bin ich da wohl ein bißchen auf der Leitung gestanden ;-)

Ciao,

Harry

[Sven Rautenberg]

Moin!

Problem: eine DB wird in einem mehrdimensionalen Array gespeichert.

Kann die Datenbank nicht sortieren? Würde dir eine Menge Ärger ersparen, es selbst tun zu müssen. :)

- Sven Rautenberg

[Hans Thomas Vogler]

Moin!

Problem: eine DB wird in einem mehrdimensionalen Array gespeichert.

Kann die Datenbank nicht sortieren? Würde dir eine Menge Ärger ersparen, es selbst tun zu müssen. :)

• Sven Rautenberg

Hast Du keine Zeit zum Fertiglesen vor dem Antwort Schreiben?

Die HTML-Tabelle *IST* die DB.

mfg
HTV

[Sven Rautenberg]

Moin!

Hast Du keine Zeit zum Fertiglesen vor dem Antwort Schreiben?

Die HTML-Tabelle *IST* die DB.

In deinem gesamten Posting steht das Wort HTML nicht drin, auch nicht das Wort Tabelle.

Wenn du DB als Abkürzung für Datenbank verwendest, dann gehe ich davon aus, daß dahinter ein DBMS steht, ein Datenbankmanagementsystem. Also eines, welches z.B. per SQL befragt werden kann. Und da kann man ganz einfach sortieren.

Wenn du die Frage besser gestellt hättest, hätte ich anders geantwortet. :)

- Sven Rautenberg

[Calocybe]

Hi there!

Wenn du DB als Abkürzung für Datenbank verwendest, dann gehe ich davon aus, daß dahinter ein DBMS steht, ein Datenbankmanagementsystem. Also eines, welches z.B. per SQL befragt werden kann. Und da kann man ganz einfach sortieren.

Yoh, hatte genau denselben Gedankengang und mich gewundert, was er eigentlich will.

Wenn du die Frage besser gestellt hättest, hätte ich anders geantwortet. :)

"Wenn du eine weise Antwort verlangst, musst du vernünftig fragen."
   -- Johann Wolfgang von Goethe
(ja ja, ich wiederhole mich)

So long

[Hans Thomas Vogler]

** DANKESCHÖN! **

Habe das Problem gelöst, und zwar ganz anders:

Beim Erzeugen des zu sortierenden Vektors schreibe ich in die jeweilige Variableneinheit einfach die Zugriffszahl (entspricht der Position im ursprünglichen DB-Array) eingeleitet mit '#' mit in den Datumsextrakt. Dann lese ich beim Auslesen des Vektors statt des Datums die Laufnummer=Speicherposition im Original-Array als Adresse.

So sortiere ich ab sofort mehrdimensionale Arrays.

Danke trotzdem für die Mitarbeit. Das und andere Ergebnisse könnt Ihr ab demNeXt auf http://ww.4html.de vorfinden.

mfg
HaThoV