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
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
danke für die schnelle antwort werd mich mal im google nach diesem Algorithmus mal umsehen gruss dmad
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.
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)
Denktipp: Die letztgrößte zahl kann man sich ja auch abspeichern und darüberliegende dann ignonieren.
Christof, daß funktioniert aber nur bei paarweise verschiedenen Eingabezahlen.
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.
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?
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
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.
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
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.
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
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).
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
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
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. ;)
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
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 ;)
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
AFAIK wurde hier aber etwas programmiert, und keine Schulung in Algorithmen und Datenstrukturen geplant :-> SCNR, Felix
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.