Mergesort in Java

Mergesort

 
Mergesort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two collections and these are again sorted via mergesort. Once the two collections are sorted then the result is combined
Mergesort will take the middle of the collection and takes then the two collection for the next iteration of mergesort. In the merging part mergesort runs through the both collections and selects the lowest of the both to insert it into a new collection.
In comparison to quicksort the divide part is simple in mergesort while the merging take is complex. In addition quicksort can work "inline", e.g. it does not have to create a copy of the collection while mergesort requires a copy

Program

Mergesort .java :-  
public class Mergesort {
  private int[] numbers;
  private int[] helper;

  private int number;

  public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
  }

  private void mergesort(int low, int high) {
    // Check if low is smaller then high, if not then the array is sorted
    if (low < high) {
      // Get the index of the element which is in the middle
      int middle = (low + high) / 2;
      // Sort the left side of the array
      mergesort(low, middle);
      // Sort the right side of the array
      mergesort(middle + 1, high);
      // Combine them both
      merge(low, middle, high);
    }
  }

  private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
      helper[i] = numbers[i];
    }

    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
      if (helper[i] <= helper[j]) {
        numbers[k] = helper[i];
        i++;
      } else {
        numbers[k] = helper[j];
        j++;
      }
      k++;
    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) { numbers[k] = helper[i]; k++; i++; } }}


Test.java:-
import java.util.Random;

class Test
{

public static void main(String args[])
{
     int numbers = new int[SIZE];
    Random generator = new Random();
    for (int i = 0; i < numbers.length; i++) {
      numbers[i] = generator.nextInt(MAX);
   }
Mergesort sorter = new Mergesort();
sorter.sort(numbers);


}
}

Complexity Analysis

The following describes the runtime complexity of mergesort.
Mergesort sorts in worst case in O(n log n) time. Due to the required copying of the collection Mergesort is in the average case slower then Quicksort.

Quicksort in Java

1.1. Overview

Sort algorithms are ordering the elements of an array according to a predefined order. Quicksort is a divide and conquer algorithm. In a divide and conquer sorting algorithm their the original data is separated into two parts (divide) which are individually sorted (conquered) and then combined.

1.2. Description of the algorithm

If the array contains only one element or zero elements then the array is sorted.
If the array contains more then one element then:

• Select an element from the array. This element is called the "pivot element". For example select the element in the middle of the array.
  
• All elements which are smaller then the pivot element are placed in one array and all elements which are larger are placed in another array.
  
• Sort both arrays by recursively applying Quicksort to them.
  
• Combine the arrays

Quicksort can be implemented to sort "in-place". This means that the sorting takes place in the array and that no additional array need to be created.

Program

Quicksort.java:--

public class Quicksort  {
  private int[] numbers;
  private int number;

  public void sort(int[] values) {
// Check for empty or null array
    if (values ==null || values.length==0){
      return;
    }
    this.numbers = values;
    number = values.length;
    quicksort(0, number - 1);
  }

  private void quicksort(int low, int high) {
    int i = low, j = high;
    // Get the pivot element from the middle of the list
    int pivot = numbers[low + (high-low)/2];

    // Divide into two lists
    while (i <= j) {
      // If the current value from the left list is smaller then the pivot
      // element then get the next element from the left list
      while (numbers[i] < pivot) {
        i++;
      }
      // If the current value from the right list is larger then the pivot
      // element then get the next element from the right list
      while (numbers[j] > pivot) {
        j--;
      }

      // If we have found a values in the left list which is larger then
      // the pivot element and if we have found a value in the right list
      // which is smaller then the pivot element then we exchange the
      // values.
      // As we are done we can increase i and j
      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }
    // Recursion
    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
  }

  private void exchange(int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
  }
}

Test.java:-

public class Test
{
public static void main(String args[]){
    Quicksort sorter = new Quicksort();
    int[] test = { 5, 5, 6, 6, 4, 4, 5, 5, 4, 4, 6, 6, 5, 5 };
    sorter.sort(test);
   printResult(test);
  }
 private void printResult(int[] numbers) {
    for (int i = 0; i < numbers.length; i++) {
      System.out.print(numbers[i]);
    }
    System.out.println();
  }
}

Complexity Analysis

The following describes the runtime complexity of quicksort.
Fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. Quicksort will in the best case divide the array into almost two identical parts. It the array contains n elements then the first run will need O(n). Sorting the remaining two sub-arrays takes 2* O(n/2). This ends up in a performance of O(n log n).
In the worst case quicksort selects only one element in each iteration. So it is O(n) + O(n-1) + (On-2).. O(1) which is equal to O(n^2).
The average case of quicksort is O(n log n).

Program to print 'n' twin Prime numbers

import java.util.Scanner;
public class TwinPrime {
   
    public static void main(String a[])
    {

         System.out.println("This program prints 1st n twin prime nummbers");
        Scanner sc= new Scanner(System.in);
        int input = sc.nextInt();
        int i=3,n=35;
        boolean k,task=true;
             
            int count =0;
             while(task)
              {
                     if((isPrime(i)) & ( isPrime(i+2)))
                     {  
                         count++;
                         System.out.println("  "+(i-2)+"  "+i );
                         if(count==input ) { task = false; }
                     }
                     i+=2;
              }
            

 System.out.println("Total no of twin prime Numbers:-"+count );

   
    }
    public static boolean isPrime(int n) {

    //check if n is a multiple of 2
    if (n%2==0) return false;

    //if not, then just check the odds
    for(int i=3;i*i<=n;i+=2) {
        if(n%i==0)
            return false;
    }
    return true;
}

}