Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Random;
- public class Exercise2 {
- public static Random random = new Random(100);
- public static void main(String[] args) {
- int[] array = createRandomArray(10000000);
- long time = System.currentTimeMillis();
- int[] sortedArray = sort(array);
- if(sortedArray.length != array.length || !isSorted(sortedArray)) {
- System.err.println("Failed to sort given array! :-(");
- return;
- }
- System.out.println("Success! Sorting took " + (System.currentTimeMillis() - time) + "ms.");
- }
- /**
- * Creates a randomly filled array of given length
- * @param length
- * @return
- */
- private static int[] createRandomArray(int length) {
- int[] result = new int[length];
- for(int i = 0; i < length; i++) {
- result[i] = random.nextInt();
- }
- return result;
- }
- /**
- * Checks whether a given int array is sorted in ascending order
- * @param array
- * @return <code>true</code> if the given int array is sorted; <code>false</code> otherwise.
- */
- private static boolean isSorted(int[] array) {
- for(int i = 1; i < array.length; i++) {
- if(array[i] < array[i-1]) {
- return false;
- }
- }
- return true;
- }
- /**
- * Merges two sorted int array into one new sorted array.
- * @param lhs
- * @param rhs
- * @return
- */
- private static int[] merge(int[] lhs, int[] rhs) {
- int[] result = new int[lhs.length + rhs.length];
- int leftIndex = 0;
- int rightIndex = 0;
- while(leftIndex < lhs.length && rightIndex < rhs.length) {
- if(lhs[leftIndex] <= rhs[rightIndex]) {
- result[leftIndex + rightIndex] = lhs[leftIndex];
- leftIndex++;
- } else {
- result[leftIndex + rightIndex] = rhs[rightIndex];
- rightIndex++;
- }
- }
- while(leftIndex < lhs.length) {
- result[leftIndex + rightIndex] = lhs[leftIndex];
- leftIndex++;
- }
- while(rightIndex < rhs.length) {
- result[leftIndex + rightIndex] = rhs[rightIndex];
- rightIndex++;
- }
- return result;
- }
- /**
- * Sorts an array from index <code>startIndex</code> (inclusive) to <code>endIndex</code> (exclusive).
- * @param array
- * @param startIndex
- * @param endIndex
- * @return new array that is sorted
- */
- private static int[] mergeSort(int[] array, int startIndex, int endIndex) {
- int length = endIndex - startIndex;
- if(length == 0) {
- return new int[]{};
- }
- if(length == 1) {
- return new int[]{array[startIndex]};
- }
- int halfLength = length / 2;
- int[] sortedLeftPart = mergeSort(array, startIndex, startIndex + halfLength);
- int[] sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
- return merge(sortedLeftPart, sortedRightPart);
- }
- /**
- * Sorts a given array (ascending order)
- * @param array
- * @return
- */
- private static int[] sort(int[] array) {
- //TODO: use multiple threads to speed up the sorting
- return mergeSort(array, 0, array.length);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement