AVR-Sortieralgorythmus der nicht ewig dauern darf

[Marco (Gast)]

Hallo, liebe Forumianer !

Ich habe mal wieder einen kleinen Brocken in einem AVR-Programm zu
knacken :
Es geht um das Sortieren von Zahlen. Der AVR soll aus seinem E2P
insgesamt 762 Werte herauslesen, welche zwischen 0 und 99999 liegen
können. Als Endergebnis soll ein Array forlaufend in steigender
Reihenfolge die E2P-Adressen enthalten, in dessen Zelle der jeweils
nächstgrößeren Wert steht.

Nun könnte ich zwei Schleifen ineiander schachteln, die eine von
0-99999, die andere 0-762. Das beduetet jedoch, das ca. 76Mio
Vergleichsopertionen durchgeführt werden müssen. Dazu kommt noch das
adressieren, lesen, schreiben, etc...
Damit ist mein Mega128 mit 8Mhz bestimmt eine halbe Minute damit
beschäftigt !!
Das ist viel zu lange. Hat jemand eine andere Idee zu einem
Algorythmus,wo's schneller geht (2 Sek. würde ich mir ja noch gefallen
lassen...)

Danke und VG Marco

[Aleksej Kiselev (Gast)]

Ich hab nicht verstanden, wozu du 76Mio Operationen brauchst. Sogar mit
dem einfachsten Sortieralgorythmus in dem ungünstigstem Fall wird es
nicht mehr als (1+2+..+761)= ca. 290000 Vergleichsoperationen brauchen.
Da wird selbst das Auslesen viel länger dauern.

[Marco (Gast)]

Danke Aleksej
Vielleicht sehe ich den Wald vor lauter Bäumen nicht...
Es sind 762 völlig verschiedene, oder auch gleiche Werte zwischen 0 und
99999. Kannst Du mir bitte dieses ein wenig mehr auswalzen, damit auch
ich das verstehe. Wäre ja genial !
Danke und VG MArco

[Michael (Gast)]

googel mal nach bubblesort. Da müßte ein interesanter Artikel bei sein.
Meine Bubblesort-Routine finde ich leider nicht.
Michael

[Aleksej Kiselev (Gast)]

Die erste Zahl vergleichst du nicht, dann nimmst du die zweite Zahl und
die sollst du mit der ersten vergleichen, das macht eine Operation,
jetzt hast du eine Reihenfolge aus zwei Zahlen (A und B z.B. A ist <
als B). Jetzt nimmst du die dritte Zahl C. Jetzt sollst du C mit A
vergleichen. Wenn C kleiner ist, dann hast du Glück gehabt und brauchst
ja keine weitere Vergleichungen. Wenn nicht, dann vergleichst du C mit
B, aber sogar in diesem Fall brauchst du nur 2 Operationen. So was
nennt man Bubblesort. Es gibt auch weitere Sortiermöglichkeiten, die
mehr komplizierter sind, aber die brauchst du wahrscheinlich nicht.

[Marco (Gast)]

Danke Euch beiden.
Ich habe eine schöne Seite beim googlen nach bubblesort gefunden,
wo bubblesort und weitere sehr gut erklärt, und Beispiele vorhanden
sind. Bubblesort läßt sich einfach realisieren, wobei Insertationsort
auch brauchbar und einfach zu implementieren ist.
Setze mich heute Abend gleich ran...

VG Marco

[Tobias Schilgen (Gast)]

Bubble Sort?? Das ist doch so ziemlich der langsamste Algorithmus,
den es gibt (quadratischer Aufwand: O(n*n), d. h. bei n zu sortierenden
Zahlen
braucht man C  n  n Vergleichsoperationen) - besser wäre der
QuickSort oder HeapSort (google) - die sind auch relativ einfach zu
implementieren und benötigen lediglich O(N * log2(N) = C*N*log2(N))
Rechenoperationen - also in diesem Fall C  762  log2(762) Dabei ist C
eine Konstante (log2() = Logarithmus zur Basis 2).

Tobias.

[Aleksej Kiselev (Gast)]

2Tobias Schilgen:
Wenn es um kleine Datenmenge geht, dann ist es viel wichtiger, ob der
Algorithmus einfach zu realisieren ist.