servus

hab folgendes problem:
muss ein 2D array sortieren nach einer bestimmten spalte:
hab ein array 8 spalten und n Zeilen, soll jenes nach der 7 spalte aufsteigend sortieren

mein algorithmus hätte so ausgesehen
(array ist bereits befüllt)

for (int i=0; i<participants-1;i++) // participants = anzahl der zeilen
{
if (dataTable[i][6]<= dataTable[i+1][6])
{
for (int j=0;j<dataTable[0].length;j++)
{
dataTable1[0][j]=dataTable[i][j];
}
for (int j=0;j<dataTable[0].length;j++)
{
dataTable[i][j]=dataTable[i+1][j];
}
for (int j=0;j<dataTable[0].length;j++)
{
dataTable[i+1][j]=dataTable1[0][j];
}

}
}

leider sortiert es absolut nicht so wie ich es will, es sortiert außerdem nur teilweise, sitze jetzt schon 5 stunden daran und komm einfach nicht drauf, kann mir vielleicht jemand helfen ?

danke schon mal im vorraus

mfg
Freddie

qsort

QSort hat zwar O(N²), aber ich glaub im Mittel log(2, N) oder so. Also eigentlich ziemlich gut, ausser halt im Worst-Case.

edit: musst wohl oder über den Array, zumindest zum Suchen, so umstrukturieren, dass die 2. Spalte die erste Dimension ist

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/

danke, aber das problem ist ich soll es selber schreiben ;-)

und keinen vorgefertigten sortieralgorithmus benutzen

mfg
Freddie

euer lehrer / dozent verlangt von euch also einen neuen sortieralgorithmus..? weil es ja so wenige gibt, ich glaube kaum

nimm bubblesort, das ist einfach nachzuvollziehen und für eine sinnlose aufgabe mehr als genug

http://www.sortieralgorithmen.de/

shielding people from their own stupidity is an evolutionary step backwards anyway.

/* God is dead!............Nietzsche */
/* Nietzsche is dead!......God */
/* Nietzsche is God!.......The Dead */

Tja, ein O(N)-Sortieralgorithmus wäre doch was Feines, gell? ;)
Leider ist General-Purpose-Sortieren schneller als O(N log N) wohl nicht möglich, und dein Algorithmus sieht aus wie ein nicht ganz zu Ende gedachter Bubble Sort. Abgesehen davon würde ich versuchen, das Hin- und Herkopieren von Zeilen irgendwie zu abstrahieren (in eine Funktion, oder durch Assignment-Overload, oder wie auch immer). Diese inneren for()-Schleifen zum Kopieren machen das Programm extrem unübersichtlich.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Mal sehen, dann such' ich mal meine alten Info I Unterlagen raus und schreibe doch mal ganz feinili nen abstraktes QSort. Obwohl, geht schlecht ohne Mengenzeichen... oO

Ne, find' ich nicht mehr, dann halt einfaches Bubblesort in C:

Quellcode:void bsort(int * p, int i) // p = data, i = length
{
  int a; // iterator
  int c; // changed something

  do
  {
    c = 0;

    for(a = 1; a < i; ++a)
    {
      if(p[a] > p[a - 1])
      {
        int tmp = p[a]; // swap
        p[a] = p[a - 1]; // .
        p[a - 1] = tmp; // .

        c = 1; // changed = yes
      }
    }
  }
  while(c);
}Ich hoffe mal, ich habe mich nicht mal wieder verdacht und blamiere mich jetzt.

Was zur Laufzeit: im Mittel N², also gaaanz schlecht.

BTW: Bei qsort musst du nen Callback machen, ist doch was eigenes. >D

Nochmal edit nur für CN. *friedenspfeiferauch* >D

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/

seit wann gibts in c bool?
und seit wann geht sowas in c: for(int i = ..; .. ; ..)

@Black/OneStone: Ich habe gelernt, dass eine polynomiale Zeitkomplexität (z.B. N²) noch in Ordnung ist, und nicht ganz schlecht. Ganz schlecht wäre eine exponentielle Zeitkomplexität oder noch viel schlimmer eine der Form N^N oder sogar N!^N!. Solche Programme sollte man gar nicht erst laufen lassen, da man dann für n=6 schon eine Zeitkomplexität im Bereich von 3*10^249 erhält...
Gut ist eine affine / proportionale (lineare) oder logarithmische Zeitkomplexität. Konstante Zeitkomplexität wäre optimal, sollte aber bei Listen/Arrays unmöglich sein.

Das Problem der Sortierung eines zweidimensionalen Arrays sollte mit dem der Sortierung eines eindimensionalen Arrays identisch sein, du sortierst ja nur nach einer der beiden Dimensionen. Wenn man nach beiden Dimensionen sortiert lässt sich das aber auf die Sortierung eines eindimensionalen Arrays zurückführen.

Schwierig wird es nur dann, wenn ein zweidimensionales Array eindimensional gespeichert ist und sortiert werden soll, dann ist die Addressierung nämlich kompliziert.

Entities: HL | HL²
Kompilierfehler
r_speeds | mehr über r_speeds

Hrm, Levi, das Problem ist nur das man mit ein bisschen Denken oft zu ner logarithmischen Lösung kommen kann, aus Sicht eines Informatikers ist N² absolut Tabu, von N^N will ich garnicht erst reden.

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/

OneStone: Sofern ich das richtig in Erinnerung habe, bezeichnet man mit Bubblesort einen Algorithmus, der aus einem Array das "kleinste" Element heraussucht, an den Anfang kopiert, und dann nach dem selben Prinzip die restlichen N-1 Elemente des Arrays sortiert. Oder, als Schleife formuliert: Suche das kleinste Element von array[i..N] und verschiebe es an die Position array[i], für i von 0 bis N-1.

Dein Algorithmus macht zwar etwas ganz ähnliches und hat die gleiche algorithmische Komplexität, ist aber trotzdem, soweit ich das auf den ersten Blick sehen kann, nicht so effizient, weil er die Elemente öfter herumkopiert. Bubblesort macht im schlimmsten Fall N Kopieroperationen, dein Algorithmus im schlimmsten Fall N^2.

Ach ja: Sortieren kann nicht schneller als O(N) sein, weil man ja jedes Element mindestens einmal anschauen muss. Ein allgemein anwendbarer Sortieralgorithmus muss denke ich mal auch langsamer sein als O(N), weil man ja jedes Element dann wiederum mit den anderen Elementen vergleichen muss - allerdings habe ich da auf die schnelle keinen Beweis.

In speziellen Fällen ist es aber möglich, in O(N) zu sortieren, und zwar dann, wenn man jedem Element einen eindeutigen Integer, nachdem sortiert werden soll, zuordnen kann. Kann man z.B. jedem Element einen Wert von 0 bis 255 zuweisen, so kann man die Liste mit N Elementen in eine Hashmap mit 256 Einträgen hineinsortieren, wobei man jedes Element genau einmal betrachtet. In der Praxis kommt sowas natürlich kaum vor.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Doch, in Hashtables. Na jedenfalls ist das, was ich da oben gepostet habe, dass was man uns in der Uni als BubbleSort eingetrichtert hat.

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/

Hashtables haben typischerweise nichts mit Sortieren in dem Sinn zu tun. Natürlich sortieren sie strenggenommen auch, aber ich habe noch nie davon gehört, dass das jemand tatsächlich als "Sortieren" bezeichnet, weil man mit dem Endresultat letztendlich wenig anfangen kann (um genau zu sein: je besser die Hashfunktion ist, desto weniger kann man mit dem Ergebnis zum Sortieren anfangen).

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Black: Ich glaube, du hast Bubblesort mit dem Straight Insert Algo verwechselt. In deinem Falle einen SI-Algo ohne Dummyfeld! Bubblesort sieht nämlich so aus:

Quellcode:int* bsort(int a[], int n)
{
    int  i, j, r, temp;

    r = n;    // Evtl. finde im ersten Durchlauf keine Vertauschung statt

    while(r > 1)
    {
        j = 1;

        for(i=1; i<r; i++)
        {
            if(a[i] > a[i+1])
            {
                temp = a[i+1];
                a[i+1] = a[i];
                a[i] = temp;
                j = i;   // Vertauschung merken
            }
            
            r = j;   // Letzte Vertauschung in diesem Durchlauf
        }
    }

    return a;
}Aus meinen staubigen Akten hervorgekramt...

Hier mal eine Liste der (mir) bekannten Algos zum Sortieren interner Listen:

- Straight Insert
- Shellsort
- Bubblesort
- Quicksort
- Heapsort
- Straight Select

Und weil Tron mich noch nervte damit:

- Mergesort
- 2-way-Sort

:D

K:R-I)Z++
"CSS ist cascading style sheets. Und nicht so'n Ranzspiel." - dp
In memory of Voice († 2005/03/30)

Straight Insert ist dann wohl das, was ich unter "insertion sort" kenne...

Genau das würd ich auch für kleine Arrays verwenden. Bubble ist nicht so der Hammer. Am simpelsten ist eigentlich selection sort, was manchal sogar besser geeignet sein kann, als qsort (z.B. sag mir die 10 meist verkaufen CDs aller Zeiten...).

cu
Matze

BattleTech-MOD:
http://bthl.unitedgaming.net/

@ Kriz

und wie schreib ich den bubble sort jetzt auf ein [][] array um ?

damit er halt immer die komplette zeile vertauscht anstatt nur den einen wert.

mfg
Freddie

Erstmal anstatt des simplen > Operators beide Strings über ne Schleife Zeichen für Zeichen vergleichen. Wenn ein Zeichen in der Zeile vorher höher geordnet ist (vom ASCII Wert her oder was immer du willst) musste die Strings dann entweder durch Pointer Manipulation in der ersten Dimension vertauschen... oder mit realloc und strcpy arbeiten (n bissl aufwendig =))

Kriz, warum beginnst du beim Index 1 zu suchen? Tippfehler?
Soll das erste Element irgendwelche speziellen Informationen enthalten, die du jetzt nicht berücksichtigt hast?

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

Nein, aus der Implementierung heraus war Feld 0 ein Dummyfeld. Man kann das natürlich nach Belieben ab Index 0 umformen...

K:R-I)Z++
"CSS ist cascading style sheets. Und nicht so'n Ranzspiel." - dp
In memory of Voice († 2005/03/30)