net.sf.jsort.sort
Class RandomizedQuickSort

java.lang.Object
  net.sf.jsort.sort.AbstractSort
      net.sf.jsort.sort.QuickSort
          net.sf.jsort.sort.RandomizedQuickSort

All Implemented Interfaces:

CompareSort, SortAlgorithm

public final class RandomizedQuickSort
extends QuickSort

This is a alternative implementation of QuickSort, that tries to eliminate the poor performance (n ^2) in worst case of QuickSort.

The worst case is eliminated by random selection of the pivot in partition method of quicksort algorithm.

Author:

Domingos Creado

Constructor Summary

RandomizedQuickSort()

Method Summary

protected int

partition(java.lang.Object[] list, java.util.Comparator comparator, int start, int end) This implementation of partion uses a random generator to select the pivot, interchange it with the last element and call the original partition method of quicksort.

Methods inherited from class net.sf.jsort.sort.QuickSort

sort

Methods inherited from class net.sf.jsort.sort.AbstractSort

sort, sort, sort, sort, sort, sort, sort

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RandomizedQuickSort

public RandomizedQuickSort()

Method Detail

partition

protected int partition(java.lang.Object[] list,
                        java.util.Comparator comparator,
                        int start,
                        int end)

This implementation of partion uses a random generator to select the pivot, interchange it with the last element and call the original partition method of quicksort.

Overrides:

partition in class QuickSort

Parameters:

list - the elements to be ordered

comparator - the element that define what is "greater than" semantics

start - first position of the list to be included in sorting

end - last position of the list to be included in sorting

Returns:

the position of the pivot