source: liacs/pm/backup/sorteren.cc@ 7

#include <iostream>
#include <ctime>
using namespace std;

//Het maken van een random getal
int randomgetal () { // tussen 0 en 999
  static int getal = time (NULL) % 1000;
  getal = ( 621 * getal + 1 ) % 1000;
  return getal;
}

//Een list bestaat uit allemaal vakjes.
class Vakje {
 public:
  int Getal_int; //Waarde van het vakje
  Vakje * Volgende_Vakje_pt; //Zijn 'rechterbuur'
  Vakje * Vorige_Vakje_pt; //Zijn 'linkbuur'
};

class listvak {
  public:
    //default constuctor (NULL pointers)
    listvak( );
    //destructor: niks doen
    ~listvak( ) { };
    //creer de list van random lengte met randomgetallen
    void randomlist();
    //druk de list van links naar rechts af
    void drukaf_l_r();
    //druk de list van recht naar links af
    void drukaf_r_l();
    //sorteer de list, volgens bubblesort methode
    int sorteren();
    //merge L1 en L2 met opvolgend principe
    void merge(listvak * L1, listvak * L2);
    //vernietig de list.
    void vernietig();
  private:    
    Vakje * Eerste_Vakje_pt; //pointer naar het eerste vakje
    Vakje * Laatste_Vakje_pt; //pointer naar het laatste vakje
};

listvak::listvak( ) {
  Eerste_Vakje_pt = NULL;
  Laatste_Vakje_pt = NULL;
}

//voeg een AantalGetallen_int getallen toe aan de List die door Lbgin wordt gepointerd.
void listvak::randomlist() {
  Vakje * VakjeNew_Vakje_pt;
  
  for (int i = 0; i < randomgetal(); i++) {
    VakjeNew_Vakje_pt = new Vakje;
    VakjeNew_Vakje_pt->Getal_int = randomgetal();
    if (Eerste_Vakje_pt != NULL) {
      VakjeNew_Vakje_pt->Volgende_Vakje_pt = Eerste_Vakje_pt;
      VakjeNew_Vakje_pt->Volgende_Vakje_pt->Vorige_Vakje_pt = VakjeNew_Vakje_pt;
    }
    else {
      Laatste_Vakje_pt = VakjeNew_Vakje_pt;
    } //end if
    
    Eerste_Vakje_pt = VakjeNew_Vakje_pt;
  } //end for
} //end listvak::randomlist

//druk de list af van links naar rechts
void listvak::drukaf_l_r() {
 Vakje * Hulp_Vakje_pt = Eerste_Vakje_pt;
 while (Hulp_Vakje_pt != NULL) {
  cout << Hulp_Vakje_pt->Getal_int << " ";
  Hulp_Vakje_pt = Hulp_Vakje_pt->Volgende_Vakje_pt;
  } //end while
} //end listvak::drukaf_lr
  
//druk de list af van rechts naar links
void listvak::drukaf_r_l() {
 Vakje * Hulp_Vakje_pt = Laatste_Vakje_pt;
 while (Hulp_Vakje_pt != NULL) {
  cout << Hulp_Vakje_pt->Getal_int << " ";
  Hulp_Vakje_pt = Hulp_Vakje_pt->Vorige_Vakje_pt;
  } //end while
} //end listvak::drukaf_rl

//sorteren volgens de bubblesort methode (grootste getal achteraan)
//uitvoer: aantal verwisselingen die plaatsgevonden hebben.
int listvak::sorteren() {
  int Verwisselingen_int = 0;
  Vakje * BubbleHulp_Vakje_pt = Eerste_Vakje_pt; //Dit is het vakje dat gechecked wordt
  Vakje * BubbleStop_Vakje_pt = Laatste_Vakje_pt; //Hierna hoeft niet meer gechecked worden
  Vakje * BubbleVakA_Vakje_pt;
  Vakje * BubbleVakB_Vakje_pt;
  Vakje * BubbleVakC_Vakje_pt;
  Vakje * BubbleVakD_Vakje_pt;
  
  while (BubbleStop_Vakje_pt->Vorige_Vakje_pt != NULL) {  
    while ( BubbleHulp_Vakje_pt != BubbleStop_Vakje_pt ) { 
      if (BubbleHulp_Vakje_pt->Getal_int > BubbleHulp_Vakje_pt->Volgende_Vakje_pt->Getal_int) {
        /* Methode voor het omwisselen van vak B en C
         *            Oude situtatie
         * ___________________________________
         * | Vorige | Vak Nummer  | Volgende  |
         * |========|=============|===========|
         * |        |     A       |   1->B    |
         * | 2->A   |     B       |   3->C    |
         * | 4->B   |     C       |   5->D    |
         * | 6->C   |     D       |           |
         * ------------------------------------
         *        
         *            Nieuwe situatie
         * ___________________________________
         * | Vorige | Vak Nummer  | Volgende  |
         * |========|=============|===========|
         * |        |     A       |   1->C    |
         * | 2->C   |     B       |   3->D    |
         * | 4->A   |     C       |   5->B    |
         * | 6->B   |     D       |           |
         * ------------------------------------
         *
         * Uitzondering betreft als A de pointer in het begin is of als
         * D de eind pointer is.
         */
        BubbleVakA_Vakje_pt = BubbleHulp_Vakje_pt->Vorige_Vakje_pt;
        BubbleVakB_Vakje_pt = BubbleHulp_Vakje_pt;
        BubbleVakC_Vakje_pt = BubbleHulp_Vakje_pt->Volgende_Vakje_pt;
        BubbleVakD_Vakje_pt = BubbleHulp_Vakje_pt->Volgende_Vakje_pt->Volgende_Vakje_pt;
        
        //Pointer 1,2 
        if (BubbleVakA_Vakje_pt == NULL) {
          Eerste_Vakje_pt = BubbleVakC_Vakje_pt;
          BubbleVakC_Vakje_pt->Vorige_Vakje_pt = NULL;
        }
        else {
          BubbleVakA_Vakje_pt->Volgende_Vakje_pt = BubbleVakC_Vakje_pt;
          BubbleVakC_Vakje_pt->Vorige_Vakje_pt = BubbleVakA_Vakje_pt;
        } //end if
       
        //Pointer 3,4
        BubbleVakB_Vakje_pt->Vorige_Vakje_pt = BubbleVakC_Vakje_pt;
        BubbleVakC_Vakje_pt->Volgende_Vakje_pt = BubbleVakB_Vakje_pt;

        //Pointer 5,6
        if (BubbleVakD_Vakje_pt == NULL) {
          Laatste_Vakje_pt = BubbleVakB_Vakje_pt;
          BubbleVakB_Vakje_pt->Volgende_Vakje_pt = NULL;
          BubbleStop_Vakje_pt = BubbleVakB_Vakje_pt;
        }
        else {
          BubbleVakD_Vakje_pt->Vorige_Vakje_pt = BubbleVakB_Vakje_pt;
          BubbleVakB_Vakje_pt->Volgende_Vakje_pt = BubbleVakD_Vakje_pt;
        } //end if

        //In het geval dat het vakje van de stop pointer kleiner is als het vakje ervoor,
        //zal de stop pointer over het nieuwe vakje moeten vallen, anders komt hij het stop
        //teken nooit tegen.
        // A B C D
        // 5 9 7 10
        //   ^ ^ 
        //   | |Stop pointer 
        //   | Huidige Waarde
        // 
        // ZONDER AANPASSING          MET AANPASSING
        //
        // A C B D                    A C B D
        // 5 7 9 10                   5 7 9 10
        //   ^ ^                        ^ ^
        //   | |Huidige Waarde          | |Huidige Waarde + Stop Pointer
        //   | Stop Pointer             |
        //
        if (BubbleStop_Vakje_pt == BubbleVakC_Vakje_pt) {
          BubbleStop_Vakje_pt = BubbleVakB_Vakje_pt; 
        } //end if
        
        Verwisselingen_int++;
      }
      else {
        BubbleHulp_Vakje_pt = BubbleHulp_Vakje_pt->Volgende_Vakje_pt;
      } //end if
    } //end while
    BubbleHulp_Vakje_pt = Eerste_Vakje_pt;
    BubbleStop_Vakje_pt = BubbleStop_Vakje_pt->Vorige_Vakje_pt;
  } //end while
  return (Verwisselingen_int);
} //end listvak::sorteren

void listvak::merge(listvak * L1, listvak * L2) {
  bool Toevoegen_bool = true; //zolang true bestaan er nog waardes die toegevoegd moeten worden
  
  Vakje * HulpL1_Vakje_pt = L1->Laatste_Vakje_pt; //pointer die bijhoudt waar we in L1 zijn
  Vakje * HulpL2_Vakje_pt = L2->Laatste_Vakje_pt; //pointer die bijhoudt waar we in L2 zijn
  
  Vakje * VakjeNew_Vakje_pt; //pointer bij gebruikt wordt bij het maken van nieuwe vakjes

  while (Toevoegen_bool) {
    VakjeNew_Vakje_pt = new Vakje;
    if (Eerste_Vakje_pt != NULL) {
      VakjeNew_Vakje_pt->Volgende_Vakje_pt = Eerste_Vakje_pt;
      VakjeNew_Vakje_pt->Volgende_Vakje_pt->Vorige_Vakje_pt = VakjeNew_Vakje_pt;
    }
    else {
      Laatste_Vakje_pt = VakjeNew_Vakje_pt;
    } //end if
    Eerste_Vakje_pt = VakjeNew_Vakje_pt;
 
    if ((HulpL1_Vakje_pt != NULL) && (HulpL2_Vakje_pt != NULL)) { //beiden bevatten nog een getal
      if (HulpL1_Vakje_pt->Getal_int > HulpL2_Vakje_pt->Getal_int) {
        VakjeNew_Vakje_pt->Getal_int = HulpL1_Vakje_pt->Getal_int;
        HulpL1_Vakje_pt = HulpL1_Vakje_pt->Vorige_Vakje_pt;
      }
      else {
        VakjeNew_Vakje_pt->Getal_int = HulpL2_Vakje_pt->Getal_int;
        HulpL2_Vakje_pt = HulpL2_Vakje_pt->Vorige_Vakje_pt;
      } //end if
    }  
    else if (HulpL1_Vakje_pt != NULL) { //L2 leeg, enkel waardes uit L1 plakken
        VakjeNew_Vakje_pt->Getal_int = HulpL1_Vakje_pt->Getal_int;
        HulpL1_Vakje_pt = HulpL1_Vakje_pt->Vorige_Vakje_pt;
    }
    else if (HulpL2_Vakje_pt != NULL) { //L1 leeg, enkel waardes uit L2 plakken
        VakjeNew_Vakje_pt->Getal_int = HulpL2_Vakje_pt->Getal_int;
        HulpL2_Vakje_pt = HulpL2_Vakje_pt->Vorige_Vakje_pt;
    }
    else { //alles leeg, 'over en sluiten'
      Toevoegen_bool = false;
    } //end if
  } //end while
} //end listvak::merge

//vernietig de list
void listvak::vernietig() {
  Vakje * Hulp_Vakje_pt;
  while (Eerste_Vakje_pt != NULL) {
    Hulp_Vakje_pt = Eerste_Vakje_pt->Volgende_Vakje_pt;
    delete Eerste_Vakje_pt;
    Eerste_Vakje_pt = Hulp_Vakje_pt;
  } //end while;    
  Laatste_Vakje_pt = NULL;
} //end listvak::vernietig
    
int main() {
  listvak L1;
  listvak L2;
  listvak L3;
  L1.randomlist();
  L2.randomlist();
  L1.sorteren();
  L2.sorteren();
  L1.drukaf_l_r();
  cout << endl << endl;
  L2.drukaf_l_r();
  cout << endl << endl;
  L3.merge(&L1,&L2);
  cout << endl << endl;
  L3.drukaf_l_r();
  cout << endl;
  
}