Quicksort template. More...
#include <rquicksort.h>
Public Member Functions | |
RQuickSort (C **tab=0, size_t max=0) | |
RQuickSort (iRContainer< C > &cont) | |
void | Order (void) |
void | Order (C **tab, size_t max) |
virtual | ~RQuickSort (void) |
Private Member Functions | |
virtual int | Compare (C *obj1, C *obj2) |
size_t | Partition (size_t left, size_t right, size_t pivotIndex) |
void | Quicksort (size_t left, size_t right) |
Private Attributes | |
C ** | Tab |
size_t | Max |
Detailed Description
template<class C>
class R::RQuickSort< C >
Quicksort template.
This class represent an implementation of the quicksort algorithm to sort a given set of elements (stored as an array of pointers).
- Template Parameters
-
C The class of the elements to be sorted.
To make the necessary comparisons, the template defines the Compare method. This method works like the strcmp function from the standard C/C++ library. The result returned specifies if a given element precedes (>0), is the same (0) or is after (<0) another element. By default, the method uses the Compare method of the C class to make the comparisons:
This method is virtual and can be re-implemented for specific needs.
Here is a simple example:
- Warning
- This implementation is slower than the qsort method of the C/C++ library. It is therefore only useful, if the comparison method between two elements cannot not be implemented as a static method of the class C.
Constructor & Destructor Documentation
RQuickSort | ( | C ** | tab = 0 , |
size_t | max = 0 |
||
) |
Constructor of the algorithm.
- Parameters
-
tab Array to sort. max Number of elements in the array.
RQuickSort | ( | iRContainer< C > & | cont | ) |
Constructor of the algorithm.
- Parameters
-
cont Container to sort.
|
virtual |
Destructor.
Member Function Documentation
|
privatevirtual |
Compare method that should work like the strcmp function of the C library. By default, it calls the Compare method of C, but it can be override.
- Parameters
-
obj1 First object to compare with. obj2 Second object to compare with.
- Returns
- a number depending if obj1 must be sorted before obj2 (<0), obj1 and obj2 are equal (==0) or obj1 must be sorted after obj2 (>0).
|
private |
Manage a partition.
- Parameters
-
left First element. right Last element. pivotIndex Index of the pivot.
- Returns
- Index of the last element sorted before the pivot.
|
private |
Do a quicksort.
- Parameters
-
left First element. right Second element.
void Order | ( | void | ) |
Order the current array.
void Order | ( | C ** | tab, |
size_t | max | ||
) |
Order an array.
- Parameters
-
tab Array to sort. max Number of elements in the array.
Field Documentation
|
private |
The array to sort.
|
private |
The number of elements in the array.