\section{search-sort.h File Reference}
\label{search-sort_h}\index{search-sort.h@{search-sort.h}}


This graph shows which files directly or indirectly include this file:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=175pt]{search-sort_h_dep_incl}
\end{center}
\end{figure}
\subsection*{Functions}
\begin{CompactItemize}
\item 
void {\bf search\_\-swap} (T \&t1, T \&t2)
\item 
void {\bf Bubble\-Sort} (T $\ast$A, int num)
\item 
void {\bf Bubble\-Sort\-Ptrs} (T $\ast$$\ast$A, int num)
\item 
void {\bf Bubble\-Sort\-R} (T $\ast$A, int num)
\item 
void {\bf Bubble\-Sort\-Ptrs\-R} (T $\ast$$\ast$A, int num)
\item 
int {\bf Partition} (T $\ast$A, int p, int r)
\item 
int {\bf Partition\-Ptrs} (T $\ast$$\ast$A, int p, int r)
\item 
void {\bf Rec\-Quick\-Sort} (T $\ast$A, int p, int r)
\item 
void {\bf Rec\-Quick\-Sort\-Ptrs} (T $\ast$$\ast$A, int p, int r)
\item 
void {\bf Quick\-Sort} (T $\ast$A, int Num)
\item 
void {\bf Quick\-Sort\-Ptrs} (T $\ast$$\ast$A, int Num)
\item 
int {\bf Bin\-Search} (const T $\ast$A, int Num, const T \&x)
\item 
int {\bf Bin\-Search\-Ptr} (T $\ast$$\ast$A, int Num, const T \&x)
\item 
int {\bf Select\-Partition} (T $\ast$A, int p, int r, T x)
\item 
double {\bf Linear\-Select} (double $\ast$L, int k, int n)
\end{CompactItemize}


\subsection{Function Documentation}
\index{search-sort.h@{search-sort.h}!BinSearch@{BinSearch}}
\index{BinSearch@{BinSearch}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int Bin\-Search (const T $\ast$ {\em A}, int {\em Num}, const T \& {\em x})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a11}




Definition at line 192 of file search-sort.h.

Referenced by dd\-Graph::Copy(), sd\-Vertex::Get\-In\-Edge\-Index(), sd\-Vertex::Get\-Out\-Edge\-Index(), and sd\-Graph::Get\-Vertex\-Index().\footnotesize\begin{verbatim}00193   {
00194     // left index, right index, pivot, respectively.
00195     //
00196     int i=0;
00197     int j=Num-1;
00198     int p;
00199 
00200     while((i<=j) && (j>=0))
00201       {
00202         p = (j+i)/2;
00203         if(x < A[p]) j = p-1;
00204         else if(x > A[p]) i = p+1;
00205         else return p;
00206       }
00207 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!BinSearchPtr@{BinSearchPtr}}
\index{BinSearchPtr@{BinSearchPtr}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int Bin\-Search\-Ptr (T $\ast$$\ast$ {\em A}, int {\em Num}, const T \& {\em x})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a12}




Definition at line 211 of file search-sort.h.\footnotesize\begin{verbatim}00212   {
00213     // left index, right index, pivot, respectively.
00214     //
00215     int i=0;
00216     int j=Num-1;
00217     int p;
00218 
00219     while((i<=j) && (j>=0))
00220       {
00221         p = (j+i)/2;
00222         if(x < *(A[p])) j = p-1;
00223         else if(x > *(A[p])) i = p+1;
00224         else return p;
00225       }
00226 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!BubbleSort@{BubbleSort}}
\index{BubbleSort@{BubbleSort}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Bubble\-Sort (T $\ast$ {\em A}, int {\em num})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a1}




Definition at line 51 of file search-sort.h.\footnotesize\begin{verbatim}00051                                      {
00052   bool stillGoing;
00053   do {
00054     stillGoing = false;
00055     for( int i=0; i<num-1; i++ ) {
00056       if( A[i] > A[i+1] ) {
00057         search_swap( A[i], A[i+1] );
00058         stillGoing = true;
00059       }
00060     }
00061   }
00062 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!BubbleSortPtrs@{BubbleSortPtrs}}
\index{BubbleSortPtrs@{BubbleSortPtrs}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Bubble\-Sort\-Ptrs (T $\ast$$\ast$ {\em A}, int {\em num})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a2}




Definition at line 65 of file search-sort.h.\footnotesize\begin{verbatim}00065                                           {
00066   bool stillGoing;
00067   do {
00068     stillGoing = false;
00069     for( int i=0; i<num-1; i++ ) {
00070       if( *(A[i]) > *(A[i+1]) ) {
00071         search_swap( A[i], A[i+1] );
00072         stillGoing = true;
00073       }
00074     }
00075   }
00076 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!BubbleSortPtrsR@{BubbleSortPtrsR}}
\index{BubbleSortPtrsR@{BubbleSortPtrsR}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Bubble\-Sort\-Ptrs\-R (T $\ast$$\ast$ {\em A}, int {\em num})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a4}




Definition at line 93 of file search-sort.h.\footnotesize\begin{verbatim}00093                                            {
00094   bool stillGoing;
00095   do {
00096     stillGoing = false;
00097     for( int i=num-1;i>0; i-- ) {
00098       if( *(A[i]) < *(A[i-1]) ) {
00099         search_swap( A[i], A[i-1] );
00100         stillGoing = true;
00101       }
00102     }
00103   }
00104 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!BubbleSortR@{BubbleSortR}}
\index{BubbleSortR@{BubbleSortR}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Bubble\-Sort\-R (T $\ast$ {\em A}, int {\em num})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a3}




Definition at line 79 of file search-sort.h.\footnotesize\begin{verbatim}00079                                       {
00080   bool stillGoing;
00081   do {
00082     stillGoing = false;
00083     for( int i=num-1; i>0; i-- ) {
00084       if( A[i] < A[i-1] ) {
00085         search_swap( A[i], A[i-1] );
00086         stillGoing = true;
00087       }
00088     }
00089   }
00090 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!LinearSelect@{LinearSelect}}
\index{LinearSelect@{LinearSelect}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}double Linear\-Select (double $\ast$ {\em L}, int {\em k}, int {\em n})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a14}




Definition at line 263 of file search-sort.h.\footnotesize\begin{verbatim}00263                                                     {
00264   // returns the k'th smallest element in L.
00265   // !! k is in the set {1 -> n} for an n element list. !! (not 0->n-1)
00266   // n represents the number of elements in L.
00267 
00268   int i;
00269   if (n <=10) { 
00270     RecQuickSort(L, 0, n-1);
00271     return L[k-1];  
00272   }
00273   int N = (int) ((n+4)/5);
00274   double ** S = new double * [N];
00275   int j = 0;
00276   for (i = 0; i < (N-1); i++){
00277     S[i] = new double [5];
00278     for (int u =0; u<5; u++) S[i][u] = L[j++];
00279   }
00280   S[N-1] = new double [5];
00281   int rem = n-j;
00282   for (i = 0; i < rem; i++){
00283     S[N-1][i] = L[j+i];
00284   }
00285   double * X = new double [N];
00286   for (i = 0;i<N-1;i++){
00287     RecQuickSort(S[i], 0, 4);
00288     X[i] = S[i][2];
00289   }
00290   if (rem == 1) X[N-1] = S[i][0];
00291   else {
00292     RecQuickSort(S[i], 0, rem-1);
00293     if (rem == 4) X[N-1] = S[i][2];
00294     else X[N-1] = S[i][1];
00295   }
00296   for (i = 0;i<N;i++){
00297     delete [] S[i];
00298   }
00299 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!Partition@{Partition}}
\index{Partition@{Partition}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int Partition (T $\ast$ {\em A}, int {\em p}, int {\em r})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a5}




Definition at line 107 of file search-sort.h.

Referenced by Rec\-Quick\-Sort().\footnotesize\begin{verbatim}00108   {
00109     T tmp;
00110     T x = A[p];
00111     int i = p-1;
00112     int j = r+1;
00113 
00114     while(1)
00115       {
00116         --j;
00117         while(A[j]>x) { --j; }
00118         ++i;
00119         while(A[i]<x) { ++i; }
00120 
00121         //
00122         // Swap the values at i and j.
00123         if(i<j)
00124           {
00125             tmp  = A[i];
00126             A[i] = A[j];
00127             A[j] = tmp;
00128           }
00129         else return j;
00130       }
00131 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!PartitionPtrs@{PartitionPtrs}}
\index{PartitionPtrs@{PartitionPtrs}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int Partition\-Ptrs (T $\ast$$\ast$ {\em A}, int {\em p}, int {\em r})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a6}




Definition at line 134 of file search-sort.h.

Referenced by Rec\-Quick\-Sort\-Ptrs().\footnotesize\begin{verbatim}00135   {
00136     T * tmp;
00137     T * x = A[p];
00138     int i = p-1;
00139     int j = r+1;
00140 
00141     while(1)
00142       {
00143         --j;
00144         while(*(A[j])>*x) { --j; }
00145         ++i;
00146         while(*(A[i])<*x) { ++i; }
00147 
00148         if(i<j)
00149           {
00150             tmp  = A[i];
00151             A[i] = A[j];
00152             A[j] = tmp;
00153           }
00154         else return j;
00155       }
00156 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!QuickSort@{QuickSort}}
\index{QuickSort@{QuickSort}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Quick\-Sort (T $\ast$ {\em A}, int {\em Num})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a9}




Definition at line 181 of file search-sort.h.

Referenced by sd\-Graph::Copy(), sd\-Vertex::Sort\-Edges(), and sd\-Graph::Sub\-Graph().\footnotesize\begin{verbatim}00182   { 
00183     if(Num<2) return;
00184     RecQuickSort(A, 0, Num-1); 
00185 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!QuickSortPtrs@{QuickSortPtrs}}
\index{QuickSortPtrs@{QuickSortPtrs}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Quick\-Sort\-Ptrs (T $\ast$$\ast$ {\em A}, int {\em Num})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a10}




Definition at line 188 of file search-sort.h.

Referenced by Process::assert\-Order().\footnotesize\begin{verbatim}00189   { if(Num<2) return; RecQuickSortPtrs(A,0,Num-1); }
00190 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!RecQuickSort@{RecQuickSort}}
\index{RecQuickSort@{RecQuickSort}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Rec\-Quick\-Sort (T $\ast$ {\em A}, int {\em p}, int {\em r})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a7}




Definition at line 159 of file search-sort.h.

Referenced by Linear\-Select(), Segments::QSort\-Reduce(), and Quick\-Sort().\footnotesize\begin{verbatim}00160   {
00161     if(p<r)
00162       {
00163         int q = Partition(A,p,r);
00164         RecQuickSort(A,p,q);
00165         RecQuickSort(A,q+1,r);
00166       }
00167 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!RecQuickSortPtrs@{RecQuickSortPtrs}}
\index{RecQuickSortPtrs@{RecQuickSortPtrs}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void Rec\-Quick\-Sort\-Ptrs (T $\ast$$\ast$ {\em A}, int {\em p}, int {\em r})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a8}




Definition at line 170 of file search-sort.h.

Referenced by Quick\-Sort\-Ptrs().\footnotesize\begin{verbatim}00171   {
00172     if(p<r)
00173       {
00174         int q = PartitionPtrs(A,p,r);
00175         RecQuickSortPtrs(A,p,q);
00176         RecQuickSortPtrs(A,q+1,r);
00177       }
00178 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!SelectPartition@{SelectPartition}}
\index{SelectPartition@{SelectPartition}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}int Select\-Partition (T $\ast$ {\em A}, int {\em p}, int {\em r}, T {\em x})\hspace{0.3cm}{\tt  [inline]}}\label{search-sort_h_a13}




Definition at line 230 of file search-sort.h.

Referenced by Linear\-Select().\footnotesize\begin{verbatim}00231   {
00232     // as above, but able to specify partion element
00233     T tmp;
00234     int i = p-1;
00235     int j = r+1;
00236 
00237     while(1)
00238       {
00239         --j;
00240         while(A[j]>x) { --j; }
00241         ++i;
00242         while(A[i]<x) { ++i; }
00243 
00244         //
00245         // Swap the values at i and j.
00246         if(i<j)
00247           {
00248             tmp  = A[i];
00249             A[i] = A[j];
00250             A[j] = tmp;
00251           }
00252         else return j;
00253       }
00254 \end{verbatim}\normalsize 
\index{search-sort.h@{search-sort.h}!search_swap@{search\_\-swap}}
\index{search_swap@{search\_\-swap}!search-sort.h@{search-sort.h}}
\subsubsection{\setlength{\rightskip}{0pt plus 5cm}void search\_\-swap (T \& {\em t1}, T \& {\em t2})\hspace{0.3cm}{\tt  [static]}}\label{search-sort_h_a0}




Definition at line 42 of file search-sort.h.

Referenced by Bubble\-Sort(), Bubble\-Sort\-Ptrs(), Bubble\-Sort\-Ptrs\-R(), and Bubble\-Sort\-R().\footnotesize\begin{verbatim}00043 {
00044         T t = t1;
00045         t1 = t2;
00046         t2 = t;
00047 \end{verbatim}\normalsize 
