A while back I had to write a program that would compare different sorting algorithms in Java. The algorithms were Heap Sort, Merge Sort, and Quick Sort. I will leave the analysis up to you, but I will share the algorithms below.
Heap Sort
Constructor takes an unsorted array and sorts the array for you automatically. You can retrieve the sorted array by calling getSortedArray().
public class HeapSort {
private int[] sortedArray; // Sorted Array
private static long COMPARISONS = 0; // Number of comparisons
private static long SWAPS = 0; // Number of swaps
/**
* HeapSort Constructor
*
* @param int[] array
*/
public HeapSort( int[] array ) {
sortedArray = array; // Store param. array in local variable
sort(); // Begin the sort
} // end HeapSort constructor
/**
* This method returns the number of
* comparisons the sorting algorithm
* made.
*
* @return long COMPARISONS
*/
public long getComparisons() {
return COMPARISONS;
} // end method getComparisons()
/**
* This method returns the final
* sorted array.
*
* @return int[] sortedArray
*/
public int[] getSortedArray() {
return sortedArray;
} // end method getSortedArray()
/**
* This method returns the number of
* swaps the sorting algorithm made.
*
* @return long SWAPS
*/
public long getSwaps() {
return SWAPS;
} // end method getSwaps()
/**
* This method heapifies the array.
*
* @param int root
* @param int size
* @param int element
*/
private void heapify( int root, int size, int element ) {
int child = 2 * root; // Left child
/**
* Find the largest child
*/
if ( ( child < size ) && ( sortedArray[child] < sortedArray[child + 1] ) ) {
child++; // Right child is largest
COMPARISONS++; // Increment comparisons
}
/**
* If child is larger than root, swap
* child and root and heapify the
* subtree.
*/
if ( ( child <= size ) && ( element < sortedArray[child] ) ) {
sortedArray[root] = sortedArray[child]; // Move child to root
heapify( child, size, element ); // Heapify subtree
COMPARISONS++; // Increment comparisons
}
/**
* Otherwise, root gets the element
*/
else {
sortedArray[root] = element; // Root gets element
}
} // end method heapify()
/**
* This method initiates the sort
* by calling the recursive
* sort method.
*/
public void sort() {
sort( sortedArray.length - 1 );
} // end method sort()
/**
* This method recursively sorts the
* array.
*
* @param int end
*/
public void sort( int size ) {
/**
* Establish the heap property
*/
for ( int i = size / 2; i >= 0; i-- ) {
heapify( i, size, sortedArray[i] );
} // end for loop
/**
* Put the largest element last
* and repeat
*/
for ( int i = size; i > 0; i-- ) {
swap( 0, i ); // Swap with element at 1st index
heapify( 0, i - 1, sortedArray[0] ); // Heap is now -1 element
} // end for loop
} // end method sort()
/**
* This method swaps two specified
* integers representing indices
* in the array.
*
* @param int i
* @param int j
*/
private void swap( int i, int j ) {
int temp = sortedArray[i]; // Temp gets i
sortedArray[i] = sortedArray[j]; // i gets j
sortedArray[j] = temp; // j gets temp
SWAPS++; // Increment swaps
} // end method swap()
} // end class HeapSort
Merge Sort
Constructor takes an unsorted array and sorts the array for you automatically. You can retrieve the sorted array by calling getSortedArray().
public class MergeSort {
private int[] sortedArray; // Final Sorted Array
private static long COMPARISONS = 0; // Number of comparisons
private static long SWAPS = 0; // Number of swaps (none for MergeSort)
/**
* MergeSort Constructor
*
* @param int[] array
*/
public MergeSort( int[] array ) {
sortedArray = new int[ array.length ]; // Initialize the sorted array
sort( array, 0, array.length - 1 ); // Merge Sort the given array
} // end MergeSort constructor
/**
* This method returns the number of
* comparisons the sorting algorithm
* made.
*
* @return long COMPARISONS
*/
public long getComparisons() {
return COMPARISONS;
} // end method getComparisons()
/**
* This method returns the final
* sorted array.
*
* @return int[] sortedArray
*/
public int[] getSortedArray() {
return sortedArray;
} // end method getSortedArray()
/**
* This method returns the number of
* swaps the sorting algorithm made.
*
* @return long SWAPS
*/
public long getSwaps() {
return SWAPS;
} // end method getSwaps()
/**
* This method merges the results into one
* array.
*
* @param int[] array
* @param int left
* @param int middle
* @param int right
*/
public void merge( int[] array, int left, int middle, int right ) {
if ( middle + 1 > right ) return; // List is empty
int tempArray[] = new int[ array.length ]; // Initialize a temporary array
/**
* Copy left side of array
* into temporary array
*/
for ( int i = left; i != middle + 1; i++ ) {
tempArray[i] = array[i];
} // end for loop
/**
* Copy right side of array
* into temporary array
*/
for ( int i = middle + 1; i != right + 1; i++ ) {
tempArray[i] = array[ right + middle + 1 - i ];
} // end for loop
/**
* Merge the two
*/
int l = left; // Left side
int r = right; // Right side
for ( int i = left; i != right + 1; i++ ) {
/**
* Left <= Right, so copy Left
* into array
*/
if ( tempArray[l] <= tempArray[r] ) {
COMPARISONS++;
array[i] = tempArray[l++];
}
/**
* Copy Right into array
*/
else {
COMPARISONS++;
array[i] = tempArray[r--];
} // end if
} // end for loop
/**
* Array should be sorted now. Copy
* the array into a local array
* variable for output.
*/
System.arraycopy( array, 0, sortedArray, 0, array.length ); // Copy the param. array into local array
} // end method merge()
/**
* This method recursively sorts the
* given array.
*
* @param int[] array
* @param int left
* @param int right
*/
public void sort( int[] array, int left, int right ) {
if ( left >= right ) return; // Only one element
int middle = ( left + right ) / 2; // Middle index
sort( array, left, middle ); // Sort left side
sort( array, middle + 1, right ); // Sort right side
merge( array, left, middle, right ); // Merge the two
} // end method sort()
} // end class MergeSort
QuickSort
Constructor takes an unsorted array and sorts the array for you automatically. You can retrieve the sorted array by calling getSortedArray().
public class QuickSort {
private int[] sortedArray; // Final Sorted Array
private static long COMPARISONS = 0; // Number of Comparisons
private static long SWAPS = 0; // Number of Swaps
/**
* QuickSort Constructor
*
* @param array
*/
public QuickSort( int[] array ) {
sortedArray = new int[ array.length ]; // Initialize the array
System.arraycopy( array, 0, sortedArray, 0, array.length ); // Copy the param. array into local array
sort( sortedArray, 0, sortedArray.length - 1 ); // Quick Sort the array
} // end QuickSort constructor
/**
* This method returns the number of
* comparisons the sorting algorithm
* made.
*
* @return long COMPARISONS
*/
public long getComparisons() {
return COMPARISONS;
} // end method getComparisons()
/**
* This method returns the final
* sorted array.
*
* @return int[] sortedArray
*/
public int[] getSortedArray() {
return sortedArray;
} // end method getSortedArray()
/**
* This method returns the number of
* swaps the sorting algorithm made.
*
* @return long SWAPS
*/
public long getSwaps() {
return SWAPS;
} // end method getSwaps()
/**
* This method recursively sorts
* the given array.
*
* @param int[] array
* @param int left
* @param int right
*/
private void sort( int[] array, int left, int right ) {
int i = left; // Left Side of Array
int j = right; // Right Side of Array
if ( left >= right ) return; // 0 elements left
int pivot = array[i]; // Choose a pivot
/**
* Left side is still less than the
* right, so continue sorting.
*/
while ( i <= j ) {
COMPARISONS++; // Increment comparisons
/**
* Value of array at index i
* is less than the pivot.
*/
while ( array[i] < pivot ) {
COMPARISONS++; // Increment comparisons
i++; // Increment i
} // end while loop
/**
* Value of pivot is less than
* value of array at index j
*/
while ( pivot < array[j] ) {
COMPARISONS++; // Increment comparisons
j--; // Increment j
} // end while loop
/**
* Left side is less than or
* equal to right side, so
* swap.
*/
if ( i <= j ) {
COMPARISONS++; // Increment comparisons
SWAPS++; // Increment swaps counter
int swap = array[i]; // Store array[i] in swap
array[i++] = array[j]; // array[i++] gets array[j]
array[j--] = swap; // array[j--] gets swap
} // end if
} // end while loop
/**
* Left is less than j,
* so perform quick sort
*/
if ( left < j ) {
COMPARISONS++;
sort(array, left, j);
} // end if
/**
* i is less than right, so
* perform quick sort
*/
if ( i < right ) {
COMPARISONS++;
sort(array, i, right);
} // end if
} // end method sort()
} // end class QuickSort
Questions, comments, errors? Please let me know in the comments.
Tags: heap sort, merge sort, quick sort