CloudTMP

Well, in this post I will share with you 17 Java Sorting implementations I had to code in an algorithms course at college ! The package includes the following implementations (from the easiest to the more complex ones).

• Bubble Sort (SorterType.BUBBLE)
• Selection Sort (SorterType.SELECTION)
• Insertion Sort (SorterType.INSERTION)
• HSort (SorterType.H)
• Shell Sort (SorterType.SHELL)
• Quick Sort (SorterType.QUICK)
• Quick “Cut” Sort (SorterType.QUICK_CUT)
• Quick “Median of Three” Sort (SorterType.QUICK_MED_OF_THREE)
• Quick “Non recursive” Sort (SorterType.QUICK_NON_RECURSIVE)
• Quick “Three way Partition” Sort (SorterType.QUICK_THREE_PARTITION)
• Bottom-Up Merge Sort (SorterType.MERGE_BOTTOM_UP)
• Bottom-Up Linked-List Merge Sort
• Top-Down Merge Sort (SorterType.MERGE)
• Top-Down Linked-List Merge Sort
• Binary Heap Sort (SorterType.HEAP_BINARY)
• Ternary Heap Sort (SorterType.HEAP_TERNARY)

All implementations come with a brief explanation for you to understand the basic idea of how the algorithm sorts the elements !

API

All Sorting implementations extends AbstractSorter which implements Sorter. The Sorter interface is generified. This allows subsequent implementations to be capable to sort any collection of objects as long as exists a Comparator for that Type of objects.

public interface Sorter {

<T> void sort(Comparator<T> comparator, List<T> list) ;

SorterType getType();

}

public abstract class AbstractSorter implements Sorter { ... }

Implementations:

public class InsertionSorter extends AbstractSorter { ... }

How to use?

• Get a DataGenerator instance:

DataSetGenerator<Integer> dataGenerator = new IntegerDataSetGenerator();

• Get a SorterProvider instance:

SorterProvider sorterProvider = new SorterProvider();

• Create a random list and sort it using QuickSort:

List<Integer> randomList = dataGenerator.createRandom(1000);
Sorter quickSort = sorterProvider.getSorterForType(SorterType.QUICK);
quickSort.sort(dataGenerator.getComparator(), randomList);

• Create a descending list and sort it using SelectionSort:

List<Integer> descendingList = dataGenerator.createDescending(1000);
Sorter selectionSort = sorterProvider.getSorterForType(SorterType.SELECTION);
selectionSort.sort(dataGenerator.getComparator(), descendingList);

• It isn’t a must to create a DataGenerator instance but at some point you will have to implement a java.util.Comparator.

public class StringComparator implements Comparator<String>  {

@Override
public int compare(String s1, String s2) {
return s1.compareTo(s2);
}

}

String[] names = new String[]{"Mery", "Paul", "Bruce"};
Sorter mergeSort = sorterProvider.getSorterForType(SorterType.MERGE);
mergeSort.sort(new StringComparator(), Arrays.asList(names));

• It also isn’t a must to instance a SorterProvider. You can directly instance the Sorter implementation.

String[] surnames = new String[]{"Smith", "Garnil", "Valentino"};
Sorter shellSort = new ShellSorter();
shellSort.sort(new StringComparator(),  Arrays.asList(surnames));

Testing the sorters

You can find a JUnit TestCase named SortersTest.java inside the anaydis.ngarnil.test package. This class tests correctness of the Sorter implementations.

A JUnit JAR (junit.jar) file is included in the lib folder.

public class SortersTest extends TestCase { ... }

I also built an Applet to run the sorters and study their dynamic characteristics.

Download !

Checkout the project from http://javasorting.googlecode.com. Don’t doubt to make questions or post issues, I will answer them as soon as I can.

Direct download: From here!

If you liked this post please vote it in dzone !

Bye !

If you enjoyed this post follow me on twitter or leave a feedback !