mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik einen Array ordnen


Autor: dmad (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Leute,
bin so ziemlich ein newbie in sachen C Programmierung versuche seit
heute Morgen eine simple Aufgabe zu lösen, doch leider ohne erfolg. Die
Aufgabenstellung ist folgendes es ist ein array gegeben mit
unterschiedlichen zahlen, die länge des arrays ist dabei wurcht. Jetzt
soll diese Array in ein anderes array geschrieben werden undzwar die
grösste Zahl kommt an die erste stelle und soweiter, hier ein Beispiel:
Array1 = {23, 4, 6,3,9,10};
          daraus folgt für Array2 = {23,10,9,6,4,3}
mein problem ist ich Suche im ersten array immer die grösste Zahl und
Setze diese in das 2 Array, damit das funktioniert muss immer die
grösste Zahl im Array1 gelöscht werden damit nicht immer die gleiche
Zahl gesetzt wird und auch die länge des Arrays muss gekürzt werden,
die Frage ist wie geht das? kann mir da einer weiter Helfen. Danke
schon mal im voraus für alle Antworten.

gruss

dmad

Autor: Steffen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schau mal nach dem Bubblesort Algoritmus. Funktioniert grundsätzlich
so:

Du schaust immer zwei nacheinanderstehende Teile des Arrays an. Ist das
hintere größer als das vordere vertauscht du die beiden. Anschließend
kommt das nächste Paar. Dann gehst du die Array Liste solange von vorne
bis hinten durch, bis ein durchlauf erfolgt, in dem du keine Paare mehr
vertauscht hast. Dann ist deine Liste fertig sortiert.

Bei google findest du bestimmt genug infos dazu.

Viele Grüße
Steffen

Autor: dmad (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
danke für die schnelle antwort werd mich mal im google nach diesem
Algorithmus mal umsehen

gruss
dmad

Autor: Sebastian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn es eh nur darum geht, einen Algorithmus abzuschreiben, ohne ihn zu
verstehen, dann würd ich direkt den Quicksort nehmen. Ist von der
Ordnung n*ld(n), IIRC, und somit dem Bubblesort bei großen Arrays weit
überlegen.

Autor: ...HanneS... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Richtig...

Beide sortieren aber im selben Array, er soll es aber einfacher machen,
er soll von einem Array in ein zweites Array sortieren, also immer die
größte Zahl eines jeden Durchlaufs in das Zweitarray übernehmen (wenn
ich die Aufgabe richtig verstanden habe).

Vielleicht hat die Aufgabe ja didaktische Gründen, so als Beispiel, wie
man es nicht macht, um einen "Aha-Effekt" zu haben, wenn man danach
die richtigen Sortieralgotithmen behandelt. Eigentlich genial, man kann
als Lehrer schnell die "Denker" von den "Abschreiber"n isolieren...

...HanneS...
(der kein C kann, auch nicht auf dem PC)

Autor: Christof Krüger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Denktipp: Die letztgrößte zahl kann man sich ja auch abspeichern und
darüberliegende dann ignonieren.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christof, daß funktioniert aber nur bei paarweise verschiedenen
Eingabezahlen.

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kann mir mal jemand O für "immer das kleinste aus einem Array in das
andere" vorrechnen? Ich käme da auf (n^2)/2. Kann das jemand
bestätigen? Dann wäre ja ein n*ld(n) immer noch besser, was mir vom
Gefühl her irgendwie nicht ganz schmeckt, so scheint es doch einfacher
mit zwei Arrays zu sortieren, als in einem in-place zu operieren.

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mir kommt gerade noch, daß (n^2)/2 zu optimistisch ist, ich glaube es
läuft auf n^2 raus. Bei einem Array  (hier das Quellarray) kann man ja
keine Elemente rauslöschen, wie es bei einer Liste ginge. Ich muß also
entweder alle aufrücken (teuer) oder in jedem Durchgang bei
Größenvergleich auch auf Leer testen, und habe damit im günstigsten
Fall n^2/2 Vergleiche, im ungünstigsten Fall n^2. Dann ist das ja mega
schlecht mit Quicksort verglichen... oder würde mich bitte mal jemand
vom Schlauch begleiten?

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du hast schon Recht. QuickSort ist asympthotisch sehr sehr schnell. Er
besitzt im Idealfalle also die bestmögliche Komplexität von allen
Sortierungen. Nur, sollte die Liste schon sortiert sein so tritt der
Worstcase für QuickSort ein, sein Big O sinkt dann auf O(n^2), also
genauso schlecht wie die ganz einfachen Algorithmen.

Ein weiteres Kriterium das niemals in den Komplexitätsanalysen
auftaucht ist der zeitliche Overhead durch die
Programmiermöglichkeiten. QuickSort ist typischerweise rekursiv und
sollte Zb. ein CALL oder Stackoperationen auf dem Zielsystem quälend
langsam sein so wird ein solcher QuickSort ineffizient.
Kurz geasagt, ein Insertion/Selection Sort mit wenigen Daten auf MCUs
wie dem AVR kann unter Umständen QuickSort immer outperformen.

Gruß Hagen

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, als alter C-Programmierer nimmt man Funktionsaufrufe meistens als
billig hin, weil man die meiste Zeit sowieso mit ganz anderen Dingen
verbrät. Bei C++ ist es ja noch schlimmer, da sieht das Einfügen in
eine Liste so einfach aus, aber intern wird die ganze
Speicherallokierung die Performance so bös' runterbremsen... naja,
reden wir nicht drüber ;-)

Was mich eigentlich eher verwundert hatte, war die Unterlegenheit trotz
des augenscheinlich viel einfacher machenden Umstands zwei Arrays zu
haben. Ich hätte gewettet, daß das einer in-place-Ersetzung überlegen
ist, aber ein in-place Selection Sort (den ich übrigens für mich bei
diesem Problem gewählt hätte) macht das ja für die meisten Fälle von n
sicher sehr zufriedenstellend.

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man kann jeden der Inplaced Algorithmen so umschreiben das er mit zwei
Arrays arbeitet, sozusagen die Daten kopiert. Man kann aber fast
garnicht einen Algo.der zwei Arrays benötigt zu umbauen das er inplaced
arbeitet. Dies und der Speicherverbrauchs-Vorteil von inplaced Algos.
könnte eine logische Erklärung dafür sein das man sich von vornhinein
auf die Entwicklung von inplaced Algos. konzentriert hat.
Aber es stimmt schon, die meisten Algos. die man findet arbeiten
inplaced.

Gruß Hagen

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Aber die Algorithmen werden ja schlechter beim Umbau.

Bei Inplace hast Du nie das Problem, daß "Löcher" in Deinem Array
entstehen. Wenn Du in ein anderes aussortierst, hast Du zwangsläufig
(wenn es nicht in genau richtiger oder genau umgekehrter Reihenfolge
vorlag) Lücken, die Du gesondert erkennen mußt, und da geht nicht wenig
Zeit dran verloren. Bei anderen Datenstrukturen sieht es anders aus,
aber gerade bei statischen Arrays ist das IMHO ein nicht zu
unterschätzendes Problem.

Ansonsten natürlich danke für die logische Erklärung mit dem Umbau,
daran hatte ich im ersten Anlauf nicht gedacht.

Autor: Ingo Henze (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wieso hab ich im Ausgangsarray Lücken? Die Elemente im Ausgangsarray
fasse ich gar nicht an. Ich gehe die von Anfang bis Ende durch und
mache für jedes Element dann in das zweite Array ein Einsortieren.
Naja, zumindest würde ich das so machen :-)

Gruß
Ingo

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann sind die "Lücken" eben die bereits einsortierten. Du mußt jedes
Ding das Du anfasst anschauen, ob es ein Einzusortierendes ist, oder
eine "Lücke". Das heißt für ein Array aus n Elementen hast Du n
Vergleiche. Bei einer Liste, die durch das Kürzen schrumpft, sind es
beim Ersten Durchgang n, beim zweiten n-1, n-2 ... bis am Ende nur noch
ein Element drin ist. Das Merken welche noch nicht behandelt wurden
entfällt. So mußt Du mindestens den Wert des zuletzt verlegten
Elementes mitschleppen und immer vergleichen (was, wie schon erwähnnt,
auch nur klappt wenn sie alle paarweise disjunkt sind, also eine
spezielle Lösung darstellt).

Autor: Ingo Henze (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmmm, vielleicht erkläre cih meine Idee noch mal anders, in Worten :-)-


Ich beginne beim Element 0 in Array1. Das kann ich unbesehen an
Position 0 ins Array2 tun.
Dann nehme ich das Element 1 aus Array1 und gucke nach, wo es im Array
2 der gewünschten Ordnung entsprechend hin muß. Dort tu ich es hin, ja
nach Situation kann ich es einfach hinten anfügen (idealer Fall), oder
ich muß alle hinter ihm liegenden Elemente in Array2 um eine Position
nach hinten verschieben, damit der Platz an der richtigen Stelle frei
wird und ich es dort einsortieren kann.
Dann nehme ich Element 2 in Array1 und verfahre genau so.
usw...

Ich gehe also alle Elemente in Array1 von 0 bis n-1 genau einaml durch,
und sortiere es an die passende Stelle im Array2 ein.
Das heiß, mein einzusortierendes Element aus Array1 ist immer das
aktuelle, ich muß mir da nichts zusätzlich merken.
Mit jedem Schritt wächst mein sortiertes Array2 um ein Element.
Nun kann man sicher auch hier das Suchen der passenden Stelle und das
Einsortieren in Array2 optimieren.

Gruß
Ingo

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ist aber dann u.U. n-1 mal um 1..n Stellen verschieben, und
Verschieben ist mit tmp = a, a = b, b = tmp aufwändiger als Vergleichen
mit anschliessendem Branch, oder? Das wäre dann Insertion Sort auf zwei
Arrays. Möglicherweise fährst Du mit Selection Sort besser. Da hast Du
dann im ungünstigsten Fall n^2 Vergleiche, aber bist dann fertig.

Für n << 100 ist es sicher eh wurst, aber ich finde Auswählen und
Anhängen schöner als sie der Reihe nach zu nehmen und einzusortieren.
Mag an meiner Abneigung gegen Verschieben in Arrays liegen g

Autor: Chaldäer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Nach ein paar Versuchen mit der Performance benutze ich ein
Kombiniertes Verfahren aus QuickSort und InsertionSort. Den Bruch mache
ich bei 10 Elementen. Soll heißen, wenn ein Teil-Array bei Quicksort
weniger als 10 Elemente hat gehe ich auf InsertionSort.

Bei 6 Elementen ist (getestet) ein direktes IfThenElse schneller aber
Codetechnisch nicht mehr handhabbar.

Getestet habe ich das Ganze mit LotusScript mit Function calls.
Ob sich das auf andere Sprachen übertragen lässt, weiss ich jetzt
nicht.

Gruß,
Chaldäer

PS: Hmm, so recht überlegt trägt dieser Beitrag (bis auf ein paar
Fachbegriffe) nicht sehr zur Lösung des ursprünglichen Problems bei. ;)

Autor: Ingo Henze (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was mir dabei noch nicht ganz klar ist, wie Du denn nun merken willst,
welche Werte bereits einsortiert sind, und welche nicht.

Wenn Du den bereits einsortierten Wert aus Array1 löschen willst, mußt
Du ja auch Daten umschaufeln.

Wenn Du ihn markieren willst, muß der Wertebereich mindestens eine Wert
haben, der in den Daten nicht vorkommt.

Wenn Du Dir den zuletzt einsortierten Wert merken willst, um dann nur
noch nächstgrößere/-kleinere zu berücksichtigen, darf ein Wert nicht
mehrfach vorkommen. Oder Du muß dann noch mitzählen, wie öft ein Wert
auftritt und wie oft er bereits in Array2 eingetragen ist.

Naja, letztendlich find ich das Einsortieren immer angenehmer, weil
es für mich anschaulicher ist, es entspricht ja z.B. der Vorgehensweise
beim Aufnehmen von Spielkarten beim Kartenspielen (zumindest mache ich
das so :-).

Ist aber, wie so oft, immer auch Geschmackssache.

Gruß
Ingo

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eben, es ist Geschmackssache. Aber wenn ich mich nach was richte, dann
eher nicht nach dem, das anschaulicher ist, sondern dem, das den
Controller weniger Zeit kostet ;)

Autor: Ingo Henze (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, das kommt nun wieder auf den Anwendungsfall an.
Anschaulichkeit könnte durchaus wichiger sein, als etwas weniger Zeit
bei der Abarbeitung zu benötigen, nämlich dann, wenn ich jemandem das
Prinzip der Sortierung vermitteln will.
Und Karten gespielt hat wohl jeder schon irgendwann mal... :-)

Gruß
Ingo

Autor: Zotteljedi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
AFAIK wurde hier aber etwas programmiert, und keine Schulung in
Algorithmen und Datenstrukturen geplant :->

SCNR,
Felix

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man nur 8 Bit Int-Werte sortieren will und man noch relativ viel
RAM frei hat und den für seine Sortierfunktion spendieren will, kann
man sich übrigens auch den Luxus eines Counting Sort gönnen, der einem
seinen Kram dann in O(n) sortiert.
In der Tat ist es aber so, daß man auf einer MCU meistens aber eh sehr
begrenzten Speicher hat und damit die Anzahl der Eingabezahlen ziemlich
begrenzt ist. Was IMHO die Diskussion über Sortieralgos hinfällig macht.
Ob ich jetzt mit Insertion-Sort in n^2 sortiere oder mit Quicksort in
nlogn fällt bei den wenigen Eingabezahlen letztendlich nicht ins
Gewicht.
Übrigens las ich oben von schlechten Eingaben für Quicksort: Stimmt,
aber das kann man durch die Variante "randomized Quicksort" umgehen.
Lohnt aber wie gesagt nur für viele Eingabezahlen, nicht wenn man 5
Zahlen sortieren will ;-).
Mein Liebling ist übrigens Merge-Sort, da einfach zu implementieren bei
ziemlich guter Laufzeit.

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.