Programmieren lernen

import java.util.Scanner;

/**
 * Mergesort als Beispiel der Rekursion
 * 
 * @author Philipp Gressly (phi@gressly.ch)
 */
/*
 * History: first Implementation: Sep 2, 2010 Bugs :
 */
public class MergeSort {
    public static void main(String[] args) {
        new MergeSort().top(); }

    
    
    void top() {
        int[] zahlen = einlesen();
        ausgabe(zahlen);
        System.out.println("Sortiere...");
        sortiere(zahlen);
        ausgabe(zahlen);
        System.out.println("... fertig.");
    }

    /**
     * Sortiere eine Zahlenreihe mit dem Merge-Sort verfahren (S. Theorieteil)
     */
    void sortiere(int[] zahlen) {
        // Rekursionsabbruch:
        // Leere Arrays und Arrays mit nur einer Zahl sind schon sortiert!
        if (zahlen.length < 2) {
            return;
        }

        // Aufteilen
        int[] links  = linkerTeilArray (zahlen);
        int[] rechts = rechterTeilArray(zahlen);

        // Rekursionsschritt
        sortiere(links);
        sortiere(rechts);

        // Zusammenfügen

        int indexLinks    = 0;
        int indexRechts   = 0;
        int indexResultat = 0;

        while (indexResultat < zahlen.length) {
            if (indexRechts >= rechts.length
                    || (indexLinks < links.length && links[indexLinks] < rechts[indexRechts])) {

                zahlen[indexResultat] = links[indexLinks];
                indexLinks = indexLinks + 1;
            } else {
                zahlen[indexResultat] = rechts[indexRechts];
                indexRechts = indexRechts + 1;
            }

            indexResultat = indexResultat + 1;
        }

    }

    int[] rechterTeilArray(int[] zahlen) {
        int   laengeRechteSeite = laengeRechteSeite(zahlen.length);
        int   laengeLinkeSeite  = laengeLinkeSeite(zahlen.length);
        int[] rechterTeilArray  = new int[laengeRechteSeite];
        int   indexRechterTeil  = 0;
        while(indexRechterTeil < laengeRechteSeite) {
            int wert = zahlen[laengeLinkeSeite + indexRechterTeil];
            rechterTeilArray[indexRechterTeil] = wert;
            indexRechterTeil = indexRechterTeil + 1;
        }
        return rechterTeilArray; 
    }

    int[] linkerTeilArray(int[] zahlen) {
        int   laengeLinkeSeite = laengeLinkeSeite(zahlen.length);
        int[] linkerTeilArray  = new int[laengeLinkeSeite];
        int   index            = 0;
        while (index < laengeLinkeSeite) {
            linkerTeilArray[index] = zahlen[index];
            index = index + 1;
        }

        return linkerTeilArray;
    }

    /**
     * Diese Funktion berechnet die Länge des halbierten Arrays.
     * Die linke und die rechte Seite sollten gleich sein.
     * Ist jedoch die anzahlElemente ungerade, so wird die  
     * linke seite um eins größer.
     * @return anzahlElemente / 2 (+1, falls ungerade)
     */
    int laengeLinkeSeite(int anzahlElemente) {
        if(ungerade(anzahlElemente)) {
            return anzahlElemente / 2 + 1;
        } 
        return anzahlElemente / 2;
    }

    /**
     * Wie linke Seite, jedoch für den zweiten (rechten) TeilArray.
     * rechteSeite + linkeSeite = anzahlElemente
     */
    int laengeRechteSeite(int anzahlElemente) {
        return anzahlElemente - laengeLinkeSeite(anzahlElemente);
    }

    boolean ungerade(int zahl) {
        return 1 == zahl % 2;
    }
    
    // Hilfsfunktionen
    
    void ausgabe(int[] zahlen) {
        System.out.println("Sortiert:");
        int index = 0;
        while (index < zahlen.length) {
            System.out.print(zahlen[index] + " ");
            index = index + 1;
        }
        System.out.println(); // neue Zeile
    }

    
    Scanner sc = new Scanner(System.in);
    int leseZahl(String meldung) {
        System.out.println(meldung + ": ");
        return sc.nextInt();
    }

    int[] einlesen() {
        int anzahl = leseZahl("Bitte Anzahl zu sortierende Elemente eingeben");
        int[] zahlen = new int[anzahl];
        int index = 0;
        while (index < anzahl) {
            zahlen[index] = leseZahl("Bitte geben Sie eine Zahl ein");
            index = index + 1;
        }
        return zahlen;
    }

} // end of class MergeSort
                

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    result += left[i:]
    result += right[j:]
    return result


def mergesort(list):
    if len(list) < 2:
        return list
    else:
        middle = len(list) / 2
        left = mergesort(list[:middle])
        right = mergesort(list[middle:])
        return merge(left, right)

k = [4, 9, 1, 8, 7, 3, 6, 8, 2, 3, 8]
print mergesort(k)
                

Lösung von: Martin Guggisberg (Universität Basel / PH FHNW)

function mergeSort(arr) {

  function merge(left, right) {
    let out = [],
        i = 0, j = 0;
    while (i < left.length && j < right.length)
      if (left[i] <= right[j]) {
        out.push(left[i]);
        i++;
      } else {
        out.push(right[j]);
        j++;
      }
      return out.concat(left.slice(i), right.slice(j));
    }

  if (arr.length < 2) return arr;
  let mid = Math.floor(arr.length / 2),
      lft = mergeSort(arr.slice(0, mid)),
      rgt = mergeSort(arr.slice(mid));
  return merge(lft, rgt);
}

// test
let test = [4, 9, 1, 8, 7, 3, 6, 8, 2, 3, 8];
console.log( mergeSort(test) );
                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)