AVR-Sortieralgorythmus der nicht ewig dauern darf

Marco Gast #106758 
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 Langsamer Modus Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
Aleksej Kiselev Gast #106759 
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 Melden Danke
Marco Gast #106760 
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 Melden Danke
Aleksej Kiselev Gast #106762 
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 Melden Danke
Marco Gast #106763 
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 Melden Danke
Tobias Schilgen Gast #106764 
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 Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 22 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.