Diploma Thesis Percolation Simulation
C++ Sourcecode Documentation

www.AndreasKrueger.de/thesis/code
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

quicksort.h File Reference

This graph shows which files directly or indirectly include this file:

Included by dependency graph

Go to the source code of this file.

Functions

template<class T> void swap1 (T &x, T &y)
template<class T> void quicksort1 (T v, NUMBER left, NUMBER right)
bool greatercoord (sphere *spheres, NUMBER sphno1, NUMBER sphno2, int coordinate)
bool sort_by_coordinate_slow (sphere *spheres, NUMLIST &source, NUMLIST &target, int direction)
void swap2 (NUMBER &x, NUMBER &y)
void quicksort_by_coordinate (sphere *spheres, NUMBER *sphno, NUMBER left, NUMBER right, int coordinate)
bool sort_by_coordinate_quick (sphere *spheres, NUMBER *temp_sphno, NUMLIST &source, NUMLIST &target, int direction)

Function Documentation

bool greatercoord (  sphere *    spheres,
NUMBER    sphno1,
NUMBER    sphno2,
int    coordinate
) 
 

Definition at line 34 of file quicksort.h.

References sphere::c, myVector::coord(), and NUMBER.

Referenced by quicksort_by_coordinate(), and sort_by_coordinate_slow(). 

00034                                                                                  {
00035                 return (spheres[sphno1].c.coord(coordinate) > spheres[sphno2].c.coord(coordinate));
00036 }

template<class T>
void quicksort1 (  T    v,
NUMBER    left,
NUMBER    right
) 
 

Definition at line 16 of file quicksort.h.

References NUMBER, and swap1().

Referenced by counters::sort_naivecount_and_analyze(). 

00016                                                 {   
00017   if (left>=right) return;
00018 
00019   swap1(v[left],v[(left+right)/2]);
00020   int last=left;
00021 
00022   for (NUMBER i = left+1; i <= right; i++) {
00023           if ((v[i].c) < (v[left].c)){
00024                   swap1(v[++last], v[i]);
00025           };
00026   }
00027   swap1(v[left],v[last]);
00028   quicksort1(v, left, last-1); 
00029   quicksort1(v,last+1, right);
00030 }

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

Definition at line 80 of file quicksort.h.

References greatercoord(), NUMBER, and swap2().

Referenced by sort_by_coordinate_quick(). 

00080                                                                                                          {   
00081 
00082   if (left>=right) return;
00083 
00084   swap2(sphno[left],sphno[(left+right)/2]);
00085 
00086   NUMBER last=left;
00087 
00088   for (NUMBER i = left+1; i <= right; i++) {
00089           // if (   (v[i].c) < (v[left].c)   ){
00090           if ( ! greatercoord(spheres, sphno[i],sphno[left],coordinate)   ){
00091                   swap2(sphno[++last], sphno[i]);
00092           };
00093   }
00094   swap2(sphno[left],sphno[last]);
00095   quicksort_by_coordinate(spheres,sphno,left,  last-1,coordinate); 
00096   quicksort_by_coordinate(spheres,sphno,last+1, right,coordinate);
00097 }

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

Definition at line 100 of file quicksort.h.

References NUMBER, and quicksort_by_coordinate(). 

00104                                                                                                 {
00105 
00106         if (source.size()==0 || &source==&target || direction== 0) return false;
00107 
00108         NUMLIST::iterator s1;
00109         NUMBER index=0;
00110         for (s1=source.begin();s1!=source.end();s1++) {
00111                 temp_sphno[index]=*s1;
00112                 index++;
00113         }
00114 
00115         int coordinate=abs(direction);
00116 
00117         quicksort_by_coordinate (spheres, temp_sphno, 0,index-1, coordinate);
00118 
00119         if (direction<0) {
00120                 for (NUMBER i=0;i<index;i++) {
00121                         target.push_front(temp_sphno[i]);
00122                 }
00123         }
00124         else {
00125                 for (NUMBER i=0;i<index;i++) {
00126                         target.push_back(temp_sphno[i]);
00127                 }
00128         }
00129 
00130         return true;
00131 }

bool sort_by_coordinate_slow (  sphere *    spheres,
NUMLIST &    source,
NUMLIST &    target,
int    direction
) 
 

Definition at line 40 of file quicksort.h.

References greatercoord(), and NUMBER. 

00043                                                                          {
00044         if (source.size()==0 || &source==&target) return false;
00045         NUMLIST::iterator s1,s2;
00046         int coordinate=abs(direction);
00047         target.insert(target.end(),source.begin(),source.end());
00048         bool swapyes;
00049         NUMBER temp1,temp2;
00050 
00051         for (s1=target.begin();s1!=target.end();s1++){
00052                 for (s2=s1;s2!=target.end();s2++) {
00053                         if (direction>0) swapyes=greatercoord(spheres, *s1,*s2,coordinate);
00054                          else swapyes=!greatercoord(spheres, *s1,*s2,coordinate);
00055                         if (swapyes){
00056                                 temp1=*s1;
00057                                 temp2=*s2;
00058                                 s2=target.erase(s2);
00059                                 s1=target.erase(s1);
00060                                 s1=target.insert(s1,temp2);
00061                                 s2=target.insert(s2,temp1);
00062                         }
00063                 }
00064         }
00065         return true;
00066 }

template<class T>
void swap1 (  T &    x,
T &    y
)  [inline]
 

Definition at line 8 of file quicksort.h.

Referenced by quicksort1(). 

00008                               {
00009         if (&x != &y){
00010                 T tmp = x; 
00011                 x = y; y = tmp;
00012         }
00013 }

void swap2 (  NUMBER &    x,
NUMBER &    y
) 
 

Definition at line 71 of file quicksort.h.

References NUMBER.

Referenced by quicksort_by_coordinate(). 

00071                                  {
00072         if (&x != &y){
00073                 NUMBER tmp = x; 
00074                 x = y; y = tmp;
00075         }
00076 }




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

www.AndreasKrueger.de/thesis/code