Introsort

From CodeCodex

Related content:

Implementations[edit]

Below are implementations of Introsort (also called introspective sort) which is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on the number of elements being sorted.

Java[edit]

B1 Algorithm to create median-of-3 killer sequences

 private static Sortable [] createMedianOf3KillerArray ( int length )
{
    if (( length %2)==1)
        return null;
    int k= length /2;
    Sortable [] a = new Sortable [ length ];
    for (int i=1; i<=k; i++)
    {
        if ((i \%2) == 1)
        {
            a[i -1] = new SortableInteger (i);
            a[i] = new SortableInteger (k+i);
        }
        a[k+i -1] = new SortableInteger (2*i);
    }
    return a;
}

B2 The class Introsort The Introsort Java class.

public class Introsort implements Sorter
{
    /*
     * Class Variables
     */
    private static Sortable[] a;
    private static int size_threshold = 16;

    /*
     * Public interface
     */
    public void sort(Sortable[] a0)
    {
        a=a0;
        introsort_loop(0, a.length, 2*floor_lg(a.length));
        insertionsort(0, a.length);
    }

    public void sort(Sortable[] a0, int begin, int end)
    {
    	if (begin < end)
    	{
	    a=a0;
	    introsort_loop(begin, end, 2*floor_lg(end-begin));
	    insertionsort(begin, end);
    	}
    }

    /*
     * Quicksort algorithm modified for Introsort
     */
    private static void introsort_loop (int lo, int hi, int depth_limit)
    {
    	while (hi-lo > size_threshold)
    	{
    	    if (depth_limit == 0)
    	    {
    	        heapsort(lo, hi);
    		return;
    	    }
    	    depth_limit=depth_limit-1;
	    int p=partition(lo, hi, medianof3(lo, lo+((hi-lo)/2)+1, hi-1));
	    introsort_loop(p, hi, depth_limit);
	    hi=p;
    	}
    }

    private static int partition(int lo, int hi, Sortable x)
    {
    	int i=lo, j=hi;
    	while (true)
    	{
    	    while (a[i].smaller(x)) i++;
    	    j=j-1;
    	    while (x.smaller(a[j])) j=j-1;
    	    if(!(i < j))
    		return i;
    	    exchange(i,j);
    	    i++;
    	}
    }

    private static Sortable medianof3(int lo, int mid, int hi)
    {
        if (a[mid].smaller(a[lo]))
        {
            if (a[hi].smaller(a[mid]))
                return a[mid];
            else
            {
                if (a[hi].smaller(a[lo]))
		    return a[hi];
		else
		    return a[lo];
            }
        }
	else
	{
            if (a[hi].smaller(a[mid]))
            {
                if (a[hi].smaller(a[lo]))
		    return a[lo];
		else
		    return a[hi];
            }
            else
                    return a[mid];
	}
    }

    /*
     * Heapsort algorithm
     */
    private static void heapsort(int lo, int hi)
    {
        int n = hi-lo;
	for (int i=n/2; i>=1; i=i-1)
	{
	   downheap(i,n,lo);
	}
	for (int i=n; i>1; i=i-1)
	{
	   exchange(lo,lo+i-1);
	   downheap(1,i-1,lo);
	}
    }

    private static void downheap(int i, int n, int lo)
    {
        Sortable d = a[lo+i-1];
        int child;
        while (i<=n/2)
	{
	   child = 2*i;
	   if (child < n && a[lo+child-1].smaller(a[lo+child]))
	   {
	       child++;
	   }
	   if (!d.smaller(a[lo+child-1])) break;
	   a[lo+i-1] = a[lo+child-1];
	   i = child;
	}
	a[lo+i-1] = d;
    }

    /*
     * Insertion sort algorithm
     */
    private static void insertionsort(int lo, int hi)
    {
	int i,j;
	Sortable t;
	for (i=lo; i < hi; i++)
	{
            j=i;
	    t = a[i];
	    while(j!=lo && t.smaller(a[j-1]))
	    {
	        a[j] = a[j-1];
		j--;
	    }
	    a[j] = t;
	}
    }

    /*
     * Common methods for all algorithms
     */
    private static void exchange(int i, int j)
    {
        Sortable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    private int floor_lg(int a)
    {
        return (int)(Math.floor(Math.log(a)/Math.log(2)));
    }
}

B3 Implemented interfaces Introsort implements this interface:

public interface Sorter
{
    void sort (Sortable [] f, int from , int to);
    /**
     * Ascendingly sorts the array from from to to,
     * where from is included and to is not.
     **/
    void sort (Sortable [] f);
}

All variables used in the sorted arry need to implement this interface:

public interface Sortable
{
    boolean smaller ( Sortable ob );
}

Ruby[edit]

Ruby implementation with simple test

#!/usr/bin/env ruby
#
# Introsort is a version of Quicksort with "introspection".
#
# When Introsort notices that its recursion depth exceeds
# a specified height, it switches over to Heapsort to
# process the (Quicksort) partition it is currently working on.
# In this way the recursion depth does not continue to increase
# as it would with Quicksort. Unconstrained recursion can reduce
# Quicksort's performance to O(n^2), whereas on the same data,
# Introsort guarantees a worst-case performance of O(n*log2(n)).
#
# This version of Introsort switches to Heapsort when its 
# recursion depth reaches 2*(floor(log2(n))).
# See Musser, David (1997). "Introspective Sorting and Selection Algorithms".
# Software: Practice and Experience 27 (8): 983?993. Wiley.
#
# The algorithm for Heapsort is adapted from 
# Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001).
# Introduction to Algorithms, second edition, MIT Press and McGraw-Hill.
#
class Heapsort
  def initialize(ary)
    @ary = ary.dup
    @heap_size = ary.length
  end
  def heapsort
   build_max_heap
   @ary.length.downto(2) {|i|
     swap(1, i) 
     @heap_size -= 1   
     max_heapify(1)
   }
   @ary
  end 
  def build_max_heap
    parent(@heap_size).downto(1) {|i|
      max_heapify(i)
    }
  end
  def max_heapify(i)
    l = left(i)  
    r = right(i)
    largest = (l <= @heap_size and @ary[l-1] > @ary[i-1]) ? l : i
    largest = r if (r <= @heap_size and @ary[r-1] > @ary[largest-1])
    if largest != i
      swap(i, largest)
      max_heapify(largest)
    end
  end 
  def parent(i)
    (i / 2).floor
  end
  def left(i)
    2 * i
  end
  def right(i)
    (2 * i) + 1
  end 
  def swap(i, j)
    @ary[i-1], @ary[j-1] = @ary[j-1], @ary[i-1]
  end
end
def introloop(ary, depth_limit)
  return ary if ary.size <= 1
  return Heapsort.new(ary).heapsort() if depth_limit == 0
  depth_limit -= 1
  pivot = ary.pop
  left, right = ary.partition { |e| e < pivot }
  introloop(left, depth_limit) + [pivot] + introloop(right, depth_limit)
end
def introsort(ary)
  introloop(ary, 2 * (Math.log10(ary.size) / Math.log10(2)).floor)
end 
if $0 == __FILE__
  print introsort([1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1]).join(", ") + "\n"
  # prints: 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7 without calling heapsort
  print introsort([13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]).join(", ") + "\n"
  # prints: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
  # and calls heapsort once for subarray [13, 12, 11, 10, 9, 8, 7]
end