www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik AVR-Sortieralgorythmus der nicht ewig dauern darf


Autor: Marco (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Aleksej Kiselev (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Marco (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Michael (Gast)
Datum:

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

Autor: Aleksej Kiselev (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Marco (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Tobias Schilgen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Aleksej Kiselev (Gast)
Datum:

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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.