PMG2527 4/Sortierverfahren implementiert

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
== Sortieren durch Auswählen (Minimumsuche) ==


        <b>Prinzip: Aus einer Menge wird das kleinste Element ausgewählt und mit dem ersten Element vertauscht.
        Diese Vorgänge werden wiederholt ,wobei die Anzahl der Elemente bei jeder Wiederholung von 
        vorn um eins verringert wird.
        Zuletzt werden nur noch zwei Elemente überprüft und gegebenenfalls vertauscht.</b>

[[Bild:Select.PNG]]


<code id="696de57b2f1e7">
function select(){
var zahl = [50,61,7,8,9,1,2,3]; // Feld mit 8 vorgegebenen Werten
for (var i = 0; i <=7; i++){
  var mini=i;                   // Setze Merker
  for (var j = i + 1; j < 8; j++){
   if (zahl[j] < zahl[mini]) {  // Vergleich Zahl an Stelle j mit Merker
    mini=j;}
   }
    var h = zahl[i];            // vertauschen
    zahl[i] = zahl[mini];
    zahl[mini] = h;
//console.log(zahl[i]);           // Ausgabe
}
console.log(zahl)
}
</code>

<run id="696de57b2f3ff">
select()
</run>

== Sortieren durch Einfügen ==


        <b>Prinzip: Man wählt ein Element (nacheinander vom zweiten bis zum letzten) und fügt es jeweils an die richtige 
        Stelle der davorstehenden geordneten Teilmenge ein. </b>

[[Bild:Insert.PNG]]
ACHTUNG: i=2 auf i=1 ändern!



Implementieren Sie das ''Sortieren durch Einfügen'' analog zum Sortieren durch Auswählen!

<code id="696de57b2f268">
</code>

<run id="696de57b2f474">
</run>



== Sortieren durch Austauschen (Bubblesort) ==


        <b>Prinzip: Vom letzten Element einer Menge an werden jeweils zwei benachbarte Elemente verglichen und ausgetauscht, wenn
        sie falsch sortiert sein sollten. Dabei wandert da kleinste Element an die erste Stelle.
        Das Vergleichen und Austauschen wird mit Ausnahme dieses bereits richtig postierten Elements wiederholt.
        Das Sortieren kann aufsteigend (links nach rechts) oder absteigend (umgekehrt) erfolgen.</b>

[[Bild:Bubblesort.PNG]]



Implementieren Sie ''Bubblesort'' analog zum Sortieren durch Auswählen!


<code id="696de57b2f2ed">
</code>

<run id="696de57b2f4e9">
</run>


=== Zusatzaufgabe ===

 Ersetzen Sie jeweils die vorgegebenen Feldinhalte in den Quelltexten durch zufällig erzeugte Zahlen.
 Lassen Sie sich diese vor dem Sortieren auch ausgeben.



== Quicksort ==


<code id="696de57b2f367">

</code>


<run id="696de57b2f562">

</run>




== weitere Sortierverfahren ==


Mergesort [[http://programmingwiki.de/Grundlagen_der_funktionsorientierten_Programmierung_mit_SCHEME/MergeSort]]


Gnomesort [[http://programmingwiki.de/Grundlagen_der_funktionsorientierten_Programmierung_mit_SCHEME/GnomeSort]]


<br>

== Literatur ==

* Fahldieck, Karl-Heinz: Algorithmen, Frankfurt am Main: Verlag Moritz Diesterweg, 1993
* Sedgewick, Robert: Algorithmen, Bonn:Addison-Wesley Publishing Company, 1992
* Hermann, Dietmar: Algorithmen Arbeitsbuch, Bonn; München; Paris, Addison-Wesley Publishing Company, 1992
* Junger, Hans u.a.: Informatik, Frankfurt am Main; Aarau, Verlag Moritz Diesterweg; Verlag Sauerländer AG, 1988