Hi Guys,
I have been asked to implement the following algorithms. I have done them according to my knowledge and would like you guys to help me by verifying them if am right. They are simple methods to sort arrays of integers
The following code contains the methods:
public class Algorithms {
// Use this class to pass a comparison counter
// as a function argument, and get the update
// in the caller.
private class Counter {
public int value;
}
//************************ 1 ************************
// Sort the elements of elementArray using insertion sort
// Return the number of comparisons
public int insertionSort(Comparable[] elementArray) {
final int LENGTH = elementArray.length;
int numberOfCompares = 0;
for(int i = 1; i < LENGTH; i++){
for(int j = i; j > 0 && elementArray[j].compareTo(elementArray[j - 1]) < 0; j--){
// swap the current element with its predecessor
Comparable tmp = elementArray[j];
elementArray[j] = elementArray[j - 1];
elementArray[j - 1] = tmp;
numberOfCompares++;
}
}
return numberOfCompares;
}
//************************ 2 ************************
// Sort the elements of elementArray using merge sort
// Return the number of comparisons
public int mergeSort(Comparable[] elementArray) {
int LENGTH = elementArray.length;
int middle = 0, high = 0, numberOfCompares = 0;
Comparable[] helper = helper = new Comparable[LENGTH];
for (int size = 1; size < LENGTH; size = size + size){
for(int low = 0; low < LENGTH - size; low += size + size){
middle = low + size - 1;
high = low + size + size - 1;
numberOfCompares += merge(elementArray, low, middle, Math.min(high, LENGTH - 1), helper);
}
}
return numberOfCompares;
}
// Merges the two sub-arrays to be one sorted array
private int merge(Comparable[] a, int low, int middle, int high, Comparable[] helper){
int i = low;
int j = middle + 1;
int numberOfCompares = 0;
for(int k = low; k <= high; k++){
helper[k] = a[k];
}
for(int k = low; k <= high; k++){
if(i > middle){
a[k] = helper[j++];
}else if(j > high){
a[k] = helper[i++];
}else if(helper[j].compareTo(helper[i]) < 0){
a[k] = helper[j++];
numberOfCompares++;
}else{
a[k] = helper[i++];
}
}
return numberOfCompares;
}
//************************ 3 ************************
// Sort the elements of elementArray using quick sort
// Always pivot on the first element
// Return the number of comparisons
public int quickSort(Comparable[] elementArray) {
Counter nCompares = new Counter();
int LENGTH = elementArray.length;
//StdRandom.shuffle(elementArray);
sortQuickSort(elementArray, 0, LENGTH - 1, nCompares);
return nCompares.value;
}
// Sorts the array recursively
private static void sortQuickSort(Comparable[] elements, int low, int high, Counter nCompares){
if(high <= low)
return;
int j = partitionArrayElements(elements, low, high, nCompares);
sortQuickSort(elements, low, j - 1, nCompares);
sortQuickSort(elements, j + 1, high, nCompares);
}
// Partitions the arrays
private static int partitionArrayElements(Comparable[] a, int low, int high, Counter nCompares){
int i = low;
int j = high + 1;
Comparable v = a[low];
while(true){
while(a[++i].compareTo(v) < 0){
nCompares.value++;
if(i == high)
break;
}
while(v.compareTo(a[--j]) < 0){
nCompares.value++;
if(j == low)
break;
}
if(i >= j)
break;
swapTwoElements(a, i, j);
}
swapTwoElements(a, low, j);
return j;
}
// Swaps two array elements
private static void swapTwoElements(Comparable[] a, int i, int j){
Comparable tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
//************************ 4 ************************
// Sort the elements of elementArray using quick sort
// Always pivot on the first element
// Switch to insertion sort for sub-arrays of length at most 5 elements
// Return the number of comparisons
public int quickInsertionSort(Comparable[] elementArray) {
Counter nCompares = new Counter();
int LENGTH = elementArray.length;
//StdRandom.shuffle(elementArray);
sortQuickSortInsertion(elementArray, 0, LENGTH - 1, nCompares);
return nCompares.value;
}
// Sorts the array recursively but uses Insertion sort
private void sortQuickSortInsertion(Comparable[] elements, int low, int high, Counter nCompares){
if(high <= low + 5){
nCompares.value += insertionSort(elements);
// System.out.println("low = " + low + " -- " + "high = " + high);
return;
}
int j = partitionArrayElements(elements, low, high, nCompares);
sortQuickSortInsertion(elements, low, j - 1, nCompares);
sortQuickSortInsertion(elements, j + 1, high, nCompares);
}
//************************ 5 ************************
// Sort the elements of elementArray using quick sort
// Always pivot on a random element
// Return the number of comparisons
public int randomQuickSort(Comparable[] elementArray) {
Counter nCompares = new Counter();
int LENGTH = elementArray.length;
//StdRandom.shuffle(elementArray);
sortRandomQuickSortWithRandomPivot(elementArray, 0, LENGTH - 1, nCompares);
return nCompares.value;
}
// Sorts the array recursively with random pivot element
private static void sortRandomQuickSortWithRandomPivot(Comparable[] elements, int low, int high, Counter nCompares){
if(high <= low)
return;
int j = partitionArrayElementsWithRandomPivot(elements, low, high, nCompares);
sortRandomQuickSortWithRandomPivot(elements, low, j - 1, nCompares);
sortRandomQuickSortWithRandomPivot(elements, j + 1, high, nCompares);
}
// Partitions the arrays
private static int partitionArrayElementsWithRandomPivot(Comparable[] a, int low, int high, Counter nCompares){
int i = low;
int j = high + 1;
Random random = new Random();
int pivot = random.nextInt(a.length);
//System.out.println("pivot: " + pivot);
Comparable v = a[pivot];
while(true){
while(a[++i].compareTo(v) < 0){
nCompares.value++;
if(i == high)
break;
}
while(v.compareTo(a[--j]) < 0){
nCompares.value++;
if(j == low)
break;
}
if(i >= j)
break;
swapTwoElements(a, i, j);
}
swapTwoElements(a, low, j);
return j;
}
//************************ 6 ************************
// Sort the elements of elementArray using quick sort
// Always pivot on a random element
// Switch to insertion sort for sub-arrays of length at most 5 elements
// Return the number of comparisons
public int randomQuickInsertionSort(Comparable[] elementArray) {
Counter nCompares = new Counter();
int LENGTH = elementArray.length;
//StdRandom.shuffle(elementArray);
sortRandomQuickInsertionSortWithRandomPivot(elementArray, 0, LENGTH - 1, nCompares);
return nCompares.value;
}
// Sorts the array recursively with random pivot element
private void sortRandomQuickInsertionSortWithRandomPivot(Comparable[] elements, int low, int high, Counter nCompares){
if(high <= (low + 5)){
nCompares.value += insertionSort(elements);
return;
}
int j = partitionArrayElementsWithRandomPivot(elements, low, high, nCompares);
sortRandomQuickInsertionSortWithRandomPivot(elements, low, j - 1, nCompares);
sortRandomQuickInsertionSortWithRandomPivot(elements, j + 1, high, nCompares);
}
}
Thanks for your help.