MergeSort

 import java.util.Random;


public class MergesortExample {

    public static void main(String[] args) {
        int N = 500; // Number of elements to sort

        // Initialize an array of random integers
        int[] arr = new int[N];
        Random rand = new Random();
        for (int i = 0; i < N; i++) {
            arr[i] = rand.nextInt(1000); // Random integers between 0 and 999
        }

        // Displaying the unsorted array (optional)
        System.out.println("Unsorted array:");
        printArray(arr);

        // Start measuring time
        long startTime = System.nanoTime();

        // Call the mergesort method
        mergesort(arr, 0, N - 1);

        // End measuring time
        long endTime = System.nanoTime();

        // Calculate time taken to sort
        long duration = (endTime - startTime); // Time in nanoseconds

        // Displaying the sorted array (optional)
        System.out.println("\nSorted array:");
        printArray(arr);

        // Display the time taken for sorting
        System.out.println("\nTime taken for Mergesort: " + duration + " nanoseconds.");
    }

    // Mergesort function using divide and conquer strategy
    public static void mergesort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int mid = (left + right) / 2;

            // Recursively divide the array into two halves
            mergesort(arr, left, mid);
            mergesort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    // Merge two halves of the array
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays for the left and right halves
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // Copy data to temporary arrays
        System.arraycopy(arr, left, leftArr, 0, n1);
        System.arraycopy(arr, mid + 1, rightArr, 0, n2);

        // Merge the temporary arrays back into the original array
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of leftArr[] if any
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        // Copy remaining elements of rightArr[] if any
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    // Helper function to print the array (optional)
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Comments

Post a Comment

Popular posts from this blog

q3part b

  import java . util . Random ; public class TSPMutation {     public static void main( String [] args ) {         // Example cities (0, 1, 2, 3, 4)         int [] chromosome = { 0 , 1 , 2 , 3 , 4 }; // A possible solution (tour)                 System .out.println( "Original Chromosome:" );         printChromosome(chromosome);                 // Apply Mutation (Swap two cities in the path)         mutate(chromosome);                 System .out.println( "Mutated Chromosome:" );         printChromosome(chromosome);     }     // Mutation function: Swap two cities' positions     public static void mutate( int [] chromosome ) {         Random rand = new Random();           ...
Read more

Literal table

 #code import java.util.*; class Literal {     String value;     int address;     public Literal(String value) {         this.value = value;         this.address = -1; // not assigned yet     } } public class Ass2{     // Check if a literal already exists in the list     public static boolean literalExists(List<Literal> list, String value) {         for (Literal l : list) {             if (l.value.equals(value)) return true;         }         return false;     }     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         List<String> code = new ArrayList<>();         List<Literal> literalTable = new ArrayList<>();         Lis...
Read more

quicksort 1

 import java.util.Random; public class QuicksortExample {     public static void main(String[] args) {         int N = 500; // Number of elements to sort         // Initialize an array of random integers         int[] arr = new int[N];         Random rand = new Random();         for (int i = 0; i < N; i++) {             arr[i] = rand.nextInt(1000); // Random integers between 0 and 999         }         // Displaying the unsorted array (optional)         System.out.println("Unsorted array:");         printArray(arr);         // Start measuring time         long startTime = System.nanoTime();         // Call the quicksort method         quicksort(arr, 0, N - 1);       ...
Read more