#include "sortieren.h"

#include <iostream>
using namespace std;

void tausche(int & a, int & b) {
  int h=a; a=b; b=h;
}

void MinimumSort(int tosort[], const int l, const int r) {
  int mindex;
  for(int i=l;i<r;i++) {
    mindex=i;
    for(int j=i+1;j<=r;j++) if (tosort[j]<tosort[mindex]) mindex=j;
    tausche(tosort[i],tosort[mindex]);
  }
}



void BubbleSort(int tosort[], const int l, const int r) {
  for(int i=l;i<r;i++)
    for(int j=l;j<r-(i-l);j++) 
      if (tosort[j]>tosort[j+1]) tausche(tosort[j],tosort[j+1]);
}

void InsertionSort(int tosort[], const int l, const int r) {
  for(int i=l+1;i<=r;i++)
    for(int j=i;j>l;j--)
      if (tosort[j]<tosort[j-1]) { // dann tauschen
        tausche(tosort[j-1],tosort[j]);
      } else break; // sonst Schleifenabbruch
}

void QuickSort(int tosort[], const int l, const int r) {
  if (l<r) {
    int pl=l;
    int pr=r;
    int pivot=tosort[(l+r)/2];
    while (pl<=pr) {
      while (tosort[pl]<pivot) { pl++; }
      while (pivot<tosort[pr]) { pr--; }
      if (pl<=pr) { tausche(tosort[pl],tosort[pr]); pl++; pr--; }
    }
    QuickSort(tosort,l,pr);
    QuickSort(tosort,pl,r);
    // will man Speicher auf dem Stack sparen, ruft man das kleinere
    // Intervall zuerst auf. Das spart allerdings nur, wenn der zweite
    // Quicksortaufruf der letzte Befehl ist. Nur dann braucht sich
    // das System im Ablauf für den entsprechenden Aufruf nichts mehr
    // zu merken -> Stichwort: Tail-Rekursion
    // -> höchstens logarithmisch statt linear viele Variablen auf dem Stack
  }
}


int *kopie; // Array für Kopie in MergeSort
int *mtosort; // modulweit bekanntes Array, um Übergabe bei der Rekursion zu sparen

void MergeSortRek(const int, const int); // Vorwärtsdeklaration

void MergeSort(int tosort[], const int l, const int r) { // sortiert tosort[l..r]
  mtosort=tosort;
  kopie=new int[(r-l)/2+1]; // maximal benötigter Zusatzspeicher
  MergeSortRek(l,r);
  delete kopie;
}

void MergeSortRek(const int l, const int r) { // sortiert tosort[l..r]
  if (l<r) { // sonst ist nichts mehr zu tun
    int m=(l+r)/2;
    MergeSortRek(l,m);
    MergeSortRek(m+1,r);
    // Teilfelder sind jetzt rekursiv sortiert worden
    // Jetzt beide Teilfelder kombinieren: linkes Teilfeld kopieren
    // Beide zusammenfügen, dabei macht das rechte Teilfeld
    // stets ausreichend Platz, sodass keine Elemente überschrieben werden
    int lae1=m-l+1;
    for (int i=l;i<=m;i++) kopie[i-l]=mtosort[i];
    int p1=0; int p2=m+1; int pg=l; // linker Rand vom 1./2. Teilfeld
    while (p1<lae1 && p2<=r) { // solange noch Elemente vom 1. Teilfeld
      // in das 2. Teilfeld eingefügt werden müssen
      if (kopie[p1]<mtosort[p2]) {
        mtosort[pg++]=kopie[p1++];
      } else {
      	mtosort[pg++]=mtosort[p2++];
      }
    }
    while (p1<lae1) {// ggf. restliche Elemente vom 1. TF ans Ende kopieren
      mtosort[pg++]=kopie[p1++];
    } // bleiben noch Elemente vom 2. TF am Ende übrig, stehen diese bereits richtig
  }
}

// nur zum Vergleich: sink_topdown ist die klassische Variante von sink
// ist im Mittel in der Praxis aber etwa um den Faktor 2 langsamer
void sink_topdown(int tosort[], const int i, const int n) { // lässt das Element mit Index i
  // in einem Heap[1..n] so absinken, dass die Heapeigenschaft erfüllt ist
  // tosort ist der Zeiger auf das virtuelle Element Heap[0]
  int v=i; int l=2*v; int r=l+1;
  while (l<=n) { // es existiert noch mind. 1 Kind
    if (r<=n) { // beide Kinder existieren
      if (tosort[l]>tosort[r]) {
	if (tosort[l]>tosort[v]) { // Element sinkt links weiter
	  tausche(tosort[l],tosort[v]);
	  v=l; l=2*v; r=l+1;
	} else break; // Element sinkt nicht weiter
      } else {
	if (tosort[r]>tosort[v]) { // Element sinkt rechts weiter
	  tausche(tosort[r],tosort[v]);
	  v=r; l=2*v; r=l+1;
	} else break; // Element sinkt nicht weiter
      }
    } else { // l=n und das linke Kind ist ein Blatt
      if (tosort[l]>tosort[v]) tausche(tosort[l],tosort[v]);
      break;
    }
  }
}

int *heap; // modulweit bekanntes Array für Heapsort

// für die Praxis besser: sink als Bottom-up-Variante
void sink(const int i, const int n) { // lässt das Element heap[i]
  // im heap[1..n] so absinken, dass die Heapeigenschaft erfüllt ist
  int v=i; int l,r; int h1,h2;
  // bestimme Blatt des Einsinkpfades
  while (2*v<n) {
    l=2*v; r=l+1;
    if (heap[l] > heap[r]) { // sinkt in Richtung des größeren Kindes
      v=l;
    } else {
      v=r;
    }
  }
  if (2*v==n) {
    v=n; // Einzelkind
  }
  // v ist jetzt das Blatt des Einsinkpfades
  // im Einsinkpfad soweit nötig wieder aufsteigen
  while (heap[v] < heap[i]) { v=v/2; }
  // Elemente auf dem Pfad bis i rotieren
  h1=heap[v]; heap[v]=heap[i]; v=v/2;
  while (v > i) {
    h2=h1; h1=heap[v]; heap[v]=h2; v=v/2;
  }
  heap[i]=h1;
}

void HeapSort(int tosort[], const int l, const int r) { // sortiert tosort[l..r]
  heap=tosort+l-1; // heap zeigt jetzt auf das Element links vom linken Rand
  // auf heap[0] darf nicht zugegriffen werden!
  int n=r-l+1; // soviel Elemente werden sortiert
  // der zu sortierende Bereich steht jetzt in heap[1..n]
  // Heapaufbau
  for(int i=n/2;i>=1;i--) { sink(i,n); }
  // Sortierphase
  for(int i=n;i>1;i--) {
    tausche(heap[i],heap[1]);
    sink(1,i-1);
  }
}