StoryMakerTV

[Java] Updated Optimization of Sorting algorithms

Feb 8th, 2012
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Arrays;
  2. import java.util.Random;
  3.  
  4.  
  5. public class shaker {
  6.  
  7.     /**
  8.      * @param args
  9.      */
  10.    
  11.     public static void quickSort(int[] array, int links, int rechts)
  12.     {
  13.        int pivot, temp;
  14.        int l, r;
  15.  
  16.        if (links < rechts)
  17.        {
  18.           l = links; r = rechts;
  19.  
  20.           pivot = array[(links+rechts) >> 1];
  21.  
  22.           do
  23.           {
  24.              while (array[l] < pivot) l++;
  25.              while (array[r] > pivot) r--;
  26.  
  27.              if (l <= r)
  28.              {
  29.                 temp = array[r]; array[r] = array[l]; array[l] = temp;
  30.  
  31.                 l++; r--;
  32.              }
  33.           }
  34.           while (l <= r);
  35.  
  36.           quickSort(array, links, r);
  37.           quickSort(array, l, rechts);
  38.        }
  39.     }
  40.    
  41.    
  42.     public static void shakerSort(int[] a) {
  43.         int begin = -1;
  44.         int ende = a.length - 2;
  45.         int temp, i;
  46.         boolean vertauscht;
  47.        
  48.         while(vertauscht) {
  49.             vertauscht = false;
  50.             ++begin;
  51.             for (i = begin; i<=ende; ++i) {
  52.                 if (a[i] > a[i+1]) {
  53.                     temp = a[i];
  54.                     a[i] = a[i+1];
  55.                     a[i+1] = temp;
  56.                     vertauscht = true;
  57.                 }
  58.             }
  59.             if (!vertauscht) break;
  60.            
  61.             vertauscht = false;
  62.             --ende;
  63.            
  64.             for (i = ende; i >= begin; i--) {
  65.                 if (a[i] > a[i+1]) {
  66.                     temp = a[i];
  67.                     a[i] = a[i+1];
  68.                     a[i+1] = temp;
  69.                     vertauscht = true;     
  70.                 }
  71.             }
  72.         }
  73.     }
  74.    
  75.  
  76.    public static void bubbleSort(int[] x) {
  77.       boolean unsortiert = true;
  78.       int temp;
  79.       while (unsortiert){
  80.          unsortiert = false;
  81.          for (int i=0; i < x.length-1; i++)
  82.             if (x[i] > x[i+1]) {                      
  83.                temp       = x[i];
  84.                x[i]       = x[i+1];
  85.                x[i+1]     = temp;
  86.                unsortiert = true;
  87.             }          
  88.       }
  89.    }
  90.  
  91.    public static int[] r(int l, int n)
  92.    {
  93.      int[] a = new int[l];
  94.      Random g = new Random();
  95.      for (int i = 0; i < a.length; i++)
  96.          a[i] = g.nextInt(n);
  97.      return a;
  98.    }
  99.    
  100.     public static void main(String[] args) {
  101.         long timeStart, timeEnd;
  102.         int elements = 1000;
  103.        
  104.         int[] arr1 = r(elements, elements*2);
  105.         int[] arr2 = arr1.clone();
  106.         int[] arr3 = arr1.clone();
  107.        
  108.         //----
  109.        
  110.         System.out.println("arr length: " + arr1.length + "\n");
  111.        
  112.         System.out.println("BubbleSort :");
  113.         timeStart = System.currentTimeMillis();
  114.             bubbleSort(arr1);
  115.             //System.out.println(Arrays.toString(arr1));
  116.         timeEnd = System.currentTimeMillis();
  117.         System.out.println("Verlaufszeit des Sortierverfahrens: " + (timeEnd - timeStart) + " Millisekunden!");
  118.        
  119.         System.out.println("");
  120.        
  121.         System.out.println("ShakerSort :");
  122.         timeStart = System.currentTimeMillis();
  123.             shakerSort(arr2);
  124.             //System.out.println(Arrays.toString(arr2));
  125.         timeEnd = System.currentTimeMillis();
  126.         System.out.println("Verlaufszeit des Sortierverfahrens: " + (timeEnd - timeStart) + " Millisekunden!");
  127.        
  128.         System.out.println("");
  129.        
  130.         System.out.println("QuickSort (rec.) :");
  131.         timeStart = System.currentTimeMillis();
  132.             quickSort(arr3, 0, arr3.length -1);
  133.             //System.out.println(Arrays.toString(arr3));
  134.         timeEnd = System.currentTimeMillis();
  135.         System.out.println("Verlaufszeit des Sortierverfahrens: " + (timeEnd - timeStart) + " Millisekunden!");
  136.        
  137.     }
  138.  
  139. }
Advertisement
Add Comment
Please, Sign In to add comment