Reputation: 7285
I have the code below that I have found. I am trying to learn which sorting method is the fastest and which ones use the most and least comparisons. Anyone have any idea how I can add some code in here to do that? I want to tally the total number of comparisons of each sort.
//***********************************************************************************
// Sorting.java
//
// Contains various sort algorithms that operate on an array of comparable objects.
//
//************************************************************************************
public class Sorting
{
//------------------------------------------------------------------------------------
// Sorts the specified array of integers using the selection sort algorithm.
//------------------------------------------------------------------------------------
public static void selectionSort (Comparable[] data)
{
int min;
for (int index = 0; index < data.length-1; index ++)
{
min = index;
for (int scan = index+1; scan < data.length; scan++)
if (data[scan].compareTo(data[min]) < 0)
min = scan;
swap (data, min, index);
}
}
//---------------------------------------------------------------------------------------
// Swaps to elements in the specified array.
//---------------------------------------------------------------------------------------
private static void swap (Comparable[] data, int index1, int index2)
{
Comparable temp = data[index1];
data[index1] = data[index2];
data[index2] = temp;
}
//---------------------------------------------------------------------------------------
// Sorts the specified array of objects using an insertion sort algorithm.
//---------------------------------------------------------------------------------------
public static void insertionSort (Comparable[] data)
{
for (int index = 1; index < data.length; index++)
{
Comparable key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position-1].compareTo(key) > 0)
{
data[position] = data[position-1];
position--;
}
data[position] = key;
}
}
//---------------------------------------------------------------------------------------
// Sorts the specified array of objects using a bubble sort algorithm.
//---------------------------------------------------------------------------------------
public static void bubbleSort (Comparable[] data)
{
int position, scan;
for (position = data.length - 1; position >= 0; position--)
{
for (scan = 0; scan <= position - 1; scan ++)
if (data[scan].compareTo(data[scan+1]) >0)
swap (data, scan, scan+1);
}
}
//---------------------------------------------------------------------------------------
// Sorts the specified array of objects using the quick sort algorithm.
//---------------------------------------------------------------------------------------
public static void quickSort (Comparable[] data, int min, int max)
{
int pivot;
if (min < max)
{
pivot = partition (data, min, max); // make partitions
quickSort(data, min, pivot-1); //sort left paritions
quickSort(data, pivot+1, max); //sort right paritions
}
}
//---------------------------------------------------------------------------------------
// Creates the partitions needed for quick sort.
//---------------------------------------------------------------------------------------
public static int partition (Comparable[] data, int min, int max)
{
//Use first element as the partition value
Comparable partitionValue = data[min];
int left = min;
int right = max;
while (left < right)
{
// Search for an element that is greater than the partition element
while (data[left].compareTo(partitionValue) <= 0 && left < right)
left++;
// Search for an element that is less than the partition element
while (data[right].compareTo(partitionValue) > 0)
right--;
if (left < right)
swap (data, left, right);
}
// Move the partition element to its final position
swap (data, min, right);
return right;
}
//---------------------------------------------------------------------------------------
// Sorts the specified array of objects using the merge sort algorithm.
//---------------------------------------------------------------------------------------
public static void mergeSort (Comparable[] data, int min, int max)
{
if (min < max)
{
int mid = (min + max) / 2;
mergeSort(data, min, mid);
mergeSort(data, mid+1, max);
merge (data, min, mid, max);
}
}
//---------------------------------------------------------------------------------------
// Sorts the specified array of objects using the merge sort algorithm.
//---------------------------------------------------------------------------------------
public static void merge (Comparable[] data, int first, int mid, int last)
{
Comparable[] temp = new Comparable[data.length];
int first1 = first, last1 = mid; //endpoints of first subarray
int first2 = mid + 1, last2 = last; //endpoints of second subarray
int index = first1; // next index open in temp array
// Copy smaller item from each subarry into temp until one of the subarrays is exhausted
while (first1 <= last1 && first2 <= last2)
{
if (data[first1].compareTo(data[first2]) < 0)
{
temp[index] = data[first1];
first1++;
}
else
{
temp[index] = data[first2];
first2++;
}
index++;
}
// Copy remaining elements from first subarray, if any
while (first1 <= last1)
{
temp[index] = data[first1];
first1++;
index++;
}
// Copy remaining elements from second subarray, if any
while (first2 <= last2)
{
temp[index] = data[first2];
first2++;
index++;
}
// Copy merged data into original array
for (index = first; index <= last; index++)
data[index] = temp[index];
}
}
Upvotes: 0
Views: 337
Reputation: 41686
You should define an abstract class that implements the counting, and then some derived classes that implement the algorithms. The main program would look like this:
List<String> list = new ArrayList<String>();
// TODO: add some elements to the list
SortingAlgorithm alg = new BubbleSort();
alg.sort(list);
alg.printSummary();
Now the abstract class that implements the counting:
public abstract class SortingAlgorithm<T> {
/* the actual algorithm, which uses the compare and swap methods. */
public abstract void sort(List<T> list);
private long compares = 0;
private long swaps = 0;
protected int compare(T a, T b) {
compares++;
return a.compareTo(b);
}
protected void swap(int index1, int index2) {
swaps++;
// TODO: do the actual swapping
}
public void printSummary() {
// TODO
}
}
The concrete algorithms now only have to implement the sort
method. How to do this is left as an excercise for the reader.
Upvotes: 1
Reputation: 8211
Rather learn about O-notation from a good book like:
http://www.amazon.com/Data-Structures-Algorithms-Java-2nd/dp/0672324539
Upvotes: 1
Reputation: 3658
If you're interested in speed, use Arrays.sort(). If you're academically interested in what's involved in various sorting techniques, it's probably faster to just look at Wikipedia. If you want us to do your homework for you...we won't, sorry.
Edit: I guess it's fair for me to say this: Is there any reason you couldn't just initialize an integer to 0 at the start of each method, increment it every time something interesting happened, and then print it at the end?
Upvotes: 5