Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
4.5 kB
3
Indexable
Never
/*
 * 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++;
        }
    }
}