HEAP SORT JAVA

import java.util.Scanner;

// Java program for implementation of Heap Sort
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;

// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}

// Driver program
public static void main(String args[])
{
        Scanner scan = new Scanner( System.in );      
        System.out.println("Heap Sort Test\n");
        int n, i;
        /* Accept number of elements */
        System.out.println("Enter number of integer elements");
        n = scan.nextInt();
        /* Create integer array on n elements */
        int arr[] = new int[ n ];
        /* Accept elements */
        System.out.println("\nEnter "+ n +" integer elements");
        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();
       
HeapSort ob = new HeapSort();
ob.sort(arr);

System.out.println("Sorted array is");
printArray(arr);
}
}

SHELL SORT JAVA

import java.util.Arrays;
import java.util.Scanner;


public class ShellSort {

public static void Sort( int arr[] )
{
int inner, outer;
int valueToInsert;
int interval = 1;  
int i = 0;
 
while(interval <= arr.length/3) {
interval = interval*3 +1;                  
}

while(interval > 0) {
System.out.println("iteration #:" + i);
System.out.println(Arrays.toString(arr));

for(outer = interval; outer < arr.length; outer++) {
valueToInsert = arr[outer];
inner = outer;

while(inner > interval -1 && arr[inner - interval]
>= valueToInsert) {
arr[inner] = arr[inner - interval];
inner -=interval;
System.out.println(" item moved: " + arr[inner] + "\n");
}
       
arr[inner] = valueToInsert;
System.out.println(" item inserted :" + valueToInsert + " at position " + inner +"\n");
}

interval = (interval -1) /3;          
i++;
}        
}

public static void main(String[] args) {
// TODO Auto-generated method stub
        Scanner scan = new Scanner( System.in );      
        System.out.println("Shell Sort\n");
        int n, i;
        /* Accept number of elements */
        System.out.println("Enter number of integer elements");
        n = scan.nextInt();
        /* Create integer array on n elements */
        int arr[] = new int[ n ];
        /* Accept elements */
        System.out.println("\nEnter "+ n +" integer elements");
        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        Sort(arr);
        System.out.println("\nElements after sorting ");      
        for (i = 0; i < n; i++)
            System.out.print(arr[i]+" ");          
        System.out.println();    
}

}

MERGE SORT IN JAVA

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

public class MergeSort {

    public static void main(String[] args) throws IOException{
    Scanner scanner = new Scanner(System.in);
        System.out.println("Enter number of elements");
        int size = scanner.nextInt();
        int[] data = new int[size];
        System.out.println("Enter " + size + " integers");
        for (int i = 0; i < size; i++) {
            data[i] = scanner.nextInt();
        }
        Divide(data);

        for (int j = 0; j < data.length; j++) {
            System.out.println(data[j]);
        }

    }

    public static void Divide(int[] A) {
    //divides into two equal halves
        if (A.length > 1) {
            int q = A.length/2;
            int[] leftArray = Arrays.copyOfRange(A, 0, q);
            int[] rightArray = Arrays.copyOfRange(A,q,A.length);
           
            //Logic for recursive division
            Divide(leftArray);
            Divide(rightArray);
            //Combine after every right array division complete
            combine(A,leftArray,rightArray);
        }
    }

    public static void combine(int[] a, int[] l, int[] r) {
        int totallength = l.length + r.length;
        int i, li, ri;
        i = li = ri = 0;
        while ( i < totallength) {
            if ((li < l.length) && (ri < r.length)) {
                if (l[li] < r[ri]) {
                //left array copies
                    a[i] = l[li];
                    i++;
                    li++;
                }
                else {
                //right array copied
                    a[i] = r[ri];
                    i++;
                    ri++;
                }
            }
            else {
                if (li >= l.length) {
                //right array copied
                    while (ri < r.length) {
                        a[i] = r[ri];
                        i++;
                        ri++;
                    }
                }
                if (ri >= r.length) {
                //left array copied
                    while (li < l.length) {
                        a[i] = l[li];
                        li++;
                        i++;
                    }
                }
            }
        }

    }

}

QUICK SORT IN JAVA

import java.util.Arrays;


public class QuickSort {
public static void main(String[] args) {
int[] x = { 9, 2, 4, 7, 3, 7, 10 };
System.out.println(Arrays.toString(x));

int low = 0;
int high = x.length - 1;

quickSort(x, low, high);
System.out.println(Arrays.toString(x));
}

public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return;

if (low >= high)
return;

// pick the pivot
int middle = low + (high - low) / 2;
int pivot = arr[middle];

// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}

while (arr[j] > pivot) {
j--;
}

if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}

// recursively sort two sub parts
if (low < j)
quickSort(arr, low, j);

if (high > i)
quickSort(arr, i, high);
}
}