//---------------------------------------------------------------------------
#ifndef quickH
#define quickH
#include <stdlib.h>
//---------------------------------------------------------------------------
template <class item>
class sort
{
public:
  //Fuld sorterings algoritmer
    //PreC: data = listen, n_ = størrelse af liste, type = faldende/stigende orden (0/1)
    //PostC: Funktionen sortere en given liste i stigende eller faldende orden (type!)
    void quicksort(item* data, const int& n_, int type = 0);

    //Delfunktion til quick sort.
    //Funktionen sortere listen i 2 dele udfra pivoterings indeket.
    void partitioner(item* data, int n, int& pivot_index, int type);

    //Delfunktion til quick sort
    //Funktionen finder et det bedst egnede pivoterings indeks udfra 3 tilfældige indekser.
    int pivotering(item* data, int n);

  //Delvis sorterings algoritmer..
    //PreC: data = listen, n = størrelse af listen, parter = det søgte objekt,
    //type = om objekterne skal placeres først eller sidst i listeb (0/1)
    //PostC: Funktion udskiller et givent objekt(parter) henholdsvis således at
    //alle identiske objekter bliver lagt først eller sidst i arrayet, alt efter typen.
	//Den returnede værdi angiver indekset på det punkt på listen hvor objekterne
	//er blevet samlet til...
    int partsort(item* data, const int& n, item parter, int type = 0);
};

template <class item>
class search
{
public:
  //Konstruktør
    search() { srand(100); cursor = 0; }

  //Søge funktioner.
    //PreC: data = Liste, n = størrelse af listen, searched = søgte objekt,
    //index = det fundne index af det søgte objekt, start = start plads på listen
    //PostC: Funktionen forsøger at finde objektet, og returnere herved en
    //sandhedsværdi for udfaldet. Endvidere returneres indekset på den plads
    //på listen som objektet har.
    bool linearsearch(item* data, const int& n, item& searched, int& index, int start = 0);

    //PreC: data = liste, n_ = størrelse af listen, searched = søgt objekt,
    //index = indekset for det søgte objekt, type = om listen er sorteret i stigende
    //eller faldende orden (0/1). NB listen skal være sorteret!!!!
    //PostC: Funktionen søger binært gennem listen. Herefter returneres en
    //sandhedsværdie for om den findes, samt indekset på denne.
    bool binarysearch(item* data, const int& n_, item& searched, int& index, int type = 0);

    //Delfunktion til binær søgning. Funktionen returnere -1 hvis den søgte ikke
    //eksistere i listen...!
    int binary(item* data, int n, item& searched, int index, int antal, int type = 0);

    //PreC: data = liste, n_ = størrelse af listen, searched = søgt objekt,
    //index_start/slut = start/slut plads for søgt sektion,
    //Ersorteret = hvis listen ikke er sorteret i forvejen => 1 ellers 0.
    //type = om listen er sorteret i stigende eller faldende orden (0/1)
    //PostC: Funktionen lokalisere det interval som det søgte objekt på listen
    //dækker. Hvis objektet ikke eksistere på listen returneres en sandhedsværdi.
    bool sectionsearch(item* data, const int& n_, item& searched, int& index_start,
                       int& index_slut, int ErSorteret = 0, int type = 0);
private:
    int cursor; //Angiver den plads på listen som det sidst objekt blev fundet på.
}; 
#include "sort.template"
#endif
