package sorts;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
/**
* A generic sort algorithm that implements the SortAlgorithm interface.
* Other algorithms extend this class to implement their own sorting logic.
* !!!!!!!!!!! DO NOT MODIFY THIS FILE !!!!!!!!!
*/
public abstract class GenericSortAlgorithm extends RecursiveAction implements SortAlgorithm {
protected static ForkJoinPool pool = new ForkJoinPool();
// For very small arrays, use insertion sort (to reduce overhead)
private static final int INSERTION_THRESHOLD = 10;
protected int[] array;
protected int left;
protected int right;
public GenericSortAlgorithm() {
}
public GenericSortAlgorithm(int[] array, int left, int right) {
this.array = array;
this.left = left;
this.right = right;
}
@Override
// Public method to initiate the sort
public void sort(int[] array) {
this.array = array;
this.left=0;
this.right = array.length - 1;
pool.invoke(this);
//compute();
}
protected void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
protected void quickSort(int[] arr, int low, int high) {
// For very small arrays, use insertion sort
if (high - low < INSERTION_THRESHOLD) {
insertionSort(arr, low, high);
} else if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
protected int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
protected void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}