SHARE
TWEET

quickSort

a guest Nov 17th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3. import java.lang.*;
  4.  
  5. public class QuickSort {
  6.     public static void bubbleSort(Integer[] arr, int n) {
  7.         for (int i = 0; i < n - 1; i++)
  8.             for (int j = 0; j < n - i - 1; j++)
  9.                 if (arr[j] > arr[j + 1]) {
  10.                     swap(arr, j, j+1);
  11.                 }
  12.     }
  13.  
  14.     public static void quickSortDeluxe(Integer[] arr, int p, int r, int c) {
  15.         if (p < r) {
  16.             bubbleSort(arr, c);
  17.             int q = partition(arr, p, r);
  18.             quickSort(arr, p, q);
  19.             quickSort(arr, q + 1, r);
  20.         }
  21.     }
  22.  
  23.     public static void quickSort(Integer[] arr, int p, int r) {
  24.         if (p < r) {
  25.             int q = partition(arr, p, r);
  26.             quickSort(arr, p, q);
  27.             quickSort(arr, q + 1, r);
  28.         }
  29.     }
  30.  
  31.     public static int partition(Integer[] arr, int p, int r) {
  32.         int x = arr[r];
  33.         int i = p - 1;
  34.         for (int j = 0; j < r; j++) {
  35.             if (arr[j] < x) {
  36.                 i++;
  37.                 swap(arr, i, j);
  38.             }
  39.         }
  40.         if (i < r)
  41.             return i;
  42.         else
  43.             return i - 1;
  44.     }
  45.  
  46.     public static void swap(Integer[] arr, int a, int b) {
  47.         int temp;
  48.         temp = arr[a];
  49.         arr[a] = arr[b];
  50.         arr[b] = temp;
  51.     }
  52.  
  53.     public static void main(String[] args) {
  54.         int[] size = {100, 500, 1000, 5000};
  55.         long[][] res = new long[4][4];
  56.         long begin, end;
  57.         Random r = new Random();
  58.  
  59.         for (int i = 0; i < size.length; i++) {
  60.             Integer[] arr = new Integer[size[i]];
  61.             int c = r.nextInt(size[i]);
  62.             Arrays.fill(arr, new Random().nextInt());
  63.             Integer dup[] = arr;
  64.             Integer dupDesc[] = arr;
  65.             Integer dupDesc2[] = arr;
  66.             Arrays.sort(dupDesc, Collections.reverseOrder());
  67.             Arrays.sort(dupDesc2, Collections.reverseOrder());
  68.  
  69.             begin = System.nanoTime();
  70.             quickSort(arr, 0, size[i]-1);
  71.             end = System.nanoTime();
  72.             res[0][i] = (end - begin);
  73.  
  74.             begin = System.nanoTime();
  75.             quickSortDeluxe(dup, 0, size[i]-1, c);
  76.             end = System.nanoTime();
  77.             res[1][i] = (end - begin);
  78.          
  79.             begin = System.nanoTime();
  80.             quickSort(dupDesc, 0, size[i]-1);
  81.             end = System.nanoTime();
  82.             res[2][i] = (end - begin);
  83.  
  84.             begin = System.nanoTime();
  85.             quickSortDeluxe(dupDesc2, 0, size[i]-1, c);
  86.             end = System.nanoTime();
  87.             res[3][i] = (end - begin);
  88.         }
  89.         System.out.println("Wyniki działania programu:");
  90.         System.out.println();
  91.         System.out.println("Rozmiar tablicy n=100:\nDane korzystne|QuickSort: "+res[0][0]+"\nDane korzystne|QuickSort+: "+res[1][0]+"\nDane niekorzystne|QuickSort: "+res[2][0]+"\nDane niekorzystne|QuickSort+: "+res[3][0]);
  92.         System.out.println();
  93.         System.out.println("Rozmiar tablicy n=500:\nDane korzystne|QuickSort: "+res[0][1]+"\nDane korzystne|QuickSort+: "+res[1][1]+"\nDane niekorzystne|QuickSort: "+res[2][1]+"\nDane niekorzystne|QuickSort+: "+res[3][1]);
  94.         System.out.println();
  95.         System.out.println("Rozmiar tablicy n=1000:\nDane korzystne|QuickSort: "+res[0][2]+"\nDane korzystne|QuickSort+: "+res[1][2]+"\nDane niekorzystne|QuickSort: "+res[2][2]+"\nDane niekorzystne|QuickSort+: "+res[3][2]);
  96.         System.out.println();
  97.         System.out.println("Rozmiar tablicy n=5000:\nDane korzystne|QuickSort: "+res[0][3]+"\nDane korzystne|QuickSort+: "+res[1][3]+"\nDane niekorzystne|QuickSort: "+res[2][3]+"\nDane niekorzystne|QuickSort+: "+res[3][3]);
  98.     }
  99. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top