Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- public class SortLibrary {
- /**
- public static void main(String[] args) {
- // Test arrays you can use to check your sorts.
- // They represent common arrangements: random, already sorted, reversed, mostly sorted
- int[] random = new int[]{33,94,9,40,77,82,47,15,51,64,76,28,2,85,11};
- int[] alreadySorted = new int[]{2,9,11,15,28,33,40,47,51,64,76,77,82,85,94};
- int[] reversed = new int[]{94,85,82,77,76,64,51,47,40,33,28,15,11,9,2};
- int[] mostlySorted = new int[]{2,85,11,15,28,33,47,40,51,64,76,77,82,9,94};
- int[] longerArray = ArrayImporter.readArrayFile("smallArray.txt");
- int[] myCustomTest = new int[]{15, 23, 42, 4, 8, 16, 1};
- // ***Enter your array to sort here
- int[] arrayToSort = random; // arrayToSort will point to the array you choose
- int[] copyOfArrayToSort = Arrays.copyOf(arrayToSort, arrayToSort.length);
- // ***Enter which sort you want to test
- mergeSort(arrayToSort); // Call your sort method -- Remember array is modified in the method, not returned!
- Arrays.sort(copyOfArrayToSort); // call java.util.Array's sort method for comparison
- if(arrayToSort.length < 50) {
- System.out.println("Result after sort: " + Arrays.toString(arrayToSort));
- System.out.println("Result should be: " + Arrays.toString(copyOfArrayToSort));
- }
- System.out.println("Sorts match? " + Arrays.equals(arrayToSort, copyOfArrayToSort));
- }
- */
- // void normally would be OK. Don't need to return int[] or anything.
- // However, I want you to keep track of and return the number of swaps.
- public static int bubbleSort(int[] nums) {
- int hold;
- int numSwaps = 0;
- for (int i = 0; i < nums.length; i++) {
- for (int j = 0; j < nums.length - 1; j++) {
- if (nums[j] > nums[j + 1]) {
- hold = nums[j];
- nums[j] = nums[j + 1];
- nums[j + 1] = hold;
- numSwaps++;
- }
- }
- }
- return numSwaps;
- }
- // void is OK. 'unsorted' simply receives a copy of reference to the unsorted
- // array 'arrayToSort' when method is called. When your method finishes,
- // 'arrayToSort' will point to the sorted array
- public static void insertionSort(int[] unsorted) {
- for (int i = 2; i < unsorted.length; i++) {
- int currentNum = unsorted[i];
- while (i - 1 >= 0 && unsorted[i-1] > currentNum) {
- unsorted[i] = unsorted [i-1];
- i--;
- }
- unsorted[i] = currentNum;
- }
- }
- public static void mergeSort(int[] unsorted) {
- int size; //how big the current chunk being merged is
- int low; //start index of the leftmost chunk being merged
- for (size = 1; size <= unsorted.length -1; size = 2*size) {
- for (low = 0; low < unsorted.length -1; low += 2*size) {
- int mid = low + size - 1;
- int high;
- if (low + 2*size - 1 < unsorted.length -1) {
- high = low + 2*size - 1;
- }
- else
- high = unsorted.length -1;
- merge(unsorted, low, mid, high);
- }
- }
- }
- public static void merge(int[] nums, int low, int mid, int high) {
- int sizeLeft = mid - low + 1;
- int sizeRight = high - mid;
- int [] l = new int [sizeLeft];
- int [] r = new int [sizeRight];
- for (int i = 0; i < sizeLeft; i++) {
- l[i] = nums[low + i];
- }
- for (int i = 0; i < sizeRight; i++) {
- r[i] = nums[mid + 1 + i];
- }
- int countL = 0;
- int countR = 0;
- int countNum = low;
- while (countL < sizeLeft && countR < sizeRight) {
- if (l[countL] <= r[countR]) {
- nums[countNum] = l[countL];
- countL++;
- }
- else {
- nums[countNum] = r[countR];
- countR++;
- }
- countNum++;
- }
- while (countL < sizeLeft) {
- nums[countNum] = l[countL];
- countL++;
- countNum++;
- }
- while (countR < sizeRight) {
- nums[countNum] = r[countR];
- countR++;
- countNum++;
- }
- }
- public static void selectionSort(int[] unsorted) {
- int sorted = 0;
- int minIndex = -1;
- int hold;
- while (sorted < unsorted.length - 1) {
- int min = Integer.MAX_VALUE;
- for (int i = sorted; i < unsorted.length; i++) {
- if (unsorted[i] < min) {
- min = unsorted[i];
- minIndex = i;
- }
- }
- hold = unsorted[sorted];
- unsorted[sorted] = unsorted[minIndex];
- unsorted[minIndex] = hold;
- sorted++;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement