Back to index

lightning-sunbird  0.9+nobinonly
Classes | Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes
QuickSort Class Reference
Collaboration diagram for QuickSort:
Collaboration graph
[legend]

List of all members.

Classes

class  Comparator

Public Member Functions

 QuickSort (Comparator comparator)
void sort (Object[] a)
void sort (Object[] a, int length)

Private Member Functions

void qsort (Object[] a, int lo0, int hi0)
 This is a generic version of C.A.R Hoare's Quick Sort algorithm.

Static Private Member Functions

static void swap (Object[] a, int i, int j)

Private Attributes

Comparator mComparator

Detailed Description

Definition at line 1 of file QuickSort.java.


Constructor & Destructor Documentation

QuickSort.QuickSort ( Comparator  comparator) [inline]

Definition at line 8 of file QuickSort.java.

                                               {
              mComparator = comparator;
       }

Member Function Documentation

void QuickSort.qsort ( Object[]  a,
int  lo0,
int  hi0 
) [inline, private]

This is a generic version of C.A.R Hoare's Quick Sort algorithm.

This will handle arrays that are already sorted, and arrays with duplicate keys.

If you think of a one dimensional array as going from the lowest index on the left to the highest index on the right then the parameters to this function are lowest index or left and highest index or right. The first time you call this function it will be with the parameters 0, a.length - 1.

Parameters:
aan Object array
lo0left boundary of array partition
hi0right boundary of array partition

Definition at line 26 of file QuickSort.java.

                                                        {
              int lo = lo0;
              int hi = hi0;

              if ( hi0 > lo0) {
                     /* Arbitrarily establishing partition element as the midpoint of
                     * the array.
                     */
                     Object mid = a[ ( lo0 + hi0 ) / 2 ];

                     // loop through the array until indices cross
                     while ( lo <= hi ) {
                            /* find the first element that is greater than or equal to 
                            * the partition element starting from the left Index.
                            */
                            while (( lo < hi0 ) && ( mComparator.compare(a[lo], mid) < 0 ))
                                   ++lo;

                            /* find an element that is smaller than or equal to 
                            * the partition element starting from the right Index.
                            */
                            while (( hi > lo0 ) && ( mComparator.compare(a[hi], mid) > 0 ))
                                   --hi;

                            // if the indexes have not crossed, swap
                            if ( lo <= hi ) {
                                   swap(a, lo, hi);

                                   ++lo;
                                   --hi;
                            }
                     }

                     /* If the right index has not reached the left side of array
                     * must now sort the left partition.
                     */
                     if ( lo0 < hi )
                            qsort( a, lo0, hi );

                     /* If the left index has not reached the right side of array
                     * must now sort the right partition.
                     */
                     if ( lo < hi0 )
                            qsort( a, lo, hi0 );
              }
       }

Here is the call graph for this function:

Here is the caller graph for this function:

void QuickSort.sort ( Object[]  a) [inline]

Definition at line 79 of file QuickSort.java.

                                    {
              qsort(a, 0, a.length - 1);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

void QuickSort.sort ( Object[]  a,
int  length 
) [inline]

Definition at line 83 of file QuickSort.java.

                                                {
              qsort(a, 0, length - 1);
       }

Here is the call graph for this function:

static void QuickSort.swap ( Object[]  a,
int  i,
int  j 
) [inline, static, private]

Definition at line 73 of file QuickSort.java.

                                                          {
              Object temp = a[i]; 
              a[i] = a[j];
              a[j] = temp;
       }

Here is the caller graph for this function:


Member Data Documentation

Definition at line 6 of file QuickSort.java.


The documentation for this class was generated from the following file: