Heap Sort in Java

Heap sort uses a binary heap, which is a complete binary tree. A binary tree is a hierarchical structure. It either is empty or consists of an element, called the root, and two distinct binary trees, called the left subtree and right subtree. The length of a path is the number of the edges in the path. The depth of a node is the length of the path from the root to the node.

A heap is a binary tree with the following properties:
  • It is a complete binary tree.
  • Each node is greater than or equal to any of its children.

Complete Binary Tree

A binary tree is complete if each of its levels is full, except that the last level may not be full and all the leaves on the last level are placed leftmost. For example, in below Figure, the binary trees in (a) and (b) are complete, but the binary trees in (c) and (d) are not complete. Further, the binary tree in (a) is a heap, but the binary tree in (b) is not a heap, because the root (39) is less than its right child (42).

Binary Tree Illustration



To sort an array using a heap, first create an object using the Heap class, add all the elements to the heap using the add method, and remove all the elements from the heap using the remove method. The elements are removed in descending order. Below code Listing gives an algorithm for sorting an array using a heap.

Heap.java


      

    public class Heap<E extends Comparable> {

       private ArrayList<E> list = new ArrayList<E>();
      
       /** Create a default heap */
       public Heap() {
    }
      
   /** Create a heap from an array of objects */
   public Heap(E[] objects) {
        for (int i = 0; i < objects.length; i++)
                     add(objects[i]);
   }
      
   /** Add a new object into the heap */
   public void add(E newObject) {
          list.add(newObject); // Append to the heap
      int currentIndex = list.size() - 1; // The index of the last node
      
      while (currentIndex > 0) {
              int parentIndex = (currentIndex - 1) / 2;
              // Swap if the current object is greater than its parent
       if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0) {
              E temp = list.get(currentIndex);
              list.set(currentIndex, list.get(parentIndex));
              list.set(parentIndex, temp);
       } else
              break; // The tree is a heap now
      
                     currentIndex = parentIndex;
              }
       }
      
       /** Remove the root from the heap */
       public E remove() {
              if (list.size() == 0)
                     return null;
      
              E removedObject = list.get(0);
              list.set(0, list.get(list.size() - 1));
              list.remove(list.size() - 1);
      
              int currentIndex = 0;
              while (currentIndex < list.size()) {
                     int leftChildIndex = 2 * currentIndex + 1;
                     int rightChildIndex = 2 * currentIndex + 2;
      
                     // Find the maximum between two children
       if (leftChildIndex >= list.size())
              break; // The tree is a heap
       int maxIndex = leftChildIndex;
       if (rightChildIndex < list.size()) {
              if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0) {
                     maxIndex = rightChildIndex;
              }
       }
      
       // Swap if the current node is less than the maximum
       if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
              E temp = list.get(maxIndex);
              list.set(maxIndex, list.get(currentIndex));
              list.set(currentIndex, temp);
              currentIndex = maxIndex;
       } else
              break; // The tree is a heap
              }
      
              return removedObject;
       }
      
       /** Get the number of nodes in the tree */
              public int getSize() {
                     return list.size();
              }
       }


  HeapSort.java




public class HeapSort {
   /** Heap sort method */
   public static <E extends Comparable> void heapSort(E[] list) {
       // Create a Heap of integers
       Heap<E> heap = new Heap<E>();

       // Add elements to the heap
       for (int i = 0; i < list.length; i++)
              heap.add(list[i]);

       // Remove elements from the heap
       for (int i = list.length - 1; i >= 0; i--)
              list[i] = heap.remove();
}

/** A test method */
public static void main(String[] args) {
       Integer[] list = { 2, 3, 2, 5, 6, 1, -2, 3, 14, 12 };
       heapSort(list);
       for (int i = 0; i < list.length; i++)
              System.out.print(list[i] + " ");
       }
}


When you run this Code listing it will produce output like:

    -2 1 2 2 3 3 5 6 12 14

Reference(s): Introduction to JAVA by Y. Daniel Liang

Quick Sort in Java

Quick Sort is a divide and conquer algorithm which was developed by Tony Hoare in 1960.

Quick Sort first divides a large list into two smaller sub-lists: the low elements and the high elements and then recursively sort the sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.


Below Figure illustrates how to sort an array (5 2 9 3 8 4 0 1 6 7) using quick sort. Choose the first element 5 as the pivot. The array is partitioned into two parts, as shown in Figure (b). The highlighted pivot is placed in the right place in the array. Apply quick sort on two partial arrays (4 2 1 3 0) and then (8 9 6 7). The pivot 4 partitions (4 2 1 3 0) into just one partial array (0 2 1 3), as shown in Figure (c). Apply quick sort on (0 2 1 3). The pivot 0 partitions it to just one partial array (2 1 3), as shown in Figure (d). Apply quick sort on (2 1 3). The pivot 2 partitions it to (1) and (3), as shown in Figure (e). Apply quick sort on (1). Since the array contains just one element, no further partition is needed. 


Quick Sort Illustration

The quick sort algorithm is implemented in below code Listing. There are two overloaded quickSort methods in the class. The first method is used to sort an array. The second is a helper method that sorts a partial array with a specified range.

QuickSort.java


public class QuickSort {

       public static void quickSort(int[] list) {
              quickSort(list, 0, list.length - 1);
       }

       private static void quickSort(int[] list, int first, int last) {
              if (last > first) {
                     int pivotIndex = partition(list, first, last);
                     quickSort(list, first, pivotIndex - 1);
                     quickSort(list, pivotIndex + 1, last);
              }
       }

       /** Partition the array list[first..last] */
       private static int partition(int[] list, int first, int last) {
           int pivot = list[first]; // Choose the first element as the pivot
           int low = first + 1; // Index for forward search
           int high = last; // Index for backward search

           while (high > low) {
                     // Search forward from left
                     while (low <= high && list[low] <= pivot)
                           low++;

                     // Search backward from right
                     while (low <= high && list[high] > pivot)
                           high--;

                     // Swap two elements in the list
                     if (high > low) {
                           int temp = list[high];
                           list[high] = list[low];
                           list[low] = temp;
                     }
             }

             while (high > first && list[high] >= pivot)
                     high--;

              // Swap pivot with list[high]
              if (pivot > list[high]) {
                     list[first] = list[high];
                     list[high] = pivot;
                     return high;
              } else {
                     return first;
              }
       }

       /** A test method */
       public static void main(String[] args) {
              int[] list = { 5, 2, 9, 3, 8, 4, 0, 1, 6, 7 };
              quickSort(list);
              for (int i = 0; i < list.length; i++)
                     System.out.print(list[i] + " ");
       }
}
  

The output of this program is:
   0 1 2 3 4 5 6 7 8 9


Reference(s): 
http://en.wikipedia.org/wiki/Quicksort
Introduction to JAVA by Y. Daniel Liang