Diploma Thesis Percolation Simulation C++ Sourcecode Documentation

www.AndreasKrueger.de/thesis/code

                 

---

quicksort.h

Go to the documentation of this file.

// quicksort.h
// Quicksort-Template       
// laut Rehmann (sein Zitat: cf. K&R, p.87)
// implemented 2.5.2000
// version 2.0, last change 2.5.2000

template <class T>
inline void swap1(T& x, T& y) {
        if (&x != &y){
                T tmp = x; 
                x = y; y = tmp;
        }
}

template <class T>                                                                             
void quicksort1(T v, NUMBER left, NUMBER right) {   
  if (left>=right) return;

  swap1(v[left],v[(left+right)/2]);
  int last=left;

  for (NUMBER i = left+1; i <= right; i++) {
          if ((v[i].c) < (v[left].c)){
                  swap1(v[++last], v[i]);
          };
  }
  swap1(v[left],v[last]);
  quicksort1(v, left, last-1); 
  quicksort1(v,last+1, right);
}

//compare two sphere-numbers by the coordinate of the sphere

bool greatercoord (sphere *spheres, NUMBER sphno1, NUMBER sphno2,int coordinate) {
                return (spheres[sphno1].c.coord(coordinate) > spheres[sphno2].c.coord(coordinate));
}

// slow sort:

bool sort_by_coordinate_slow (sphere* spheres, 
                                                          NUMLIST &source, 
                                                          NUMLIST &target, 
                                                          int direction) {
        if (source.size()==0 || &source==&target) return false;
        NUMLIST::iterator s1,s2;
        int coordinate=abs(direction);
        target.insert(target.end(),source.begin(),source.end());
        bool swapyes;
        NUMBER temp1,temp2;

        for (s1=target.begin();s1!=target.end();s1++){
                for (s2=s1;s2!=target.end();s2++) {
                        if (direction>0) swapyes=greatercoord(spheres, *s1,*s2,coordinate);
                         else swapyes=!greatercoord(spheres, *s1,*s2,coordinate);
                        if (swapyes){
                                temp1=*s1;
                                temp2=*s2;
                                s2=target.erase(s2);
                                s1=target.erase(s1);
                                s1=target.insert(s1,temp2);
                                s2=target.insert(s2,temp1);
                        }
                }
        }
        return true;
}


// using quicksort: 

void swap2(NUMBER &x, NUMBER &y) {
        if (&x != &y){
                NUMBER tmp = x; 
                x = y; y = tmp;
        }
}

// void quicksort2(T v, NUMBER left, NUMBER right) {   

void quicksort_by_coordinate(sphere* spheres, NUMBER* sphno , NUMBER left, NUMBER right, int coordinate) {   

  if (left>=right) return;

  swap2(sphno[left],sphno[(left+right)/2]);

  NUMBER last=left;

  for (NUMBER i = left+1; i <= right; i++) {
          // if (   (v[i].c) < (v[left].c)   ){
          if ( ! greatercoord(spheres, sphno[i],sphno[left],coordinate)   ){
                  swap2(sphno[++last], sphno[i]);
          };
  }
  swap2(sphno[left],sphno[last]);
  quicksort_by_coordinate(spheres,sphno,left,  last-1,coordinate); 
  quicksort_by_coordinate(spheres,sphno,last+1, right,coordinate);
}


bool sort_by_coordinate_quick (sphere* spheres, 
                                                                                 NUMBER* temp_sphno, 
                                                                                 NUMLIST &source, 
                                                                                 NUMLIST &target, 
                                                                                 int direction) {

        if (source.size()==0 || &source==&target || direction== 0) return false;

        NUMLIST::iterator s1;
        NUMBER index=0;
        for (s1=source.begin();s1!=source.end();s1++) {
                temp_sphno[index]=*s1;
                index++;
        }

        int coordinate=abs(direction);

        quicksort_by_coordinate (spheres, temp_sphno, 0,index-1, coordinate);

        if (direction<0) {
                for (NUMBER i=0;i<index;i++) {
                        target.push_front(temp_sphno[i]);
                }
        }
        else {
                for (NUMBER i=0;i<index;i++) {
                        target.push_back(temp_sphno[i]);
                }
        }

        return true;
}

Diploma Thesis Sourcecode Documentation check out the text and the executable binaries

www.AndreasKrueger.de/thesis/code