Advertisement
Guest User

help me

a guest
Feb 22nd, 2018
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.19 KB | None | 0 0
  1.  
  2. import java.util.Arrays;
  3.  
  4. public class SortLibrary {
  5.  
  6. /**
  7.     public static void main(String[] args) {
  8.         // Test arrays you can use to check your sorts.
  9.         // They represent common arrangements: random, already sorted, reversed, mostly sorted
  10.         int[] random = new int[]{33,94,9,40,77,82,47,15,51,64,76,28,2,85,11};
  11.         int[] alreadySorted = new int[]{2,9,11,15,28,33,40,47,51,64,76,77,82,85,94};
  12.         int[] reversed = new int[]{94,85,82,77,76,64,51,47,40,33,28,15,11,9,2};
  13.         int[] mostlySorted = new int[]{2,85,11,15,28,33,47,40,51,64,76,77,82,9,94};
  14.         int[] longerArray = ArrayImporter.readArrayFile("smallArray.txt");
  15.         int[] myCustomTest = new int[]{15, 23, 42, 4, 8, 16, 1};       
  16.  
  17.         // ***Enter your array to sort here
  18.         int[] arrayToSort = random; // arrayToSort will point to the array you choose
  19.         int[] copyOfArrayToSort = Arrays.copyOf(arrayToSort, arrayToSort.length);
  20.  
  21.         // ***Enter which sort you want to test
  22.         mergeSort(arrayToSort);     // Call your sort method -- Remember array is modified in the method, not returned!
  23.         Arrays.sort(copyOfArrayToSort); // call java.util.Array's sort method for comparison
  24.  
  25.         if(arrayToSort.length < 50) {
  26.             System.out.println("Result after sort: " + Arrays.toString(arrayToSort));
  27.             System.out.println("Result should be: " + Arrays.toString(copyOfArrayToSort));
  28.         }
  29.  
  30.         System.out.println("Sorts match? " + Arrays.equals(arrayToSort, copyOfArrayToSort));
  31.  
  32.     }
  33.     */
  34.  
  35.     // void normally would be OK.  Don't need to return int[] or anything.
  36.     // However, I want you to keep track of and return the number of swaps.
  37.     public static int bubbleSort(int[] nums) {
  38.  
  39.         int hold;
  40.         int numSwaps = 0;
  41.  
  42.         for (int i = 0; i < nums.length; i++) {
  43.             for (int j = 0; j < nums.length - 1; j++) {
  44.                 if (nums[j] > nums[j + 1]) {
  45.                     hold = nums[j];
  46.                     nums[j] = nums[j + 1];
  47.                     nums[j + 1] = hold;
  48.                     numSwaps++;
  49.                 }
  50.             }
  51.         }
  52.         return numSwaps;
  53.  
  54.     }
  55.  
  56.     // void is OK.  'unsorted' simply receives a copy of reference to the unsorted
  57.     // array 'arrayToSort' when method is called.  When your method finishes,
  58.     // 'arrayToSort' will point to the sorted array
  59.     public static void insertionSort(int[] unsorted) {
  60.  
  61.         for (int i = 2; i < unsorted.length; i++) {
  62.             int currentNum = unsorted[i];
  63.             while (i - 1 >= 0 && unsorted[i-1] > currentNum) {
  64.                 unsorted[i] = unsorted [i-1];
  65.                 i--;
  66.             }
  67.             unsorted[i] = currentNum;
  68.         }
  69.  
  70.     }
  71.  
  72.     public static void mergeSort(int[] unsorted) {
  73.         int size; //how big the current chunk being merged is
  74.         int low; //start index of the leftmost chunk being merged
  75.        
  76.         for (size = 1; size <= unsorted.length -1; size = 2*size) {
  77.             for (low = 0; low < unsorted.length -1; low += 2*size) {
  78.                 int mid = low + size - 1;
  79.                 int high;
  80.                
  81.                 if (low + 2*size - 1 < unsorted.length -1) {
  82.                     high = low + 2*size - 1;
  83.                 }
  84.                 else
  85.                     high = unsorted.length -1;
  86.                
  87.                 merge(unsorted, low, mid, high);
  88.             }
  89.         }
  90.        
  91.  
  92.     }
  93.  
  94.     public static void merge(int[] nums, int low, int mid, int high) {
  95.         int sizeLeft = mid - low + 1;
  96.         int sizeRight = high - mid;
  97.  
  98.         int [] l = new int [sizeLeft];
  99.         int [] r = new int [sizeRight];
  100.  
  101.         for (int i = 0; i < sizeLeft; i++) {
  102.             l[i] = nums[low + i];
  103.         }
  104.         for (int i = 0; i < sizeRight; i++) {
  105.             r[i] = nums[mid + 1 + i];
  106.         }
  107.  
  108.         int countL = 0;
  109.         int countR = 0;
  110.         int countNum = low;
  111.  
  112.         while (countL < sizeLeft && countR < sizeRight) {
  113.             if (l[countL] <= r[countR]) {
  114.                 nums[countNum] = l[countL];
  115.                 countL++;
  116.             }
  117.             else {
  118.                 nums[countNum] = r[countR];
  119.                 countR++;
  120.             }
  121.             countNum++;
  122.         }
  123.  
  124.         while (countL < sizeLeft) {
  125.             nums[countNum] = l[countL];
  126.             countL++;
  127.             countNum++;
  128.         }
  129.  
  130.         while (countR < sizeRight) {
  131.             nums[countNum] = r[countR];
  132.             countR++;
  133.             countNum++;
  134.         }
  135.  
  136.     }
  137.  
  138.  
  139.     public static void selectionSort(int[] unsorted) {
  140.         int sorted = 0;
  141.         int minIndex = -1;
  142.         int hold;
  143.  
  144.         while (sorted < unsorted.length - 1) {
  145.             int min = Integer.MAX_VALUE;
  146.  
  147.             for (int i = sorted; i < unsorted.length; i++) {
  148.                 if (unsorted[i] < min) {
  149.                     min = unsorted[i];
  150.                     minIndex = i;
  151.                 }
  152.             }
  153.             hold = unsorted[sorted];
  154.             unsorted[sorted] = unsorted[minIndex];
  155.             unsorted[minIndex] = hold;
  156.             sorted++;
  157.         }
  158.  
  159.     }
  160.  
  161.  
  162.  
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement