Hallo,
ich würde gerne die einzelnen Indexinhalte eines Arrays nach deren Größe sortieren. Kein Indexinhalt kommt innerhalb des Arrays mehrfach vor.
Gegeben:
byte tollesArray[5] = {0, 23, 1, 9, 50}
Gesucht:
byte Zielarray[5] = {0, 1, 9, 23, 50}
Wie macht man das?
Gruß Chris
Ähm.. danke.
'size' was not declared in this scope
Muss ich das über sizeof machen?
An welcher Stelle muss ich das Ausgangsbasisarray und an welcher Stelle das Zielarray eintragen?
Gruß Chris
byte tollesArray[5] = {0, 23, 1, 9, 50}; // Ausgangsbasis
byte Zielarray[5] = {0, 0, 0, 0, 0}; // Zielarray
void setup()
{
Serial.begin(9600);
ordnungs_Funktion();
delay(1000);
Serial.println(Zielarray[0]);
Serial.println(Zielarray[1]);
Serial.println(Zielarray[2]);
Serial.println(Zielarray[3]);
Serial.println(Zielarray[4]);
}
void loop()
{
}
void ordnungs_Funktion()
{
for (int k = 1; k < size; k++)
{
for (int i = 0; i a[i +1])
{
int temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
}
Das ist der sogenannte "Bubblesort" Algorithmus. Bubblesort ist am einfachsten zu implementieren, aber insbesondere bei sehr vielen zu sortierenden Elementen nicht das schnellste Sortierverfahren.
size ist in dem Fall die Anzahl der Elemente im Array.
Also int size=sizeof(tollesArray)/sizeof(tollesArray[0]); // Größe des gemamten Arrays in Bytes durch Größe eines Elements
Eine "Sortierung" erfolgt übrigens immer an Ort und Stelle, im selben Array. Als zusätzlicher Speicher wird nur Zwischenspeicher (Variable "temp") zur Aufnahme eines einzigen Elements beim Vertauschen von Elementen im Array benötigt.
hi,
und es gibt kein zielarray, es wird im ausgangsarray verändert...
gruß stefan
Danke, jurs.
Da in meinem Fall im Hintergrund mit nem Timer höhe Frequenzen berechnet werden, würde mir viel an einer schnellen Ausführung liegen.
Hast Du mir nen Tipp
Gruß Chris
PS: Kompiliert schonmal:
byte tollesArray[5] = {0, 23, 1, 9, 50}; // Ausgangsbasis
byte Zielarray[5] = {0, 0, 0, 0, 0}; // Zielarray
int size = sizeof(tollesArray)/sizeof(tollesArray[0]);
void setup()
{
Serial.begin(9600);
ordnungs_Funktion();
delay(1000);
Serial.println(Zielarray[0]);
Serial.println(Zielarray[1]);
Serial.println(Zielarray[2]);
Serial.println(Zielarray[3]);
Serial.println(Zielarray[4]);
}
void loop()
{
}
void ordnungs_Funktion()
{
for (int k = 1; k < size; k++)
{
for (int i = 0; i < size -1 - k; i++)
{
if (tollesArray[i] > tollesArray[i +1])
{
int temp = tollesArray[i];
tollesArray[i] = tollesArray[i + 1];
tollesArray[i + 1] = temp;
}
}
}
}
Edit: Ok- muss ich halt das tolle Array vorher ins Zielarray kopieren und dann dor die Sortierung vornehmen, aber das sollte ich hinbekommen. :)
Chris72622: Da in meinem Fall im Hintergrund mit nem Timer höhe Frequenzen berechnet werden, würde mir viel an einer schnellen Ausführung liegen.
Und was und warum willst du sortieren ? Was sind für dich "sehr viele zu sortierende Elemente" ? Was ist viel ? ( Es gibt schnellere Computer als einen Arduino ) Was soll der Arduino machen, wenn er schneller fertig ist ? ;)
Ich will sortieren, um in einem Array gespeicherte Tonhöhen auf bestimmte Floppy_Laufwerke umleiten zu können. Ist etwas kompliziert zu erklären, aber ich brauche das genau so.
Mehr als 999.
Ich möchte das Projekt mit einem Arduino realisieren und das wird auch so klappen, wenn diese Sortierung nicht länger als ca. 10 Mikrosekunden dauert. Es sollen übrigens lediglich 8 Indexe sortiert werden. :P
Die Dinge, welche durch Timerinterrupts ausgelöst werden bearbeiten.
Gruß Chris
Chris72622:
Da in meinem Fall im Hintergrund mit nem Timer höhe Frequenzen berechnet werden, würde mir viel an einer schnellen Ausführung liegen.Hast Du mir nen Tipp
Hat das Array immer nur 5 Elemente?
In dem Fall gibt es wohl keinen allgemeinen Sortieralgorithmus, der bei “gut gemischten Elementen” in den meisten Fällen viel schneller sein kann als Bubblesort.
Warum mußt Du das Array überhaupt in ein Zielarray kopieren und dann nur das Zielarray sortieren?
Kannst Du die einzelnen Werte nicht bereits beim Einfügen in das Array “sortiert einfügen”?
Schneller werden kannst Du insbesondere dann, wenn die Daten im Array nicht zufällig gleichverteilt vorkommen, sondern wenn Du über die Art der Daten irgendwelche Annahmen machen kannst. Wenn Du z.B. weißt, dass z.B. von fünf Werten immer zwei Werte unter 10 und zwei Werte über 10 liegen und nur ein Wert vollkommen beliebig ist, kannst Du wesentlich effektiver Sortieren (oder beim Erstellen des Arrays einfügen) als wenn Du gar keine Annahmen über die Daten im Array machen kannst.
Üblicherweise wird in einer ISR 1 Ereignis bearbeitet. Es geht also --wenn überhaupt-- darum, 1 neue Zahl zwischen schon vorhandenen 8 anderen richtig einzusortieren und eine andere dafür rauszuschmeissen? Das kann man sicher einen Tick schneller als der Standard-Algorithmus.
Bubblesort sollte man nur jemandem beibringen um Sortier-Algorithmen zu lernen und zu verstehen warum der schlecht ist. Selbst bei O(n²) Komplexität gibt es weit bessere Algorithmen wie Insertionsort (besonders wenn man sie auf dem PC mit modernen CPUs laufen lässt). Der beste Allaround Algorithmus ist Quicksort.
C++ (und auch AVR gcc) hat schon einen halbwegs fertigen Quicksort:
http://www.nongnu.org/avr-libc/user-manual/group__avr__stdlib.html#gafd4bf2faec43342e7ad3d2ab37bac1fe
http://www.cplusplus.com/reference/cstdlib/qsort/
Man muss nur eine Vergleichs-Funktion implementieren und diese als Parameter übergeben. Was bei Integern trivial ist. 
In zweiten Links ist ein fertiges Beispiel um ein int-Array zu sortieren
Wobei es bei so wenigen Elementen wahrscheinlich keine so große Rolle spielt Da kann es sein dass Quicksort seine Vorteile wieder größtenteils verspielt.
Wobei es bei so wenigen Elementen wahrscheinlich keine so große Rolle spielt
Richtig teuer wird es, wenn von qsort deine (sicher triviale) Vergleichsfunktion aufgerufen wird, mit 2 Parametern auf dem Stack, wenn der Compiler das nicht wegoptimiert kriegt.
Aber mein Punkt ist, dass der Ansatz, ein array erst irgendwie zusammenzustellen und dann zu sortieren, vermutlich Unsinn ist. Unsinn zu optimieren ist erst recht Unsinn.
Ja, das schon beim Einfügen zu sortieren wäre natürlich sinnvoller :)
Chris72622: 2. Mehr als 999.
- Ich möchte das Projekt mit einem Arduino realisieren und das wird auch so klappen, wenn diese Sortierung nicht länger als ca. 10 Mikrosekunden dauert. Es sollen übrigens lediglich 8 Indexe sortiert werden. :P
Also bei 999 Elementen würdest du vermutlich Ram-Probleme bekommen. Das erscheint mir mehr dein Wertebereich zu sein. Du schreibst von 8 Indexe. Also müssen 8 Elemente sortiert werden?
Im Falle von 8Elementen ist Bubblesort gar nicht so übel.
Wenn allerdings die Elemente schon sortiert sind und immer nur einzelne Elemente einsortiert oder aussortiert werden müssen, dann dürfte ein Einfüge-Algorithmus besser sein. Ein weiterer Weg wäre, im Voraus die Elemente zu sortieren.
Hallo,
bist du dir bei den 10µs sicher? Das wäre 100.000mal pro Sekunde. Das ist weit außerhalb des akkustisch sinnvollen Bereich. Musik liegt doch eher im Bereich 100-2000Hz. Bei 2000Hz hättest du 500µs Zeit.
Wenn das bestehende Array schon sortiert ist und nur ein Wert einsortiert werden muss, dann ist Bubblesort nach einem Durchgang fertig .
Der Vollständigkeit halber für die blutigen Anfänger (wie z.B. mich):
byte tollesArray[5] = {0, 23, 1, 9, 50}; // Ausgangsbasis
byte Zielarray[5] = {0, 0, 0, 0, 0}; // Zielarray
void setup()
{
Serial.begin(9600);
ordnungs_Funktion();
delay(1000);
for(int i = 0; i < 5; i++)
{
Serial.print(Zielarray[i]);
Serial.print(" ");
}
}
void loop()
{
}
void ordnungs_Funktion()
{
memcpy(Zielarray, tollesArray, sizeof(Zielarray)); // supertolles Array ins Zielarray kopieren
for (int k = 1; k < sizeof(Zielarray); k++)
{
for (int i = 0; i < sizeof(Zielarray) -1 - k; i++)
{
if (Zielarray[i] > Zielarray[i +1])
{
int temp = Zielarray[i];
Zielarray[i] = Zielarray[i + 1];
Zielarray[i + 1] = temp;
}
}
}
}
Works. Danke an alle!
Mit der zweiten Methode will es jedoch leider noch nicht wirklich funktionieren:
#include
#include
byte tollesArray[5] = {0, 23, 1, 9, 50}; // Ausgangsbasis
byte Zielarray[5] = {0, 0, 0, 0, 0}; // Zielarray
void setup()
{
Serial.begin(9600);
ordnungs_Funktion();
delay(1000);
for(int i = 0; i < 5; i++)
{
Serial.print(Zielarray[i]);
Serial.print(" ");
}
}
void loop()
{
}
void ordnungs_Funktion()
{
memcpy(Zielarray, tollesArray, sizeof(Zielarray)); // supertolles Array ins Zielarray kopieren
int n;
qsort (Zielarray, 5, sizeof(Zielarray), compare);
}
int compare (const void * a, const void * b)
{
return (*(int*)a - *(int*)b );
}
Gruß Chris
Chris72622: Mit der zweiten Methode will es jedoch leider noch nicht wirklich funktionieren:
Zumindest der Aufruf der Funktion ist falsch, weil Du die Größe eines einzelnen zu sortierenden Elements falsch angibst. Wenn Du int-Werte sortieren möchtest, hat ein zu sortierendes Element die Größe "sizeof(int)".
qsort (Zielarray, 5, sizeof(int), compare);
Jetzt hab ichs..
byte tollesArray[5] = {0, 23, 1, 9, 50}; // Ausgangsbasis
byte Zielarray[5] = {0, 0, 0, 0, 0}; // Zielarray
byte values[] = { 40, 10, 100, 90, 20, 25 };
void setup()
{
Serial.begin(9600);
ordnungs_Funktion();
delay(1000);
for (int i = 0; i < 5; i++)
{
Serial.print(Zielarray[i]);
Serial.print(" ");
}
}
void loop()
{
}
void ordnungs_Funktion()
{
memcpy(Zielarray, tollesArray, sizeof(Zielarray)); // supertolles Array ins Zielarray kopieren
qsort (Zielarray, 5, sizeof(byte), compare); // Zielarray ordnen
}
int compare (const void * a, const void * b)
{
return ( *(byte*)a - *(byte*)b );
}
Die zweite Version gefällt mir besser, da kürzer. :P
Gruß Chris
Chris72622: Jetzt hab ichs.. Die zweite Version gefällt mir besser, da kürzer. :P
Die Anzahl Zeilen oder der Flash Speicher ?
Und was ist mit der Geschwindigkeit? Das würde mich jetzt mal interessieren ;) 10tausend mal wiederholt sollte sich eine aussagekräftige Zahl ergeben, die nicht massgeblich vom Aufruf der Funktion millis() vorher und nachher und von der Schleife selbst herrührt ... -- Das kannst du natürlich auch messen, wie lange 10000 mal eine Funktion dauert, die die Daten nur von einem Array ins andere umkopiert --
Dann prüf es doch nach. :cold_sweat:
Ich bin mit dem Rest des Codes leider noch nicht ganz soweit und werde es auch nur dann testen, wenn es zu Problemen kommen sollte.
Übrigens produziert die erste Variante bei gleichen Indexinhalten Fehler. Ja, ich weiss- das war auch nicht gefordert.
Gruß Chris
Edit: Argh! War noch ein Fehler drin. Jetzt passt's auch mit der ersten Version:
byte tollesArray[5] = {0, 23, 9, 9, 0}; // Ausgangsbasis
byte Zielarray[5] = {0, 0, 0, 0, 0}; // Zielarray
void setup()
{
Serial.begin(9600);
ordnungs_Funktion();
delay(1000);
for(int i = 0; i < 5; i++)
{
Serial.print(Zielarray[i]);
Serial.print(" ");
}
}
void loop()
{
}
void ordnungs_Funktion()
{
memcpy(Zielarray, tollesArray, sizeof(Zielarray)); // supertolles Array ins Zielarray kopieren
for (int k = 1; k < sizeof(Zielarray); k++)
{
for (int i = 0; i < sizeof(Zielarray) - k; i++)
{
if (Zielarray[i] > Zielarray[i +1])
{
int temp = Zielarray[i];
Zielarray[i] = Zielarray[i + 1];
Zielarray[i + 1] = temp;
}
}
}
}