AVR-Sortieralgorythmus der nicht ewig dauern darf

Marco Gast #106758
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Aleksej Kiselev Gast #106759
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Marco Gast #106760
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Aleksej Kiselev Gast #106762
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Marco Gast #106763
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Tobias Schilgen Gast #106764
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren