Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on May 7th, 2011  |  syntax: Java  |  size: 2.90 KB  |  views: 85  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.  
  2. import java.util.Random;
  3.  
  4. public class Exercise2 {
  5.         public static Random random = new Random(100);
  6.        
  7.         public static void main(String[] args) {
  8.                 int[] array = createRandomArray(10000000);
  9.                
  10.                 long time = System.currentTimeMillis();
  11.                
  12.                 int[] sortedArray = sort(array);
  13.                
  14.                 if(sortedArray.length != array.length || !isSorted(sortedArray)) {
  15.                         System.err.println("Failed to sort given array! :-(");
  16.                         return;
  17.                 }              
  18.                 System.out.println("Success! Sorting took " + (System.currentTimeMillis() - time) + "ms.");            
  19.         }
  20.  
  21.         /**
  22.          * Creates a randomly filled array of given length
  23.          * @param length
  24.          * @return
  25.          */
  26.         private static int[] createRandomArray(int length) {
  27.                 int[] result = new int[length];
  28.                 for(int i = 0; i < length; i++) {
  29.                         result[i] = random.nextInt();
  30.                 }
  31.                 return result;
  32.         }
  33.        
  34.         /**
  35.          * Checks whether a given int array is sorted in ascending order  
  36.          * @param array
  37.          * @return <code>true</code> if the given int array is sorted; <code>false</code> otherwise.
  38.          */
  39.         private static boolean isSorted(int[] array) {
  40.                 for(int i = 1; i < array.length; i++) {
  41.                         if(array[i] < array[i-1]) {
  42.                                 return false;
  43.                         }
  44.                 }
  45.                 return true;
  46.         }
  47.        
  48.         /**
  49.          * Merges two sorted int array into one new sorted array.
  50.          * @param lhs
  51.          * @param rhs
  52.          * @return
  53.          */
  54.         private static int[] merge(int[] lhs, int[] rhs) {
  55.                 int[] result = new int[lhs.length + rhs.length];
  56.                
  57.                 int leftIndex = 0;
  58.                 int rightIndex = 0;
  59.                 while(leftIndex < lhs.length && rightIndex < rhs.length) {
  60.                         if(lhs[leftIndex] <= rhs[rightIndex]) {
  61.                                 result[leftIndex + rightIndex] = lhs[leftIndex];
  62.                                 leftIndex++;
  63.                         } else {
  64.                                 result[leftIndex + rightIndex] = rhs[rightIndex];
  65.                                 rightIndex++;
  66.                         }
  67.                 }
  68.                
  69.                 while(leftIndex < lhs.length) {
  70.                         result[leftIndex + rightIndex] = lhs[leftIndex];
  71.                         leftIndex++;
  72.                 }
  73.                
  74.                 while(rightIndex < rhs.length) {
  75.                         result[leftIndex + rightIndex] = rhs[rightIndex];
  76.                         rightIndex++;
  77.                 }
  78.                
  79.                 return result;
  80.         }
  81.        
  82.         /**
  83.          * Sorts an array from index <code>startIndex</code> (inclusive) to <code>endIndex</code> (exclusive).
  84.          * @param array
  85.          * @param startIndex
  86.          * @param endIndex
  87.          * @return new array that is sorted
  88.          */
  89.         private static int[] mergeSort(int[] array, int startIndex, int endIndex) {
  90.                 int length = endIndex - startIndex;
  91.                 if(length == 0) {
  92.                         return new int[]{};
  93.                 }
  94.                 if(length == 1) {
  95.                         return new int[]{array[startIndex]};
  96.                 }
  97.                
  98.                 int halfLength = length / 2;
  99.                 int[] sortedLeftPart = mergeSort(array, startIndex, startIndex + halfLength);
  100.                 int[] sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
  101.                
  102.                 return merge(sortedLeftPart, sortedRightPart);         
  103.         }
  104.        
  105.        
  106.         /**
  107.          * Sorts a given array (ascending order)
  108.          * @param array
  109.          * @return
  110.          */
  111.         private static int[] sort(int[] array) {
  112.                 //TODO: use multiple threads to speed up the sorting
  113.                
  114.                 return mergeSort(array, 0, array.length);
  115.         }
  116.        
  117.        
  118. }
clone this paste RAW Paste Data