import java.io.*;
import java.util.*;
//-------------------------------------------------------------------
// This program implements 4 sorting algorithms : bubble,
// insertion, selection and quick. It counts the number of
// loops, number of comparisons, number of swaps each of
// these algorithms perform on input with different properties
// (sorted, inverse sorted, and random).
//
// The class hierarchy are as follows :
// - SortMain - the class with the main() method
// - Sorter // abstract sorting class, for sorting.
// +- BubbleSorter // implments bubble sort
// +- QuickSorter // implments quick sort
// +- InsertionSorter // implments insertion sort
// +- SelectionSorter // implments selection sort
// - TestGenerator - abstract class for generating test arrays.
// +- RandomGenerator // generates a random array
// +- SortedGenerator // generates a sorted array
// +- InverseSortedGenerator // generates an inverse sorted array.
//
// TODO : Add more comments to the sort implementations.
//--------------------------------------------------------------------
public class SortMain
{
// The size of the array to sort. Modify this value to change the
// lenght of the array.
final static int DATA_SIZE = 100;
public static void main(String[] args) throws IOException
{
// An array of array generators. If you want to add a new type
// of array, simple add the generator here.
TestGenerator gen[] = {
new RandomGenerator(0),
new SortedGenerator(0),
new InverseSortedGenerator(0)
};
// An array of Sorter. If you want to add a new sorting algorithm,
// simply add the sorter here.
Sorter sorter[] = {
new QuickSorter (),
new InsertionSorter (),
new SelectionSorter (),
new BubbleSorter ()
};
// Loop through all generator, and all sorting algorithm, and
// print out the statistics.
System.out.println("Array Length : " + DATA_SIZE + "\n");
for (int i = 0; i < gen.length; i++)
{
for (int j = 0; j < sorter.length; j++)
{
sorter[j].init(gen[i].generate(DATA_SIZE));
sorter[j].sort();
System.out.println(sorter[j].describe() + "\t" +
gen[i].describe() + "\t" + sorter[j].stats());
}
System.out.println();
}
System.in.read();
}
}
//----------------------------------------------------------
// Sorter
//
// An abstraction that contains an array. We can sort the
// array. There is a toString function that can print out
// the elements in the array. We also keep tracks of the
// number of comparison, number of exchanges, and number of
// loops. These statistic can be accessed by the stats()
// method.
//----------------------------------------------------------
abstract class Sorter
{
int b[];
int numOfComparisons;
int numOfLoops;
int numOfExchanges;
String description; // name of this sorting algorithm
//------------------------------------------------------
// Constructor for Sorter
// This constructor takes in a description that describe
// this sorting method.
//------------------------------------------------------
public Sorter(String description)
{
this.description = new String(description);
}
//------------------------------------------------------
// init()
//
// input : an array of integer.
// Initialized the sorter with an array to be sorted.
//------------------------------------------------------
public void init(int b[])
{
numOfComparisons = 0;
numOfLoops = 0;
numOfExchanges = 0;
// make a copy of the array.
this.b = new int[b.length];
for (int i = 0; i < b.length; i++)
{
this.b[i] = b[i];
}
}
//------------------------------------------------------
// describe()
//
// Return the description of this Sorter.
//------------------------------------------------------
public String describe()
{
return description;
}
//------------------------------------------------------
// stats()
//
// Return the stats of this sorter as a string.
//------------------------------------------------------
public String stats()
{
return numOfComparisons + "\t" + numOfLoops + "\t"
+ numOfExchanges;
}
//------------------------------------------------------
// toString()
//
// Return the elements of this array as a string.
//------------------------------------------------------
public String toString()
{
String n = "";
for (int i = 0; i < b.length; i++)
{
n = n + b[i] + "\t";
}
return n;
}
//------------------------------------------------------
// swap()
//
// input : two indices of array b : i, j
// Swap the element b[i] and b[j] in the array b.
//------------------------------------------------------
protected void swap(int i, int j)
{
int temp = b[i];
b[i] = b[j];
b[j] = temp;
}
abstract public void sort();
}
//-----------------------------------------------
// BubbleSorter
//
// This subclass of Sorter implements the sort
// method using BubbleSort.
//-----------------------------------------------
class BubbleSorter extends Sorter
{
public BubbleSorter()
{
super("Bubble Sort");
}
public void sort()
{
for (int i = 0; i < b.length; i++)
{
for (int j = 0; j < b.length - 1 - i; j++)
{
numOfLoops++;
numOfComparisons++;
if (b[j] > b[j+1])
{
numOfExchanges++;
// swap b[j] and b[j+1]
swap(i, j);
}
}
}
}
}
//-----------------------------------------------
// SelectionSorter
//
// This subclass of Sorter implements the sort
// method using selection sort.
//-----------------------------------------------
class SelectionSorter extends Sorter
{
public SelectionSorter()
{
super("Selection Sort");
}
public void sort()
{
for (int k = 0; k < b.length-1; k++)
{
// Find min so that b[min] is the minimum of b[k..b.length-1]
int min = k;
for (int h = k+1; h < b.length; h++)
{
numOfLoops++;
numOfComparisons++;
if (b[h] < b[min])
min = h;
}
numOfExchanges++;
// Swap b[k] with b[min]
swap(k, min);
}
}
}
//-----------------------------------------------
// InsertionSorter
//
// This subclass of Sorter implements the sort
// method using insertion sort.
//-----------------------------------------------
class InsertionSorter extends Sorter
{
public InsertionSorter()
{
super("Insertion Sort");
}
public void sort()
{
for (int k= 0; k < b.length; k++)
{
// Place b[k] in its sorted position in b[0..k]
int temp = b[k]; //Save b[k] in temp
int h = k;
// Inv: b[0..k] is sorted except for position b[h], temp <= b[h+1..k]
numOfExchanges++;
numOfComparisons++;
for (h = k; (h != 0) && b[h-1]>=temp; h--)
{
numOfComparisons++;
numOfLoops++;
numOfExchanges++;
b[h]= b[h-1];
}
// Note: {b[0..h-1] <= temp <= b[h+1..k]}
b[h] = temp;
}
}
}
//-----------------------------------------------
// QuickSorter
//
// This subclass of Sorter implements the sort
// method using quick sort.
//-----------------------------------------------
class QuickSorter extends Sorter
{
//------------------------------------------------------
// The class SubTask encapsulates a sub-array that we
// want to sort. It simply contains the indices of the
// first element and the last element of this sub-array.
//------------------------------------------------------
class SubTask
{
int first;
int last;
public SubTask(int first, int last)
{
this.first = first;
this.last = last;
}
}
public QuickSorter()
{
super("Quick Sort");
}
public int partition (int first, int last)
{
int pivot = b[first];
int i = first;
int j = last;
while (i <= j)
{
numOfLoops++;
numOfComparisons++;
if (b[i] <= pivot)
{
i++;
}
else
{
numOfComparisons++;
if (b[j] > pivot)
j--;
else
{
numOfExchanges++;
//Swap b[i] and b[j]
swap(i, j);
}
}
}
numOfExchanges++;
swap(first, j);
return j;
}
public void quickSort(int first, int last)
{
SubTask c[] = new SubTask[last + 1 - first];
c[0] = new SubTask(first, last);
int i = 1;
while ( i > 0 )
{
numOfLoops++;
i--;
int f = c[i].first;
int l = c[i].last;
if (l - f == 1)
{
numOfComparisons++;
if (b[f] > b[l])
{
numOfExchanges++;
swap(f, l);
}
}
else if (l - f > 1)
{
int j = partition(f, l);
c[i++] = new SubTask(f, j - 1);
c[i++] = new SubTask(j+1, l);
}
}
}
public void sort()
{
quickSort(0, b.length - 1);
}
}
//------------------------------------------------------
// TestGenerator
//
// This class encapsulates a test generator that can
// generate an array of random numbers with a certain
// properties. The concrete subclass of TestGenerator
// should implement the function generate() that
// generate an array.
//------------------------------------------------------
abstract class TestGenerator
{
Random r;
String description;
public TestGenerator(int seed, String description)
{
this.description = new String(description);
r = new Random(seed);
}
public String describe()
{
return description;
}
public abstract int [] generate(int numOfElem);
}
//------------------------------------------------------
// RandomGenerator
//
// This subclass of TestGenerator generates an array
// of random numbers, between -999 and 999.
//------------------------------------------------------
class RandomGenerator extends TestGenerator
{
public RandomGenerator(int seed)
{
super(seed, "Random ");
}
public int [] generate(int numOfElem)
{
int b[] = new int[numOfElem];
for (int i = 0; i < numOfElem; i++)
{
b[i] = r.nextInt()%1000;
}
return b;
}
}
//------------------------------------------------------
// SortedGenerator
//
// This subclass of TestGenerator generates an array
// that are sorted in increasing order.
//------------------------------------------------------
class SortedGenerator extends TestGenerator
{
public SortedGenerator(int seed)
{
super(seed, "Sorted ");
}
public int [] generate(int numOfElem)
{
int b[] = new int[numOfElem];
b[0] = r.nextInt()%1000;
for (int i = 1; i < numOfElem; i++)
{
int delta = r.nextInt()%10;
// make sure that the increment is positive.
if (delta < 0)
delta = -delta;
b[i] = b[i-1] + delta;
}
return b;
}
}
//------------------------------------------------------
// InverseSortedGenerator
//
// This subclass of TestGenerator generates an array
// that are sorted in decreasing order.
//------------------------------------------------------
class InverseSortedGenerator extends TestGenerator
{
public InverseSortedGenerator(int seed)
{
super(seed, "InvSorted");
}
public int [] generate(int numOfElem)
{
int b[] = new int[numOfElem];
b[0] = r.nextInt()%1000;
for (int i = 1; i < numOfElem; i++)
{
int delta = r.nextInt()%10;
// make sure that the increment is positive.
if (delta < 0)
delta = -delta;
b[i] = b[i-1] - delta;
}
return b;
}
}