Untitled
unknown
plain_text
2 years ago
4.5 kB
6
Indexable
/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package mergesort; import java.util.Random; import java.util.Scanner; /** * * @author ADMIN */ public class MergeSort { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here Scanner sc = new Scanner(System.in); int n = InputNumberArray(); int[] array = RandomArray(n); PrintArray("The array:", array); mergeSort(array, 0, array.length - 1); System.out.println(); PrintArray("Sorted array : ", array); } public static int InputNumberArray() { Scanner scanner = new Scanner(System.in); int size; while (true) { // Start an infinite loop to keep asking for input until a valid value is provided. try { System.out.println("Input Number of Array : "); size = Integer.parseInt(scanner.nextLine()); // Read the user's input and parse it as an integer. if (size > 0) { break; // if size > 0 , valid value and loop break } else { System.out.println("You have to input a positive number , Reinpiut : "); // iff size <= 0 , Display notice } } catch (NumberFormatException e) { System.out.println("Invalid value , Reinput : "); // if users input a special character , program will notice to users } } return size; } public static int[] RandomArray(int ArraySize) { int[] array = new int[ArraySize]; // Create a random object name random Random random = new Random(); for (int i = 0; i < ArraySize; i++) { array[i] = random.nextInt(ArraySize); } // loop use to random each element of array return array; } public static void PrintArray(String variable, int[] array) { System.out.print(variable); System.out.print("["); // loop use to accessed each element of array and display them for (int i = 0; i < array.length; i++) { System.out.print(array[i]); if (i < array.length - 1) { System.out.print(","); } }// print each element of the array System.out.print("]"); } public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int middle = (left + right) / 2; // Find the middle index. // Recursively sort the left and right halves. mergeSort(arr, left, middle); // Sort the left half. mergeSort(arr, middle + 1, right); // Sort the right half. // Merge the two sorted halves. merge(arr, left, middle, right); } } // Merge two subarrays of arr[]. public static void merge(int[] arr, int left, int middle, int right) { // Calculate the sizes of the two subarrays to be merged. int size1 = middle - left + 1; int size2 = right - middle; // Create temporary arrays to hold the subarrays. int[] leftArray = new int[size1]; int[] rightArray = new int[size2]; // Copy data to temporary arrays leftArray[] and rightArray[]. for (int i = 0; i < size1; i++) { leftArray[i] = arr[left + i]; } for (int j = 0; j < size2; j++) { rightArray[j] = arr[middle + 1 + j]; } // Merge the two subarrays back into arr[]. int i = 0, j = 0, k = left; while (i < size1 && j < size2) { if (leftArray[i] <= rightArray[j]) { arr[k] = leftArray[i]; i++; } else { arr[k] = rightArray[j]; j++; } k++; } // Copy remaining elements of leftArray[], if any. while (i < size1) { arr[k] = leftArray[i]; i++; k++; } // Copy remaining elements of rightArray[], if any. while (j < size2) { arr[k] = rightArray[j]; j++; k++; } } }
Editor is loading...