Moin Leude,
Ich muss gerade was für die Informatikklausur an der Uni programmieren
und wollte einen Sortieralgorithmus programmieren. Leider weiß ich nicht
welchen Typ dieser hier entspricht. Ist das ein selection sort
algorithmus?
#include <stdio.h>
int main()
{
int hilf1,hilf2,i,k;
int array[10]={4,7,2,8,6,3,5,9,0,1};
for(k=0;k<10;k++){
for(i=0;i<10;i++){
if(array[k]<array[i]){
hilf1=array[k];
hilf2=array[i];
array[k]=hilf2;
array[i]=hilf1;
}} }
int j;
for(j=0;j<10;j++){
printf("%i", array[j]);
}
return 0;
}
Vielen dank im vorraus!
Joachim M. schrieb: > und wollte einen Sortieralgorithmus programmieren. So ohne irgendwelche Anforderungen? Sehr seltsam. Joachim M. schrieb: > Ist das ein selection sort algorithmus? Kannst du das nicht er-wikipedia-en, ob dein Code auf die Beschreibung da passt?
Ich bin der Meinung es handelt sich um eine Art Bubblesort aber ich bin mir ja gerade nicht sicher trotz wikipedia.
Bubblesort braucht immer 2 Schleifen die ineinander verschachtelt sind und eine Puffer_variable für jedes Feld. Bubblesort heißt deshalb so weil der Wert solange nach vorne gesetzt wird, wie er kleiner ist, als der Wert der vor ihm ist. Er steigt also auf wie eine Bubble (Blase). Ergo ist dein Code ein Bubble-sort (wenn er funktioniert). Bubblesort ist übrigens der sicherste Sortiercode aber auch der langsamste.
Schlaumaier schrieb: > Bubblesort heißt deshalb so weil der Wert solange nach vorne gesetzt > wird, wie er kleiner ist, als der Wert der vor ihm ist. GRÖSSER natürlich. Man ich sollte pennen gehen. 16 Std. am Stück am PC sind zu viel.
Schlaumaier schrieb: > Bubblesort ist übrigens der sicherste Sortiercode aber auch der > langsamste. Wie genau definierst du sicher?
Joachim M. schrieb: > Ist das ein selection sort > algorithmus? Definitiv nicht. Dieser wuerde in jedem Schritt das kleinste Element aus den verbleibenden suchen, und dieses dann mit einer Vertauschung an den Anfang bringen, und dann auf den verbleibenden weiter machen. Dies ist eher Bubble Sort ohne fruehzeitigen Abbruch wenn bereits alles sortiert ist. ZigZeg
Vielen Dank an beide. War bisschen verunsichert, welcher das genau ist. Und ja er funktioniert. Das war ja das erste was mich überrascht hat. :D
Wie kann man einen geeigneten Abbruch den einfügen in dem Fall jetzt?
Joachim M. schrieb: > Wie kann man einen geeigneten Abbruch den einfügen in dem Fall jetzt? Wenn nichts getauscht wurde - also der if-Zweig nicht ausgeführt wird.
#include <stdio.h>
int main()
{
int hilf1,hilf2,i,k;
int array[10]={14,17,12,18,6,13,5,19,0,1};
for(k=0;k<10;k++){
for(i=0;i<10;i++){
if(array[k]>array[i]){
hilf1=array[k];
hilf2=array[i];
array[k]=hilf2;
array[i]=hilf1;
}
break;
}}
int j;
for(j=0;j<10;j++){
printf("%i ", array[j]);
}
return 0;
}
So hatte ich das jetzt verstanden. Das funktioniert aber nicht.
Muss das nicht heißen?
for(k=0;k<9;k++){
for(i=k+1;i<10;i++){...
usw.
Was genau würde das denn deiner Meinung nach bringen? ALso ich binabsoluter anfänger:D
Schlaumaier schrieb: > Bubblesort ist übrigens der sicherste Sortiercode aber auch der > langsamste. Korrekt. Wir wir alle wissen sind schnellere Algorithmen generell unsicher.. Slow seems save!
Irgendetwas zusammenbauen und nachher gucken, was es geworden ist. Das kenne ich sonst nur vom Kochen und Backen.
Joachim M. schrieb: > Wie kann man einen geeigneten Abbruch den einfügen in dem Fall jetzt? Warum willst du irgendwas abbrechen? Die unnötigen Vergleiche kannst du noch rausschmeißen: Nach n Durchläufen der äußeren Schleife sind die ersten n Elemente bereits an der korrekten Position. Wie man die innere Schleife verbiegen muss, damit das nicht immer wieder von vorne überprüft wird, findest du selbst raus. Es steht ansonsten auch in jeder Implementierung. Außerdem ist der Tausch mit zwei Hilfsvariablen unnötig, eine tut's auch. Eigentlich ergibt sich das alles, wenn du eine beliebige Bubblesort-Implementierung anschaust. Schlaumaier schrieb: > Bubblesort ist übrigens der sicherste Sortiercode aber auch der > langsamste. Wuff. Normalen Menschen würde das Gehirn explodieren, wenn sie so einen Unfug schreiben würden, aber bei dir scheint da keine Gefahr zu bestehen.
Deswegen werde ich wahrscheinlich auch kein Informatiker... Das mit der Abbruchbedingung hab ich aber immer noch richtig verstanden wie man die hier einbringen kann.
Joachim M. schrieb: > So hatte ich das jetzt verstanden. Das funktioniert aber nicht. Wenn der if-Zweig in der inneren Schleife nicht mehr ausgeführt wird. Einmal reicht nicht. Du musst dir merken, ob er ausgeführt wurde - ja, da brauchst du eine zusätzliche Variable.
#include <stdio.h>
int main()
{
int hilf1,hilf2,i,k;
int
array[20]={14,17,12,18,6,13,5,19,0,1,56,77,88,99,22,34,56,76,11,119};
for(k=0;k<20;k++){
for(i=k;i<20;i++){
if(array[k]>array[i]){
hilf1=array[k];
array[k]=array[i];
array[i]=hilf1;
}
}
}
int j;
for(j=0;j<20;j++){
printf("%i ", array[j]);
}
return 0;
}
Habe ich das so ganz gut umgesetzt oder gibt es da noch immer Punkte die
den Code sehr ineffizient machen?
Danke für die Hilfe!
Joachim M. schrieb: > Das mit der Abbruchbedingung hab ich aber immer noch richtig verstanden > wie man die hier einbringen kann. Lies den Wikipedia-Artikel. Für das Ergebnis ist das hier aber irrelevant und der asymptotische Aufwand ändert sich auch nicht, nur die Best-Case-Laufzeit. Bei Fragen der Art "Wie funktioniert Algorithmus X und wie implementiert man das?" ist der Cormen im Studium dein Freund, vielleicht auch noch darüber hinaus.
In meiner Jugend gab es noch Bücher. Das Standardwerk dazu war "Algorithmen und Datenstrukturen" von einem gewissen Niklaus Wirth. (Der hat dann auch noch die Sprachen Pascal und Modula (und weitere) entwickelt.) In dem Buch sind auf 50 Seiten (77-145) die verschiedenen Sortieralgorithmen gegenüber gestellt. Vielleicht findet sich ja noch ein Exemplar in einer Uni-Bibliothek, oder einem Antiquariat. Mir hat es damals sehr geholfen.
Zeig mir doch mal einer einen Bubble-sort wo so mit den beiden
Schleifenindices getauscht wird:
for(k=0;k<10;k++){
for(i=0;i<10;i++){
if(array[k]<array[i]){
hilf1=array[k];
hilf2=array[i];
array[k]=hilf2;
array[i]=hilf1;
Das ist nie und nimmer ein Bubble Sort. Ob dieses Konstrukt wirklich
funktioniert oder nur zufällig bei den gewählten Zahlen habe ich mir
nicht mehr genauer angeschaut.
Nimm eine gequirlte Zahlenmenge, stelle sie graphisch in excel dar, sortiere, das Ergebnis wieder graphisch darstellen. Ist das so schwierig? Dann kannst die deine Sortierverfahren nach Qualität bewerten.
Joachim M. schrieb: > Was genau würde das denn deiner Meinung nach bringen? > ALso ich binabsoluter anfänger:D Er spart Vergleiche auf 0<0 bzw 10<10 damit ein.
mh schrieb: > Wie genau definierst du sicher? Einfach und schnell zu schreiben. Geht mit wenigen Zeilen Code. Sicher = Weniger Code = Weniger potenzielle Fehlerquellen. Ich kann ihn (als einzigen) schon seit 20 Jahren auswendig. Ich hatte mal einen anderen probiert der war ca. 40% schneller aber hat mich 2 Tage gekostet ihn anzupassen. Und was auch das Sicher macht. Schonmal mit array-Sort bei VB gearbeitet. Das ist so schrottig das es sogar die Hilfe zugibt. Bei den Bubblesort muss man nur darauf achten das bei Texten die selbe Codepage + die selbe Buchstabengröße benutzt wird. Deshalb empfehle ich immer ein Vergleich mit LCASE - Funktion(alles in Kleinbuchstaben), wenn nix anders explizit gefordert wird. Fast alle Programmiersprachen sehe da nämlich ein Unterschied weil die Sortierreihenfolge nach der geltenden ASCII-Tabelle (Locations-Einstellungen) durchgeführt wird. Ist aber nur wichtig wenn man kein AMI ist. ;) ÄÖÜ sind nämlich öfters mal woanders, in der Tabelle. Joachim M. schrieb: > Wie kann man einen geeigneten Abbruch den einfügen in dem Fall jetzt? Mit einen EXIT-FOR oder in den man (unelegant aber geht) den Schleifenwert über die den Max-wert der Schleife stellt.
Also ich habe keine Ahnung vom Programmieren @Udo aber das sortieren funktionier für verschiedene Zahlen und auch Anzahlen an Zahlen habe ich variiert. Dafür dass mir gesagt wurde dass es ja so leicht mit dem Wikipediaartikel wäre passen die Meinungen hier aber nicht ganz. Aber @Udo du kannst den Code gerne ausprobieren und mir dann sagen welchen Sortiertyp das entspricht. Das war ja meine ursprüngliche frage.
for(k=0;k<20;k++){
for(i=k;i<20;i++){
Vergleicht als erstes [0] mit [0] ist nicht übermäßig sinnvoll.
Beim zweiten Durchlauf von k ist der erste Vergleich [1] ? [1]
Bei den folgenden Durchläufen sieht es gleich aus.
Der letzte Durchlauf vergleicht [19] mit [19] ist auch nicht der
Bringer.
Deshalb mein Vorschlag:
for(k=0;k<19;k++){
for(i=k+1;i<20;i++){
siehe auch mein Tip von 16:43
muss aber nicht sein;-)
Joachim M. schrieb: > Leider weiß ich nicht welchen Typ dieser hier entspricht. schau mal hier, da kannst du nachsehen ob deiner mit dabei ist. https://www.youtube.com/results?search_query=sortieralgorithmen+tanz
:
Bearbeitet durch User
Schlaumaier schrieb: > Bubblesort heißt deshalb so weil der Wert solange nach vorne gesetzt > wird, wie er kleiner ist, als der Wert der vor ihm ist. Er steigt also > auf wie eine Bubble (Blase). Auf alten Maschinen mit ihren bescheidenen Taktfrequenzen konnte man das sogar schön sehen, wenn man Textzeilen auf dem Bildschirm sortiert hat. Vielleicht geht das auch heute noch, wenn man mal einen Bubblesort für den Makro-Interpreter der Textverarbeitung schreibt. Schlaumaier schrieb: > Bubblesort ist übrigens der sicherste Sortiercode aber auch der > langsamste. Langsam ist er, aber "sicher" ist das falsche Attribut. Das Gegenteil wäre "unsicher", und das kann eigentlich nur wegen eines Progammierfehlers oder Hardwaredefekts passieren. Der Bubbelsort ist aber ein stabiler Sortieralgorithmus, was bedeutet, dass zwei gleiche Elemente in ihrer ursprünglichen Reihenfolge stehen bleiben. Es gibt auch (schnellere) Sortierverfahren, bei denen nicht garantiert ist, dass die Reihenfolge gleicher Elemente nicht verändert wird. Auf den ersten Blick scheint es gleichgültig zu sein, ob die ursprüngliche Ordnung gleicher Elemente erhalten bleibt, aber das ist nicht so: Angenommen man möchte folgendes numerisch sortiertes Telefonverzeichnis nach Namen und Vornamen sortieren:
1 | Zeile, Name, Vorname, Nebenstelle |
2 | 1, Hoffmann, Harald, 114 |
3 | 2, Heimermann, Dirk, 161 |
4 | 3, Faßbender, Eva, 176 |
5 | 4, Felderhoff, Stefanie, 314 |
6 | 5, Faller, Carolin, 336 |
7 | 6, Hoffmann, Marlies, 409 |
8 | 7, Heinen, Roswitha, 445 |
9 | 8, Falkenburg, Eva, 449 |
10 | 9, Hoffmann, Kerstin, 485 |
11 | 10, Heimann, Sascha, 629 |
Dazu wird man zunächst die Vornamen sortieren, wobei es gleichgültig ist, in welcher Reihenfolge die Nachnamen kommen. Man kann dafür also das schnellste verfügbare Sortierverfahren verwenden. Bei sehr grossen Datenbeständen kann das einen erheblichen Zeitunterschied bedeuten. Es gibt sogar Verfahren, die erst einmal den ganzen Datenbestand dahingehend überprüfen, ob er bereits in irgend einer Weise vorsortiert ist, und danach entscheiden, welche Sortieralgorithmen verwendet werden. Mit einem Algorithmus, der die Quelle Zeile für Zeile von vorn liest, und den Datensatz in die Zielliste einfügt, !sobald das möglich ist!, erhalten wir nach und nach folgende Kette :
1 | Harald |
2 | Dirk-Harald |
3 | Dirk-Eva(3)-Harald |
4 | Dirk-Eva(3)-Harald-Stefanie |
5 | Carolin-Dirk-Eva(3)-Harald-Stefanie |
6 | Carolin-Dirk-Eva(3)-Harald-Marlies-Stefanie |
7 | Carolin-Dirk-Eva(3)-Harald-Marlies-Stefanie-Roswitha |
8 | Carolin-Dirk-Eva(8)-Eva(3)-Harald-Marlies-Stefanie-Roswitha |
9 | Carolin-Dirk-Eva(8)-Eva(3)-Harald-Kerstin-Marlies-Stefanie-Roswitha |
10 | Carolin-Dirk-Eva(8)-Eva(3)-Harald-Kerstin-Marlies-Sascha-Stefanie-Roswitha |
Die nach Vornamen sortierte Liste lautet nun also:
1 | 5, Faller, Carolin, 336 |
2 | 2, Heimermann, Dirk, 161 |
3 | 8, Falkenburg, Eva, 449 |
4 | 3, Faßbender, Eva, 176 |
5 | 1, Hoffmann, Harald, 114 |
6 | 9, Hoffmann, Kerstin, 485 |
7 | 6, Hoffmann, Marlies, 409 |
8 | 10, Heimann, Sascha, 629 |
9 | 4, Felderhoff, Stefanie, 314 |
10 | 7, Heinen, Roswitha, 445 |
Beachte, dass die beiden Evas jetzt die Plätze getauscht haben, diese Sortierung ist also nicht stabil! Das ist hier aber unerheblich, da die im nächsten Schritt erfolgende Sortierung nach Familiennamen Vorrang hat. Ab hier muss ein stabiles Sortierverfahren verwendet werden, da sonst die (hier zufällig bereits richtig) vorsortierten Hoffmänner durcheinander geraten könnten. Nach dem obigen instabilen Sortierverfahren wäre deren Reihenfolge nämlich 6-9-1, was offensichtlich zur falschen Reihenfolge der Vornamen führt. Vor 50 Jahren, als Speicherplatz noch knapp und teuer war, selbst Grossrechner hatten oft nur 512 Kilo(!)Byte RAM, und Magnetbänder das (langsame) Speichermedium für grosse Datenmengen waren, hat man viel Gehirnschmalz auf effiziente Sortierverfahren verwendet. https://de.wikipedia.org/wiki/Sortierverfahren https://en.wikipedia.org/wiki/IBM_System/370_Model_145 Es ist kein Fehler, sich an die damals erworbenen Kenntnisse zu erinnern.
Schlaumaier schrieb: > Ich hatte mal einen anderen probiert der war ca. 40% schneller aber hat > mich 2 Tage gekostet ihn anzupassen. Vorsicht! Beim Boublesort steigt die Laufzeit quadratisch mit der Anzahl der Elemente an. Kann gut sein, das es bei Deinem Testfall nur 40% Unterschied waren. Wie sieht es aber aus, wenn Du mal die Anzahl der zu sortierenden Elemente mit Faktor 100 multiplizierst? Dann steht Deine Kiste schnell mal für eine Sekunde oder länger. Wie sieht es bei Faktor 1000 oder 10000 aus? Diese Algorithmen mit O(n²) Komplexität sind gefährlich, weil man beim Test häufig nicht merkt wie drastisch langsam sie bei größeren Datenmengen werden können. Wenn Du weist, das Du wirklich nur eine Hand voll Werte sortieren willst, dann sind solche billig Algorithmen tatsächlich häufig eine gute Wahl. Wenn Du Dir aber nicht sicher bist, dann hat Dein Code eine tickende Zeitbombe. Die Zeit, die Du am Anfang in der Implementation sparst, sind nichts gegen den Stress, den Du mit dem Kunden hast sobald dein Code nicht mehr performt. Und für die Embedded Neulinge: Auch Vorsicht mit Quicksort. Der Stackbedarf kann mit der Anzahl der Elemente steigen. Passiert in der Praxis selten, aber ich hatte schon Tester, die mit Quicksort Killer Sequenzen angekommen sind und mir der Stack um die Ohren geflogen ist. Seitdem setze ich eigentlich nur noch Heapsort ein. Das habe ich vor 25 Jahren ein mal vom Buch abgeschrieben (eine Stunde, keine zwei Tage) und seitdem immer mal wieder in angepasster Form verwendet.
Nils schrieb: > ? Dann steht Deine > Kiste schnell mal für eine Sekunde oder länger. Wie sieht es bei Faktor > 1000 oder 10000 aus? Keine Ahnung ab ca. 3-5000 Elementen aufwärts halte ich die sowieso nicht mehr im Speicher. Dann lagere ich die in einen Datenbank aus, und lasse sie mit "Order by was_ich_will" sortieren. Der Grund ist. Habe ich so viele Elemente dann werden das zu 99% eh mehr. Also gleich vernünftig auslagern, anstatt sein Speicher mit z.b. DIM a(1000000) voll zu müllen. Bubblesort reicht völlig aus, um kleinere Mengen an Daten zu sortieren, wobei ich die meist nur für einen schönere Ansicht der Daten brauche. User mögen es wenn sie die Daten sortiert angezeigt bekommen. Und da kommt es sehr selten zu mehr als 100 Elementen. Womit ich sogar zugebe das ich noch nie mehr als ca. 500 Elemente "per programmierter Sortierroutine" bearbeitet habe. Das Beispiel wo ich man 2 Tage dran gesessen habe war ein Job der ca. 12.000 Elemente sortieren sollte und wo ich keine Datenbank verwenden sollte. Der Kunde ist König, aber die Regierung hat selten Ahnung. ;)
Nils schrieb: > Seitdem setze ich eigentlich nur noch Heapsort ein. Eine weitere gute Alternative ist Shellsort mit Ciura-Sequenz, was schneller als Heapsort ist. Dafür hat Heapsort eine konstantere Laufzeit.
Hallo Nils, Nils schrieb: > Schlaumaier schrieb: >> Ich hatte mal einen anderen probiert der war ca. 40% schneller aber hat >> mich 2 Tage gekostet ihn anzupassen. > > Vorsicht! Beim Boublesort steigt die Laufzeit quadratisch mit der Anzahl > der Elemente an. Kann gut sein, das es bei Deinem Testfall nur 40% > Unterschied waren. Wie sieht es aber aus, wenn Du mal die Anzahl der zu > sortierenden Elemente mit Faktor 100 multiplizierst? Dann steht Deine > Kiste schnell mal für eine Sekunde oder länger. Wie sieht es bei Faktor > 1000 oder 10000 aus? > > Diese Algorithmen mit O(n²) Komplexität sind gefährlich, weil man beim > Test häufig nicht merkt wie drastisch langsam sie bei größeren > Datenmengen werden können. Du hast vollkommen Recht, aber der Herr Schlaumeier veröffentlicht hier einen unterirdischen Beitrag nach dem nächsten. Wer von 40% Laufzeitgewinn spricht, der hat von Laufzeitklassen nichts gehört. Auch die Begründung für minderwertige Algorithmen "Sicher = Weniger Code = Weniger potenzielle Fehlerquellen." ist hanebüchen. Wer denn noch von DIM a(1000000) spricht, der benutzt auch REDIM. Das alleine ist schon in O(n^2). Bubble-Sort ist ein netter Sortieralgorithmus, geeignet für einen VHS-Kurs, für mehr nicht. Aber wenn der Erkenntnisprozess nicht da ist, kann man auch mit einer Parkuhr sprechen, das ist auch folgenlos. [... Der Grund ist. Habe ich so viele Elemente dann werden das zu 99% eh mehr. Also gleich vernünftig auslagern, anstatt sein Speicher mit z.b. DIM a(1000000) voll zu müllen. ...] Große Probleme kann er auch nicht sortieren, dass muss dann die Datenbank für ihn tun: [... Keine Ahnung ab ca. 3-5000 Elementen aufwärts halte ich die sowieso nicht mehr im Speicher. Dann lagere ich die in einen Datenbank aus, und lasse sie mit "Order by was_ich_will" sortieren. ...]
Diese erste Version Joachim M. schrieb: > int main() > ... ist im Wesentlichen ein deoptimierter¹ Insertion-Sort, die zweite Version Joachim M. schrieb: > int main() > ... im Wesentlichen ein deoptimierter Selection-Sort. Das erkennt man leicht, wenn man sich in jedem Durchlauf der äußeren Schleife den Zwischenstand des Array-Inhalts anschaut. Korrekt sind beide Algorithmen, im Vergleich zu den jeweiligen Originalen werden aber mehr Vergleiche und Vertauschungen benötigt. Wie Udo bereits schrieb, hat das Ganze mit dem Bubble-Sort nichts zu tun. Beim Bubble-Sort werden immer nur benachbarte Array-Elemente (also array[i] und array[i+1]) verglichen und ggf. vertauscht. Das ist hier definitiv nicht der Fall. ¹) Ich wollte das Wort "verhunzt" vermeiden ;-)
Peter M. schrieb: > Wer denn noch von DIM a(1000000) spricht, der benutzt auch REDIM. > Das alleine ist schon in O(n^2). Bei gewissen Programmiersprachen muss man JEDE Variable mit DIM deklarieren es sei denk man schaltet diese ab. Was aber kein 'Feine Programmierstil' ist. DIM variablen_name as TYP. Ist halt standard. REDIM gibt es glaub ich nicht einmal mehr. Peter M. schrieb: > Große Probleme kann er auch nicht sortieren, dass muss dann die > Datenbank für ihn tun: Kann er schon. Aber ich bevorzuge halt eine einfache und übersichtliche Methode. Und es ist einfacher und schneller eine SQL-Abfrage über eine Funktion laufen zu lasen als ein großes Array mit For-Next durchsuchen zu wollen. Und wenn ich schon ein Array machen muss, dann mache ich das nicht zum vergnügen sondern weil es sein muss. Und bitte verwechsle Daten-Array nicht mit Typen-Array. Solche Typen-Array brauche ich z.b. für eine Perfekte REZIZE-Funktion des Frames. Einfach gesagt sobald du mehr als 640x480 Bildpunkte hast wird das Frame immer perfekt auf den Bildschirm dargestellt. Und das sogar unter Android ohne das ich dazu Klimmzüge machen muss. ;) Ich denke eher deine Programmierkenntnisse sind sehr veraltet oder nur für billige Script-Sprachen.
Joachim M. schrieb: > Ich muss gerade was für die Informatikklausur an der Uni programmieren > und wollte einen Sortieralgorithmus programmieren. Leider weiß ich nicht > welchen Typ dieser hier entspricht. Lässt Du Hausaufgaben vom "Schwarmwissen" erledigen? Du "programmierst" einfach mal so etwas und fragst dann, was Du programmiert hast? Joachim M. schrieb: > vorraus Uni-Niveau?
Zunächst mal: Deine Formatierung (Einrücken) ist subotimal. Verwende bitte zum darstellen die c-Tags. Auch ist es für den Optimierer besser, wenn die Variablen dort definiert werden, wo sie gebraucht werden. Ok, spielt jetzt bei dem Beispiel keine große Rolle. Aber: Es reicht eine Hilfsvariable aus, du brauchst keine 2!
1 | #include <stdio.h> |
2 | |
3 | int main() |
4 | {
|
5 | int array[20]={14,17,12,18,6,13,5,19,119,56,77,88,99,22,34,56,76,11,0,1}; |
6 | |
7 | for(int k=0; k<20; k++) { |
8 | for(int i=0; i<20; i++) { |
9 | if(array[k] < array[i]) { |
10 | int hilf1 = array[k]; |
11 | array[k] = array[i]; |
12 | array[i] = hilf1; |
13 | }
|
14 | }
|
15 | }
|
16 | for(int j=0; j<20; j++) { |
17 | printf("%i ", array[j]); |
18 | }
|
19 | printf("\n"); |
20 | return 0; |
21 | }
|
liefert: 0 1 5 6 11 12 13 14 17 18 19 22 34 56 56 76 77 88 99 119 Die Variante mit for(int i=k+1; i<20; i++) liefert was anderes:
1 | #include <stdio.h> |
2 | |
3 | int main() |
4 | {
|
5 | int array[20]={14,17,12,18,6,13,5,19,119,56,77,88,99,22,34,56,76,11,0,1}; |
6 | |
7 | for(int k=0; k<20; k++) { |
8 | for(int i=k+1; i<20; i++) { |
9 | if(array[k] < array[i]) { |
10 | int hilf1 = array[k]; |
11 | array[k] = array[i]; |
12 | array[i] = hilf1; |
13 | }
|
14 | }
|
15 | }
|
16 | for(int j=0; j<20; j++) { |
17 | printf("%i ", array[j]); |
18 | }
|
19 | printf("\n"); |
20 | return 0; |
21 | }
|
Und zwar: 119 99 88 77 76 56 56 34 22 19 18 17 14 13 12 11 6 5 1 0 Richtig wäre: for(int i=0; i<k; i++) Dies wäre also der klassische Bubblesort:
1 | #include <stdio.h> |
2 | |
3 | int main() |
4 | {
|
5 | int array[20]={14,17,12,18,6,13,5,19,119,56,77,88,99,22,34,56,76,11,0,1}; |
6 | |
7 | for(int k=0; k<20; k++) { |
8 | for(int i=0; i<k; i++) { |
9 | if(array[k] < array[i]) { |
10 | int hilf1 = array[k]; |
11 | array[k] = array[i]; |
12 | array[i] = hilf1; |
13 | }
|
14 | }
|
15 | }
|
16 | for(int j=0; j<20; j++) { |
17 | printf("%i ", array[j]); |
18 | }
|
19 | printf("\n"); |
20 | return 0; |
21 | }
|
Ah ok jetzt habe ich verstanden wie ich das machen soll. Vielen dank auf jeden Fall das war sehr hilfreich. Nein das sind nicht meine Hausaufgaben und ich versuche hier gerade die Tutorenstunden, welche es ja dank Corona nicht gibt, zu ersetzen. Wenn man sich in einem Punkt festgefahren hat oder es einfach noch nicht ganz verstanden hat. Hilft es Leute zu fragen die was davon verstehen. Offensichtlich verstehen das manche hier nicht ganz. Wenn ich einfach ein Code wollte könnte ich googlen. Oder wurde das nicht bedacht? Trotzdem gab es viele Leute die mir sehr geholfen haben das ein bisschen besser zu verstehen.
Joachim M. schrieb: > Wenn man sich in einem Punkt festgefahren hat oder es einfach noch nicht > ganz verstanden hat. Hilft es Leute zu fragen die was davon verstehen. > Offensichtlich verstehen das manche hier nicht ganz. Im nächsten Semester solltest du dich während des Semesters darum kümmern und nicht erst kurz vor der Klausur. Die Pandemie ist hier ne schlechte Ausrede.
Joachim M. schrieb: > Wenn ich einfach ein Code wollte könnte ich googlen. Oder wurde das > nicht bedacht? Woher hast Du denn den Code? Ist er Dir im Schlaf eingefallen und jetzt weißt Du nicht mehr, was Du gemacht hast? Wenn Du Dir den Code selbst ausgedacht hättest wüsstest Du wohl, was Du gemacht hast - oder?
:
Bearbeitet durch User
witzigerweise habe ich mir ein Videos zu Quicksort anguckt und habe das als Anfang gehabt. Und es hat funktioniert und deswegen wollte ich wissen was ich da produziert habe. Eigentlich wars nur ein test. Ja nächstes Semester bombadier ich euch während des Semsters mit fragen dachte ich hätte das verstanden.
Joachim M. schrieb: > Ja nächstes Semester bombadier ich euch während des Semsters mit fragen > dachte ich hätte das verstanden. Wende dich an deinen Prof, der wird dafür bezahlt.
Joachim M. schrieb: > witzigerweise habe ich mir ein Videos zu Quicksort anguckt und habe das > als Anfang gehabt. Und es hat funktioniert und deswegen wollte ich > wissen was ich da produziert habe. Erzähl das mal Deiner Oma :-)
Ich dachte der Code war so schlecht? Was ist also so unwahrscheinlich daran das ein Anfänger das falsche macht...
Joachim M. schrieb: > Ich dachte der Code war so schlecht? Was ist also so unwahrscheinlich > daran das ein Anfänger das falsche macht... Deine Story ist einfach zu schlecht für einen guten Freitags-Troll.
Schlaumaier schrieb: > Und bitte verwechsle Daten-Array nicht mit Typen-Array. Solche > Typen-Array brauche ich z.b. für eine Perfekte REZIZE-Funktion des > Frames. Einfach gesagt sobald du mehr als 640x480 Bildpunkte hast wird > das Frame immer perfekt auf den Bildschirm dargestellt. Bahnhof? Was ist ein "Typen-Array"? Was ist der Unterschied zu einem "Daten-Array"? Und was ist ein "perfektes Resize"? Und warum benötigt man mehr als 640x480 Bildpunkte? Zum Sortieren? > Und das sogar unter Android ohne das ich dazu Klimmzüge machen muss. Bahnhof-Quadrat? Welche Klimmzüge? Für was? > Ich denke eher deine Programmierkenntnisse sind sehr veraltet oder nur > für billige Script-Sprachen. Oh je, mir schwant böses...
Joachim M. schrieb: > Ok wenn du meinst. Ja, meine ich. Jeder Dödel kann den Algorithmus mit Papier und Bleistift nachvollziehen, wenn er das denn will und rudimentäre Kenntnisse der Programmierung hat. Wenn Du das nicht kannst wäre vielleicht eine Anstellung als Facility-Manager o.ä. passender für Dich :-) Oh - jetzt komme ich mir fast wie C-Hater vor ... nein, das bin ich nicht.
:
Bearbeitet durch User
Vlt. Programmierer werde ich sicher nicht. Offensichtlich habe ich noch keine rudimentären Kenntnisse über das Programmieren. Wenn du nicht helfen willst könntest du auch was besseres für die Menschheit machen als mich hier so anzukacken und den Besserwisser raushängen zu lassen. Wenn es so einfach ist hättest du deine Zeit dafür verwenden können mir zu helfen. Mehr als unnötige Kommentare schreiben ist ja offensichtlich nicht drin.
Joachim M. schrieb: > Vlt. Programmierer werde ich sicher nicht. Offensichtlich habe ich noch > keine rudimentären Kenntnisse über das Programmieren. Dann hast Du Informatik als falsches Fach gewählt. Joachim M. schrieb: > und wollte einen Sortieralgorithmus programmieren Das ist offensichtlich nicht gerade Deine Kernkompetenz. Was willst denn mal werden (Facility-Manager mal ausgenommen)? Joachim M. schrieb: > Mehr als unnötige Kommentare schreiben ist ja offensichtlich nicht drin. Doch - aber nicht für Menschen wie Dich :-)
Ingenieur nicht für info... Aber offensichtlich muss ich mir das Programmieren nochmal angucken ;D
:
Bearbeitet durch User
Joachim M. schrieb: > Ingenieur nicht für info... Nun, auch und gerade da muss man logisch denken können - oder? Joachim M. schrieb: > int array[10]={4,7,2,8,6,3,5,9,0,1}; > for(k=0;k<10;k++){ > for(i=0;i<10;i++){ > if(array[k]<array[i]){ > hilf1=array[k]; > hilf2=array[i]; > array[k]=hilf2; > array[i]=hilf1; Was genau passiert denn in "Deinem" Programm? Es werden immer 2 Werte verglichen if(array[k]<array[i]) und vertauscht, wenn der 2. Wert größer wie der 1. Wert ist. Für mich ist das ein popliger Bubble-Sort. Wenn ich falsch liege ist es halt so :-)
Dachte ich ja auch. Aber irgendwie wurden mir immer wieder gesagt es wäre keiner. Aber wie gesagt ich kann nicht behaupten, dass ein Bubblesort mein Ziel gewesen war. Danke auf jeden Fall.
:
Bearbeitet durch User
Hugo H. schrieb: > größer Kleiner - und es wird umgekehrt sortiert :-/ - aber trotzdem Bubblesort.
:
Bearbeitet durch User
Joachim M. schrieb: > Aber irgendwie wurden mir immer wieder gesagt es wäre keiner. Man muss ja auch nicht immer alles glauben, was die Leute so sagen. Besser ist es, selber zu recherchieren. Hier findest du mehrere Bubble-Sorts aus (vermutlich) voneinander unabhängigen Quellen: https://de.wikipedia.org/wiki/Bubblesort https://en.wikipedia.org/wiki/Bubble_sort https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort Vergleiche sie mit deinem Code, und du wirst feststellen, dass die Leute, die behaupten, dein Code sei kein Bubble-Sort, recht haben.
Yalu X. schrieb: > Vergleiche sie mit deinem Code, und du wirst feststellen, dass die > Leute, die behaupten, dein Code sei kein Bubble-Sort, recht haben. Ich vermute, Du meinst mich damit. Welcher genau ist es denn?
Yalu X. schrieb: > Besser ist es, selber zu recherchieren. > > Hier findest du mehrere Bubble-Sorts aus (vermutlich) voneinander > unabhängigen Quellen: > > https://de.wikipedia.org/wiki/Bubblesort > https://en.wikipedia.org/wiki/Bubble_sort > https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort In der Zeit, die er hier vergeudet hat, hätte er sich Algorithmen und Datenstrukturen von Wirth in seiner Uni-Bibliothek ausleihen und das Kapitel über Sortieralgorithmen durcharbeiten können. Ich hab bei drei Unis nachgeschaut, überall waren mehrere vorhanden und ausleihbar, auch als rein digitale Version, für die man das Haus nichtmal verlassen muss.
mh schrieb: > In der Zeit, die er hier vergeudet hat, hätte er sich Algorithmen und > Datenstrukturen von Wirth in seiner Uni-Bibliothek ausleihen und das > Kapitel über Sortieralgorithmen durcharbeiten können. Warum selber arbeiten, wenn einem in Forum die Hausaufgaben gemacht werden? Das ist ja sicherlich nicht das einzige Forum, wo man seine Fragen abstellen kann. Wenn Du das parallel mit 5 Foren machst, in jedem Forum ein anderes Thema bearbeiten lässt, kommst Du schnell voran.
Ich habe ehrlicherweise noch nicht verstanden von was für Hausaufgaben du redest? Hat dir jemand Hausaufgaben gegeben und dann wurden die Kontrolliert? Den Cormen habe ich tatsächlich gefunden und gedownloadet. Wirth hingegen finde ich nicht.
Joachim M. schrieb: > Wirth hingegen finde ich nicht. Nikolaus Wirth: "Algorithmen und Datenstrukturen" gesucht mit: Wirth Algorithmen Datenstrukturen z.B. hier: https://sites.google.com/site/tesdenatant/home/algorithmen-palilwu3qcwotvjq oder der hier: https://www.hs-bremen.de/internet/hsb/struktur/mitarbeiter/schormann/skripte/echte_programmierer.pdf
:
Bearbeitet durch User
>Keine Ahnung ab ca. 3-5000 Elementen aufwärts halte ich die sowieso
nicht mehr im Speicher. Dann lagere ich die in einen Datenbank aus, und
lasse sie mit "Order by was_ich_will" sortieren.
Dann wird das Ganze nie was. Vergiss Informatik, das hat keinen Sinn so.
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.