Java program for heap sort

import java.util.Scanner;

public class HeapSort {

public static void main(String args[]) {

int n;

int num[];

Scanner scan = new Scanner(System.in);

System.out.println("\nEnter the number of elements :");

n = Integer.parseInt(scan.nextLine());

System.out.println("Enter the numbers :");

num = new int[n];

for(int i=0; i<n; i++) {

num[i] = Integer.parseInt(scan.nextLine());

}

for(int i=n; i>1; i--) {

HeapSort(num, i - 1);

}

System.out.println("\nHeap sorted list are");

for(int i=0; i<n; i++) {

System.out.print(" " + num[i]);

}

}

private static void HeapSort(int array[], int bound) {

int left, right, middle, root, temp;

root = (bound-1) / 2;

for(int i=root; i>=0; i--) {

for(int j=root; j>=0; j--) {

left = (2*j) + 1;

right = (2*j) + 2;

if((left <= bound) && (right <= bound)) {

if(array[right] >= array[left])

middle = right;

else

middle = left;

}

else {

if(right > bound)

middle = left;

else

middle = right;

}

if(array[j] < array[middle]) {

temp = array[j];

array[j] = array[middle];

array[middle] = temp;

}

}

}

temp = array[0];

array[0] = array[bound];

array[bound] = temp;

}

}

OUTPUT:-

C:\Users\saty\Desktop>javac HeapSort.java

C:\Users\saty\Desktop>java HeapSort 

Enter the number of elements :

8

Enter the numbers :

45

8

72

34

5

1

9

34

Heap sorted list are

 1 5 8 9 34 34 45 72

Java program for shell sort

import java.util.*;

class ShellSort {

public static void main(String args[]) {

int[] array = new int[] { 56, 25, 4, 1, 14 };

int p, i, j, increment, temp, number_of_elements = array.length;

/* Shell Sort Program */

for (increment = number_of_elements / 2; increment > 0; increment /= 2)

{

for (i = increment; i < number_of_elements; i++)

{

temp = array[i];

for (j = i; j >= increment; j -= increment)

{

if (temp < array[j - increment]) {

array[j] = array[j - increment];

} else {

break;

}

}

array[j] = temp;

}

}

System.out.println("Shell sorted list are:");

for (p = 0; p < 5; p++) {

System.out.println(array[p]);

}

}

}

OUTPUT:-

C:\Users\saty\Desktop>javac ShellSort.java

C:\Users\saty\Desktop>java ShellSort

Shell sorted list are:

1

4

14

25

56

Java program for quick sort

import java.util.*;

public class QuickSort {

public static void main(String[] args) {

int[] x = { 12, 54, 9, 2, 15, 64, 32 };

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;

// take pivot

int middle = low + (high - low) / 2;

int pivot = arr[middle];

// 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);

}

}

OUTPUT:-

C:\Users\saty\Desktop>javac QuickSort.java

C:\Users\saty\Desktop>java QuickSort

[12, 54, 9, 2, 15, 64, 32]

[2, 9, 12, 15, 32, 54, 64]