import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.*;
class Solution {
void popul(int[] ar) {
for (int i = 0; i < ar.length; i++) {
ar[i] = random.nextInt();
}
}
interface ProcessIntArray {
void process(int[] arr);
}
public Future<Double> measure(int[] arr, ProcessIntArray processIntArray, ExecutorService es) {
Callable<Double> task = () -> {
long start
= System.
nanoTime(); processIntArray.process(arr);
return (end - start) / 1000000000.0;
};
return es.submit(task);
}
ExecutorService executorService = Executors.newFixedThreadPool(8);
int size = 1000 * 1000;
int[] quickSortArray = new int[size];
popul(quickSortArray);
int[] bubbleSortArray
= Arrays.
copyOf(quickSortArray, quickSortArray.
length); int[] mergeSortArray
= Arrays.
copyOf(quickSortArray, quickSortArray.
length); int[] originalArray
= Arrays.
copyOf(quickSortArray, quickSortArray.
length); int[] insertionSortArray
= Arrays.
copyOf(quickSortArray, quickSortArray.
length);
Future<Double> bubbleSortTime = measure(bubbleSortArray, Solution::bubbleSort, executorService);
Future<Double> insertionSortTime = measure(insertionSortArray, Solution::insertionSort, executorService);
Future<Double> quickSortTime = measure(quickSortArray, Solution::quickSort, executorService);
Future<Double> mergeSortTime = measure(mergeSortArray, Solution::mergeSort, executorService);
System.
out.
println("array size: " + size
); System.
out.
println("quick sort: " + quickSortTime.
get() + "s"); System.
out.
println("merge sort: " + mergeSortTime.
get() + "s"); System.
out.
println("insertion sort: " + insertionSortTime.
get() + "s"); System.
out.
println("bubble sort: " + bubbleSortTime.
get() + "s"); executorService.shutdown();
for (int i = 0; i < quickSortArray.length; i++) {
if (quickSortArray[i] != bubbleSortArray[i] || quickSortArray[i] != mergeSortArray[i] || quickSortArray[i] != insertionSortArray[i]) {
}
}
}
public static void mergeSort(int[] ar) {
if (ar.length < 5) {
bubbleSort(ar);
return;
}
int pivot = ar.length / 2;
int[] ar2 = new int[pivot];
int[] ar3 = new int[ar.length - pivot];
for (int i = 0; i < ar.length; i++) {
if (i < pivot) {
ar2[i] = ar[i];
} else {
ar3[i - pivot] = ar[i];
}
}
mergeSort(ar2);
mergeSort(ar3);
int ar2idx = 0;
int ar3idx = 0;
int arIndexCounter = 0;
while (true) {
int whatToPutInAR = 0;
if (ar2idx != ar2.length && ar3idx != ar3.length) {
if (ar2[ar2idx] < ar3[ar3idx]) {
whatToPutInAR = ar2[ar2idx];
ar2idx++;
} else {
whatToPutInAR = ar3[ar3idx];
ar3idx++;
}
} else if (ar2idx != ar2.length) {
whatToPutInAR = ar2[ar2idx];
ar2idx++;
} else if (ar3idx != ar3.length) {
whatToPutInAR = ar3[ar3idx];
ar3idx++;
} else if (arIndexCounter != ar.length) {
}
if (arIndexCounter == ar.length) return;
ar[arIndexCounter++] = whatToPutInAR;
}
}
private static void quickSort(int[] ar) {
quickSort(ar, 0, ar.length);
}
static public void quickSort(int[] array, int start, int end) {
boolean changed = false;
if (end == 0) return;
int pivot = array[end - 1];
int partitionCandidate = start;
for (int i = start; i < end; i++) {
if (array[i] < pivot) {
swap(array, partitionCandidate++, i);
changed = true;
} else if (pivot < array[i]) {
swap(array, end - 1, i);
changed = true;
}
}
if (start < partitionCandidate) {
quickSort(array, start, partitionCandidate);
}
if (partitionCandidate < end) {
if (partitionCandidate != start || changed) quickSort(array, partitionCandidate, end);
}
}
public static void swap(int[] ar, int from, int to) {
int old = ar[from];
ar[from] = ar[to];
ar[to] = old;
}
public static void bubbleSort(int[] ar) {
for (int i = 0; i < ar.length; i++) {
for (int j = 0; j < ar.length - 1; j++) {
if (ar[j] > ar[j + 1]) {
swap(ar, j + 1, j);
}
}
}
}
private static void insertionSort(int[] ar) {
for (int i = 0; i < ar.length; i++) {
for (int j = i; j >= 1; j--) {
boolean breaker = true;
if (ar[j] < ar[j - 1]) {
breaker = false;
swap(ar, j - 1, j);
}
if (breaker) break;
}
}
}
Solution s = new Solution();
while (true) s.start();
}
}