//program suchen (input, output);
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

long int liste[10000];  // Liste zum Sortieren
long int copy[10000];   // Original-Liste, soll nicht geaendert werden
long int laenge;        // Anzahl der Elemente in der Liste

char dateiname[255];
char d [200];
char op;
long int nr_cmp;


class Liste
{
private:
public:
   //Liste();
   //~Liste();
   long int mergesort ();
   long int heapsort ();
   long int quicksort ();
   long int einfuegesort ();
   void CREATE (void);
   void GIBAUS (void);
};


//============================ab hier veraendern=========================
// Elemente der Liste laufen von 0 bis laenge-1 (C/C++-Konvention)

// Fuer jede der vier Methoden: liste sortieren (ist globale Variable),
// und Anzahl der benoetigten Schritte zurueckliefern.
long int Liste::mergesort ()
   {
   return 0;
   }

long int Liste::heapsort ()
   {
   return 0;
   }

long int Liste::quicksort ()
   {
   return 0;
   }

long int Liste::einfuegesort ()
   {
   return 0;
   }


//============Der folgende Teil darf nicht veraendert werden==============

void copyliste (long int laenge)
   {
   long int i;
   for (i=0; i<laenge; i++)
      {
      liste[i] = copy[i];  // Hole "Backup" der Liste zurueck
      }
   } // initliste

long int istSortiert (long int von, long int bis)
   {                 // testet ob die Liste sortiert ist
   long int i;
   if (von >= bis) return 1;
   for (i=von; i<bis; i++)
      {
      if (liste[i] > liste[i+1]) return 0;
      }
   return 1;
   } // testliste



int main (void)             
   {
   Liste list;
   char Zeile[12]; // eingelesene Zeile
   laenge = 0;
   cout << "Name der Eingabedatei: ";
   cin >> dateiname;
   
   ifstream eingabe (dateiname, ios::in | ios::nocreate);
                           // oeffne Datei zum Auslesen
   while (eingabe.good())  // Bis wir am Zeilenende angekommen sind
      {
      eingabe.getline(Zeile,12);
      if (strlen(Zeile)>0)
         {
         copy[laenge]=atoi(Zeile);
         laenge++;
         }
      }
      cout << "Hab "<< laenge <<" Elemente eingelesen.\n";
   while (1)
      {
      cout << "\n ========Sortier-Algorithmus:========= \n";
      cout << "Sortieren durch Einfuegen <E>\n";
      cout << "Quicksort .  .  .  .  .   <Q>\n";
      cout << "Heapsort   .  .  .  .  .  <H>\n";
      cout << "Mergesort   .  .  .  .  . <M>\n";
      cout << "Ende   .  .  .  .  .  .   <S>  ?:>";
      cin >>op;
      switch (op)
         {
         case 'e':
         case 'E':
            copyliste(laenge);
            nr_cmp = list.einfuegesort();
            if (istSortiert(0, laenge-1)==1)
               {
               cout << "Einfuegesort hat Liste erfolgreich sortiert!\n";
               cout << "Es wurden " << nr_cmp << " Vergleiche benoetigt\n";
               }
            else
               cout << "Einfuegesort hat VERSAGT: Liste ist nicht sortiert!\n";
            break;
         case 'q':
         case 'Q':
            copyliste(laenge);
            nr_cmp = list.quicksort();
            if (istSortiert(0,laenge-1)==1)
               {
               cout << "Quicksort hat Liste erfolgreich sortiert!\n";
               cout << "Es wurden " << nr_cmp << " Vergleiche benoetigt\n";
               }
            else
               cout << "Quicksort hat VERSAGT: Liste ist nicht sortiert!\n";
            break;
         case 'h':
         case 'H':
            copyliste(laenge);
            nr_cmp = list.heapsort();
            if (istSortiert(0,laenge-1)==1)
               {
               cout << "Heapsort hat Liste erfolgreich sortiert!\n";
               cout << "Es wurden " << nr_cmp << " Vergleiche benoetigt\n";
               }
            else
               cout << "Heapsort hat VERSAGT: Liste ist nicht sortiert!\n";
            break;
         case 'm':
         case 'M':
            copyliste(laenge);
            nr_cmp = list.mergesort();
            if (istSortiert(0,laenge-1)==1)
               {
               cout << "Mergesort hat Liste erfolgreich sortiert!\n";
               cout << "Es wurden " << nr_cmp << " Vergleiche benoetigt\n";
               }
            else
               cout << "Mergesort hat VERSAGT: Liste ist nicht sortiert!\n";
            break;
         case 's':
         case 'S':
            return 0;
         default:
            ;
         }
      }         
   }