Sortieralgorithmen

import java.util.Date;

/**
* Mergesort und Quicksort, möglichst keine Bibliotheken benutzen
*/
public class SortierAlgorithmen
{
   private final static int[] EINGABE_SORTIERT = { 1, 2, 3, 4, 5, 6, 7};
   private final static int[] EINGABE_ZUFAELLIG = { 7, 2, 5, 1, 3, 6, 4};

   private static class ArrayPaar
   {
       private int[] arrayLinks;
       private int[] arrayRechts;

       protected ArrayPaar(final int[] arrayLinks, final int[] arrayRechts)
       {
           this.arrayLinks = arrayLinks;
           this.arrayRechts = arrayRechts;
       }

       protected ArrayPaar(final int[] array)
       {
           assert array.length > 1;

           this.arrayLinks = arrayVonBis(array, 0, array.length / 2 - 1);
           this.arrayRechts = arrayVonBis(array, array.length / 2, array.length - 1);
           System.out.println("Neues ArrayPaar: arrayLinks");
           ausgabe(arrayLinks);
           System.out.println("Neues ArrayPaar: arrayRechts");
           ausgabe(arrayRechts);
       }

       public int[] getArrayLinks()
       {
           return this.arrayLinks;
       }

       public int[] getArrayRechts()
       {
           return this.arrayRechts;
       }

       private int[] arrayVonBis(final int[] eingabeArray, final int von, final int bis)
       {
           assert von <= bis;
           System.out.println("Array von " + von + " bis " + bis);
           int[] ausgabeArray = new int[bis - von + 1];
           int ausgabeArrayIndex = 0;
           for (int i = von; i <= bis; i++)
           {
               ausgabeArray[ausgabeArrayIndex] = eingabeArray[i];
               ausgabeArrayIndex++;
           }

           return ausgabeArray;
       }

       public int[] alsSortierterArray()
       {
           assert this.arrayLinks != null && this.arrayRechts != null;

           int[] ausgabeArray = new int[arrayLinks.length + arrayRechts.length];
           for (int i = 0; i < ausgabeArray.length; i++)
           {
               ausgabeArray[i] = 0;
           }

           // arrays einfügen und dadurch sortieren
           for (int j = 0; j < arrayLinks.length; j++)
           {
               ausgabeArray = vonRechtsEinfuegen(ausgabeArray, arrayLinks[j]);
           }
           for (int k = 0; k < arrayRechts.length; k++)
           {
               ausgabeArray = vonRechtsEinfuegen(ausgabeArray, arrayRechts[k]);
           }
           System.out.println("Zusammenfügen von arrayLinks");
           ausgabe(arrayLinks);
           System.out.println("und arrayRechts");
           ausgabe(arrayRechts);
           System.out.println("ergab");
           ausgabe(ausgabeArray);

           return ausgabeArray;
       }

       private int einfuegeIndex(final int[] array, final int einzufuegenderWert)
       {
           int index = -1;
           for (int i = array.length - 1; i >= 0; i--)
           {
               // Duplikate sind erlaubt, >=
               if (einzufuegenderWert >= array[i])
               {
                   index = i;
                   break;
               }
           }
           return index;
       }

       private int[] vonRechtsEinfuegen(final int[] array, final int einzufuegenderWert)
       {
           int index = einfuegeIndex(array, einzufuegenderWert);
           for (int i = 0; i < index; i++)
           {
               array[i] = array[i + 1];
           }
           System.out.println("Von rechts einfügen:");
           System.out.println("Füge " + einzufuegenderWert + " an Position " + index + " ein");
           array[index] = einzufuegenderWert;
           ausgabe(array);
           System.out.println("---");
           return array;
       }
   }

   private static int[] mergeSort(final int[] eingabeArray)
   {
//        wenn array 1 lang ist
       if (eingabeArray.length == 1)
       {
//        gib array zurück
           System.out.println("Array der Länge 1 wird unsortiert zurückgegeben:");
           ausgabe(eingabeArray);
           return eingabeArray;
       }
//        sonst
//        teile array
       ArrayPaar arrayPaar = new ArrayPaar(eingabeArray);
//        rufe mergesort für beide hälften auf
       int[] arrayLinks = mergeSort(arrayPaar.arrayLinks);
       int[] arrayRechts = mergeSort(arrayPaar.arrayRechts);
//        führe arrays zusammen
       ArrayPaar ausgabeArrayPaar = new ArrayPaar(arrayLinks, arrayRechts);
       return ausgabeArrayPaar.alsSortierterArray();
   }

   public static void main(final String[] args)
   {
       System.out.println("- - -");
       System.out.println("- - -");
       System.out.println("- - -");

       System.out.println("MergeSort eines sortierten Arrays:");
       int[] sortierterArray = mergeSort(EINGABE_SORTIERT);
       ausgabe(sortierterArray);
       System.out.println("MergeSort eines unsortierten Arrays:");
       sortierterArray = mergeSort(EINGABE_ZUFAELLIG);
       ausgabe(sortierterArray);

       System.out.println("- - -");
       System.out.println("- - -");
       System.out.println("- - -");

       System.out.println("QuickSort eines sortierten Arrays:");
       int[] sortierterArray2 = quickSort(EINGABE_SORTIERT);
       ausgabe(sortierterArray2);
       System.out.println("QuickSort eines unsortierten Arrays:");
       sortierterArray2 = quickSort(EINGABE_ZUFAELLIG);
       ausgabe(sortierterArray2);

       System.out.println("- - -");
       System.out.println("- - -");
       System.out.println("- - -");
   }

   private static int[] quickSort(final int[] eingabeArray)
   {
       System.out.println("Sortiere array:");
       ausgabe(eingabeArray);
       if (eingabeArray.length == 1)
       {
           return eingabeArray;
       }
//    beliebiges Element wählen
       int zufaelligerIndex = zufaelligerIndex(eingabeArray);
       int zufaelligesElement = eingabeArray[zufaelligerIndex];
       System.out.println("Index " + zufaelligerIndex + " gewählt, wert " + zufaelligesElement);
       int[] tempArray = arrayOhneElement(eingabeArray, zufaelligerIndex);
//    Array in kleinere und größere Elemente splitten
       int[] kleinerGleichArray = arrayElementeKleinerGleich(tempArray, zufaelligesElement);
       int[] groesserArray = arrayElementeGroesser(tempArray, zufaelligesElement);
//    Rekursion
       int[] kleinerSortierterArray = null;
       if (kleinerGleichArray != null)
       {
           System.out.println("Array der kleineren Werte:");
           ausgabe(kleinerGleichArray);
           kleinerSortierterArray = quickSort(kleinerGleichArray);
       }
       int[] groesserSortierterArray = null;
       if (groesserArray != null)
       {
           System.out.println("Array der größeren Werte:");
           ausgabe(groesserArray);
           groesserSortierterArray = quickSort(groesserArray);
       }
       if (kleinerSortierterArray != null && groesserSortierterArray != null)
       {
           System.out.println("MethodenEnde für Eingabearray |");
           ausgabe(eingabeArray);
           System.out.println("Ausgewählter Wert " + zufaelligesElement + " Index " + zufaelligerIndex);
           System.out.println("zurückgegebener Array");
           ausgabe(arraysVerbinden(elementAngehaengt(kleinerSortierterArray, zufaelligesElement), groesserSortierterArray));
           return arraysVerbinden(elementAngehaengt(kleinerSortierterArray, zufaelligesElement), groesserSortierterArray);
       }
       if (kleinerSortierterArray != null)
       {
           System.out.println("MethodenEnde für Eingabearray <<<");
           ausgabe(eingabeArray);
           System.out.println("Ausgewählter Wert " + zufaelligesElement + " Index " + zufaelligerIndex);
           System.out.println("zurückgegebener Array");
           ausgabe(elementAngehaengt(kleinerSortierterArray, zufaelligesElement));
           return elementAngehaengt(kleinerSortierterArray, zufaelligesElement);
       }
       if (groesserSortierterArray != null)
       {
           System.out.println("MethodenEnde für Eingabearray >>>");
           ausgabe(eingabeArray);
           System.out.println("Ausgewählter Wert " + zufaelligesElement + " Index " + zufaelligerIndex);
           System.out.println("zurückgegebener Array");
           ausgabe(elementVorneAngefuegt(groesserSortierterArray, zufaelligesElement));
           return elementVorneAngefuegt(groesserSortierterArray, zufaelligesElement);
       }
       return null;
   }

   private static int[] elementAngehaengt(final int[] eingabeArray, final int wert)
   {
       int[] ausgabeArray = new int[eingabeArray.length + 1];
       for (int i = 0; i < eingabeArray.length; i++)
       {
           ausgabeArray[i] = eingabeArray[i];
       }
       ausgabeArray[eingabeArray.length] = wert;
       return ausgabeArray;
   }

   private static int[] elementVorneAngefuegt(final int[] eingabeArray, final int wert)
   {
       int[] ausgabeArray = new int[eingabeArray.length + 1];
       ausgabeArray[0] = wert;
       for (int i = 1; i < ausgabeArray.length; i++)
       {
           ausgabeArray[i] = eingabeArray[i - 1];
       }
       return ausgabeArray;
   }

   private static int[] arraysVerbinden(final int[] arrayLinks, final int[] arrayRechts)
   {
       assert arrayLinks != null && arrayRechts != null;
       assert arrayLinks.length > 0 && arrayRechts.length > 0;
       int[] ausgabeArray = new int[arrayLinks.length + arrayRechts.length];
       for (int i = 0; i < arrayLinks.length; i++)
       {
           ausgabeArray[i] = arrayLinks[i];
       }
       for (int j = 0; j < arrayRechts.length; j++)
       {
           ausgabeArray[arrayLinks.length + j] = arrayRechts[j];
       }
       return ausgabeArray;
   }

   private static int[] arrayOhneElement(final int[] eingabeArray, final int index)
   {
       assert eingabeArray.length > 1 && index < eingabeArray.length;
       int[] ausgabeArray = new int[eingabeArray.length - 1];
       boolean indexWurdePassiert = false;
       for (int i = 0; i < eingabeArray.length; i++)
       {
           if (i != index)
           {
               if (indexWurdePassiert)
               {
                   ausgabeArray[i - 1] = eingabeArray[i];
               }
               else
               {
                   ausgabeArray[i] = eingabeArray[i];
               }
           }
           else
           {
               indexWurdePassiert = true;
           }
       }
       return ausgabeArray;
   }

   private static int indexDesWerts(final int[] eingabeArray, final int wert)
   {
       assert eingabeArray != null && eingabeArray.length >= 1;
       int index = -1;
       for (int i = 0; i < eingabeArray.length; i++)
       {
           if (eingabeArray[i] == wert)
           {
               index = i;
           }
       }
       return index;
   }

   private static int[] arrayElementeKleinerGleich(final int[] eingabeArray, final int wert)
   {
       int arrayGroesse = anzahlElementeKleinerGleich(eingabeArray, wert);
       IntegerListe tempListe = new IntegerListe();
       if (arrayGroesse > 0)
       {
           for (int i = 0; i < eingabeArray.length; i++)
           {
               if (eingabeArray[i] <= wert)
               {
                   tempListe.wertHinzufuegen(eingabeArray[i]);
               }
           }
           assert tempListe.getListenLaenge() == arrayGroesse;
       }
       return tempListe.getWerteliste();
   }

   private static int[] arrayElementeGroesser(final int[] eingabeArray, final int wert)
   {
       int arrayGroesse = anzahlElementeGroesser(eingabeArray, wert);
       IntegerListe tempListe = new IntegerListe();
       if (arrayGroesse > 0)
       {
           for (int i = 0; i < eingabeArray.length; i++)
           {
               if (eingabeArray[i] > wert)
               {
                   tempListe.wertHinzufuegen(eingabeArray[i]);
               }
           }
           assert tempListe.getListenLaenge() == arrayGroesse;
       }
       return tempListe.getWerteliste();
   }

   private static class IntegerListe
   {
       private int[] werteliste;

       public void wertHinzufuegen(final int wert)
       {
           if (werteliste == null)
           {
               werteliste = new int[1];
               werteliste[0] = wert;
           }
           else
           {
               int[] tempListe = new int[werteliste.length + 1];
               for (int i = 0; i < werteliste.length; i++)
               {
                   tempListe[i] = werteliste[i];
               }
               tempListe[werteliste.length] = wert;
               werteliste = tempListe;
           }
       }

       public void wertEntfernen(final int wert)
       {
           if (enthaeltWert(wert))
           {
               if (werteliste.length == 1)
               {
                   werteliste = null;
               }
               else
               {
                   werteliste = arrayOhneElement(werteliste, indexDesWerts(werteliste, wert));
               }
           }
       }

       private boolean enthaeltWert(final int wert)
       {
           boolean resultat = false;
           if (werteliste != null)
           {
               for (int i = 0; i < werteliste.length; i++)
               {
                   if (werteliste[i] == wert)
                   {
                       resultat = true;
                   }
               }
           }
           return resultat;
       }

       public int[] getWerteliste()
       {
           return werteliste;
       }

       public int getListenLaenge()
       {
           return werteliste.length;
       }

   }

   private static int anzahlElementeKleinerGleich(final int[] eingabeArray, final int wert)
   {
       int anzahl = 0;
       for (int i = 0; i < eingabeArray.length; i++)
       {
           if (eingabeArray[i] <= wert)
           {
               anzahl++;
           }
       }
       return anzahl;
   }

   private static int anzahlElementeGroesser(final int[] eingabeArray, final int wert)
   {
       int anzahl = 0;
       for (int i = 0; i < eingabeArray.length; i++)
       {
           if (eingabeArray[i] > wert)
           {
               anzahl++;
           }
       }
       return anzahl;
   }

   private static int zufaelligerIndex(final int[] eingabeArray)
   {
       Date date = new Date();
       int zufaelligerIndex = (int) (date.getTime() % eingabeArray.length);
       return zufaelligerIndex;
   }

   private static void ausgabe(final int[] array)
   {
       for (int i = 0; i < array.length; i++)
       {
           System.out.print(i + " ");
       }
       System.out.print(System.lineSeparator());
       for (int i = 0; i < array.length; i++)
       {
           System.out.print(array[i] + " ");
       }
       System.out.print(System.lineSeparator());
   }

}