BubbleSort - Irrt sich mein Lehrer?

[SebiB90]

Hi,

mittlerweile sind wir echt weit in Info, wir machen Sortier Algos *IronieWiederAbstell*.

Jedenfalls haben wir den richtigen BubbleSort gemacht. Da war noch alles ok. So wie er auch in Wikipedia und sonst wo drin steht. Vergleichen der benachbarten Elemente und gegebenenfalls tauschen.

Dann wollte uns der Lehrer eine andere Variante von BubbleSort zeigen. Schon gewundert welche andere Variante, da gibts doch nur eine oder? Jedenfalls was er uns gezeigt hat war dann aber soweit ich weiß ein SelektionSort.
Zurückhalten wie ich bin, hab ich ihn gleich ma angeschnauzt, was er doch für nen Schrott erzählt, dass das BubbleSort sei. Er wollte mir dann erklären, das BubbleSort nur "Sortieren durch Tausch" bedeutet. Wie will man denn Sortieren ohne zu tauschen? Jedenfalls wenn man nicht ein 2. Array hat?

Dann war schon die Stunde schluss. Wollte jetzt von euch wissen, ob ich Recht habe oder vllt doch mein Lehrer und SelectionSort ne andere Variante von BubbleSort ist. Nicht dass ich nächstemal weiter mecker und ich hab dann doch Unrecht^^

Also, wie siehts aus?

 

[tfa]

Bei Bubble-Sort werden immer nur zwei Elemente verglichen, die direkt nebeneinander stehen und dann eventuell vertauscht.
Macht das der Algorithmus von Deinem Lehrer?
Bubble-Sort bedeutet, dass die großen Elemente langsam wie Blasen in der Liste aufsteigen. Selection-Sort ist etwas anders.

 

[tuxedo]

Deine Ausdrucksweise ist doch etwas gewöhnungsbedürftig.

Grundlegend ist:

Wenn ich etwas "sortiere", dann heisst das, dass ich die Plätze der zu sortierenden Elemente ändere (oder zumindest die Elementierte nach der Sortierreihenfolge nummeriere).

Bubble-Sort basiert darauf immer zwei benachbarte Elemente zu vergleichen und dann, je nachdem ob aufsteigend oder absteigend sortiert wird, in eine Richtung zu vertauschen.

Bei Selektion-Sort wird davon ausgegangen dass ich das kleinste (oder das größte) Element ermitteln kann. Tauschen muss man auch hier. Nur werden nicht zwei benachbarte Elemente getauscht. In Wikipedia heisst es: "Suche das kleinste Element in U und vertausche es mit dem ersten Element."

Darauf ruzmzureiten dass Selektion-Sort eine Variante von Bubble-Sort ist oder nicht, ist in meinen Augen kleinkariert oder erbsenzählerei. Das ist wie ähnlich wie "Das Glas ist halb voll"/"Das Glas ist halb leer".

Beide Algos sortieren, und das mit hilfe von tauschen. Es unterscheidet sich lediglich der Ansatz zum Tauschen.

 

[SebiB90]

Bei Bubble-Sort werden immer nur zwei Elemente verglichen, die direkt nebeneinander stehen und dann eventuell vertauscht.
Macht das der Algorithmus von Deinem Lehrer?

Bei der ersten Variante, die ja inordnung war ja.
bei der anderen, die selektionsort war, nicht, denn da ging er folgender Maßen vor.

Mal in Java übersetzt:

for(int i = 0; i < array.length-2; i++) {
  for(int j = i; j < array.length-1; j++) {
    if(array[j] < array[i]) {
      int hilf = array[i];
      array[i] = array[j];
      array[j] = hilf;
    }
  }
}

 

[tfa]

Das sieht in der Tat nach Selektion-Sort aus (wenn auch nicht optimal implementiert).

@alex: Es bestreitet sicher keiner, dass das zwei funktionierende Algorithmen sind. Aber wenn ein Lehrer etwas falsch erklärt bzw. einen Algorithmus unter falschem Namen verkaufen will, muss man ihm das doch sagen.

 

[Marco13]

mittlerweile sind wir echt weit in Info, wir machen Sortier Algos *IronieWiederAbstell*.

"If you think you're a really good programmer... read (Knuth's) Art of Computer Programming...You should definitely send me a resume if you can read the whole thing." (Bill Gates)

Das Zitat greife ich mal auf, und beziehe es auf Kapitel 3, "Sorting and Searching".

 

[SebiB90]

Das sieht in der Tat nach Selektion-Sort aus (wenn auch nicht optimal implementiert).

@alex: Es bestreitet sicher keiner, dass das zwei funktionierende Algorithmen sind. Aber wenn ein Lehrer etwas falsch erklärt bzw. einen Algorithmus unter falschem Namen verkaufen will, muss man ihm das doch sagen.

darum gehts mir^^

bzgl der Ausdrucks. ich hab den titel mal abgeändert^^


@Marco:
das ich guter Programmierer bin hab ich net gesagt. Nur mir gehts da bissel zu langsam vorwärts. Und z.b. auch der letzte Jahrgang hatte zu diesem Zeitpunkt bereits mit OOP angefangen. Großteil der Klasse weiß nichtmal was ne Methode ist^^

 

[tfa]

Steht im Knuth eigentlich auch Stooge-Sort? Der ist mal bei uns in einer Vordiplomsklausur drangekommen.

 

[Marco13]

Hey, wer hat denn den Titel geändert? :lol: (Ich finde, man darf ALLE Fragen stellen... Also: Spinnt derjenige, der den Titel geändert hat? :bae: :wink: )

 

[SebiB90]

Hey, wer hat denn den Titel geändert? :lol: (Ich finde, man darf ALLE Fragen stellen... Also: Spinnt derjenige, der den Titel geändert hat? :bae: :wink: )

alex hat sich über Ausdruck beschwert und wenn ichs nochma les, bissel blöd formuliert
daher geändert

back to topic pls^^

 

[Marco13]

Ah, das mit der Titel-Änderung ist ja dann klar :wink:

@tfa: Gff. kann ich nachher mal nachsehen, aber das Buch stammt von 1973, und wer weiß, wann Stoogesort entwickelt wurde. (Ein kurze Websuche hat da keinen Aufschluß gebracht - wohl aber einen möglichen Grund, warum er vielleicht NICHT behandelt wurde:
http://www.nist.gov/dads/HTML/stoogesort.html
stooge sort - "Definition: A terribly inefficient sort algorithm...")

 

[tfa]

Richtig. Den gibt's auch nur zu Lehrzwecken

 

[Marco13]

"Back to topic"? Falls das noch nicht geklärt ist, und um da noch meine unbedeutende Meinung nachzureichen: Die Algorithmen "BubbleSort" und "SelectionSort" werden unterschiedlich geschrieben, unterschiedlich ausgesprochen, haben eine unterschiedliche Laufzeit, und werden unterschiedlich implementiert. Meine subjektive Antwort auf deine Frage im Titel ist also "Ja". (Auf die neue - bei der alten Frage ... weiß ich die Antwort nicht....)