Sorting Suite

Download

Includes the following: (User's Guide)

  • Full .java source files and .class compiled source for the entire framework, which includes the sorting algorithm implementations, code for some common java.util.Comparator classes, code for testing each of the algorithms, code for timing each of the algorithms, and windows .bat files for easily invoking the testing and timing code.

  • A user's guide with example code and detailed information about how to use the framework. The user's guide is available online here.

  • Performance analysis for the sorting algorithms. This can be found online here.

  • Implementations for the following sorting algorithms:
    • QuickSort (an implementation one of the fastest average-case performing sorting algorithms)

    • QuickInsertionSort (an optimized quicksort implementation that uses insertion for to sort small sub-lists)

    • QuickSortMedian3 (an implementation of quicksort that uses the median of three approach to find the pivot point)

    • QuickSortRandom (an implementation of quicksort that uses a random number generator to find the pivot point)

    • HeapSort (an implementation of this nlog2n comparison, worst-case sorting algorithm)

    • MergeSort (an implementation of this nlog2n comparison, worst-case sorting algorithm)

    • MergeInsertionSort (an optimized implementation of MergeSort that uses insertion sort to sort small sub-lists)

    • InsertionSort (an implementation of this n2 comparison, worst-case sorting algorithm)

    • InsertionSortBinarySearch (an optimized implementation of InsertionSort that uses binary search to find the insertion position)

    • SelectionSort (an implementation of this n2 comparison, worst-case sorting algorithm)

    • ShellSort (an implementation of this n2 comparison, worst-case sorting algoirthm)

    • BubbleSort (an implementation of this n2 comparison, worst-case sorting algorithm)

    • CombSort (an implementation of this extremely fast BubbleSort variant)


  • Sorting methods to sort the following Java types for each algorithm:
    • java.util.List (can be used to sort the popular java.util.ArrayList)

    • Arrays of the following types:

    • java.lang.Object
    • String
    • int
    • long
    • short
    • double
    • float
    • char
    • byte

  • A testing implementation including the following:
    • A Random Array Generator to generate random test data

    • A command line invoked Java program that can be used to test any of the algorithms for any of the data types for any size of data input

    • A windows batch file that can be run to do a complete test on all algorithms for all data types


  • A timing implementation that includes the following:
    • A command line invoked Java program that can be used to time any of the algorithms for any of the data types for any size of data input

    • A windows batch file that can be run to do a complete timing analysis on all algorithms for all data types for a set of input sizes.

  • In addition to the ability to sort java.util.Lists, the framework offers the following in regards to sorting java.lang.Object arrays:
    • Object array sorting that sorts object arrays based on the value of a method call on the object. This approach uses Reflection to call the method and a java.util.Comparator to do the comparison.

    • Object array sorting that sorts object arrays using a passed in java.util.Comparator

  • A set of common java.util.Comparator classes for use with the methods of the sorting framework that use Reflection. These include the following:
    • IntegerComparator
    • LongComparator
    • ShortComparator
    • DoubleComparator
    • FloatComparator
    • CharacterComparator
    • ByteComparator
    • StringComparator