Question

Implement the following sorting algorithms using Java: a. Heap Sort. b. Quick Sort. c. Radix Sort. Verify the correctness of each implemented algorithm by sorting the following array: 10, 5, 60, 53, 45, 3, 25,37,39,48

Answer 1

Solution :

I have taken your example in my output.

a)HEAP SORT:

• It is a comparison based sorting technique
• It is based on Binary Heap data structure.

Heap Sort Algorithm :
1. Build max heap from input data.
2. Now,the largest item is present at root of the heap. Replace it with the last node of heap then reduce size of heap by Then,heapify the root of tree.
3. Repeat above steps while size of heap is greater than 1.

Screenshot:

- o F:\Computer Networking\EXTRA Difference between Virus, Worm and Trojan Horse (with Comparison Chart) - Tech Differences_files\Main.java - Sublime Text (UNREGISTERED) File Edit Selection Find View Goto Tools Project Preferences Help quick_sort.java . Main.java import java.util.Scanner; public class Main{ static void heapify(int all, int n, int i) { int largest-i; // Initialize largest as root int 1=2 i+1; // left = 2*i + 1 int r=2 i+2; // right = 2 i + 2 if(l<n && a[1]>a[largest]) // If left child is larger than root largest=1; if(r<n && a[c]>a[largest]) // If right child is larger than largest so far largest=r; if(largest !=i) { // If largest is not root int swap-a[i]; a[i]=a[largest]; a[largest]=swap; heapify(a,n, largest); // Recursively heapify the affected sub-tree static void sort(int a[]){ int n=a.length; int i; for(i=n/2-1;i>= 0;i--) // Build heap heapify(a,n,i); for(i=n-1;i>=0;i--){ // One by one extract an element from heap then Move current root to end int temp=a[0]; a[@]=a[i]; a[i]=temp; heapify(a,i,o); // call max heapify on the reduced heap static void print_array(int a[]){ int n=a.length; for (int i=0;i<n; ++i) System.out.print(a[i]+" "); System.out.println(); Line 15, Column 79 Tab Size: 4 1 Type here to search Java 19:03 12-02-202020 12 ANO A 2 ENG

- o F:\Computer Networking\EXTRA Difference between Virus, Worm and Trojan Horse (with Comparison Chart) - Tech Differences_files\Main.java.- Sublime Text (UNREGISTERED) File Edit Selection Find View Goto Tools Project Preferences Help quick_sort.java . Main.java static void sort(int a[]){ int n=a.length; int i; for(i=n/2-1;i>= 0;i--) // Build heap heapify(a,n,i); for(i=n-1;i>=0;i--){ // One by one extract an element from heap then Move current root to end int temp=a[@]; a[@]=a[i]; a[i]=temp; heapify(a,i,o); // call max heapify on the reduced heap static void print_array(int a[]){ int n=a.length; for (int i=0;i<n; ++i) System.out.print(a[i]+" "); System.out.println(); public static void main(String args[]) { int n; Scanner sc=new Scanner(System.in); System.out.print("Enter no. of elements you want in array:"); n=sc.nextInt(); int a[] = new int[n]; System.out.println("Enter all the elements:"); for(int i=0;i<n;i++){ a[i]=sc.nextInt(); sort(a); System.out.print("sorted array: "); print_array(a); 50 ] O Line 50, Column 2 Tab Size: 4 1 Type here to search Java 19:03 12-02-202020 A O / 2 ENG

Output:

input Enter no. of elements you want in array:10 Enter all the elements: 10 5 60 53 45 3 25 37 39 48 sorted array : 3 5 10 25 37 39 45 48 53 60 ... Program finished with exit code o Press ENTER to exit console.]

Code :

import java.util.Scanner;
public class Main{
static void heapify(int a[],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(l<n && a[l]>a[largest]) // If left child is larger than root
           largest=l;
       if(r<n && a[r]>a[largest]) // If right child is larger than largest so far
           largest=r;
       if(largest!=i){ // If largest is not root
           int swap=a[i];
           a[i]=a[largest];
           a[largest]=swap;
           heapify(a,n,largest); // Recursively heapify the affected sub-tree
       }
   }
   static void sort(int a[]){
       int n=a.length;
       int i;
       for(i=n/2-1;i>= 0;i--) // Build heap
           heapify(a,n,i);
       for(i=n-1;i>=0;i--){ // One by one extract an element from heap then Move current root to end
           int temp=a[0];
           a[0]=a[i];
           a[i]=temp;
           heapify(a,i,0); // call max heapify on the reduced heap
       }
   }
   static void print_array(int a[]){
       int n=a.length;
       for (int i=0;i<n;++i)
           System.out.print(a[i]+" ");
       System.out.println();
   }
   public static void main(String args[]){
int n;
Scanner sc=new Scanner(System.in);
System.out.print("Enter no. of elements you want in array:");
n=sc.nextInt();
int a[] = new int[n];
System.out.println("Enter all the elements:");
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
       sort(a);
       System.out.print("sorted array : ");
       print_array(a);
   }
}

-------------------------------------------------------------------------------

b)QUICK SORT :

• It is a Divide and Conquer algorithm.
• It choose an element as pivot & partitions given array around the pivot.
• The key process in quickSort is partition().

Screenshot :

F:\Computer Networking\EXTRA Difference between Virus, Worm and Trojan Horse (with Comparison Chart) - Tech Differences_files\Main.java - Sublime Text (UNREGISTERED) File Edit Selection Find View Goto Tools Project Preferences Help 1 quick_sort.java . Main.java import java.util.Scanner; class Main{ static int partition(int a[], int Low, int high) { int j; int pivot=a[high]; int i=low-1; for(j=low;j<high; j++){ if(a[j]<pivot){ i++; int temp=a[i]; a[i]=a[j]; a[j]-temp; int temp=a[i+1]; a[i+1]=a[high); a[high]=temp; return i+1; static void sort(int a[], int Low, int high) { if(low<high) { int pi-partition(a, low, high); sort(a,low,pi-1); sort(a,pi+1, high); static void print_array(int a[]){ int i; int n=a.length; for(i=0;i<n; ++i) System.out.print(a[i]+" "); System.out.println(); public static void main(String args[]) { int n; Line 52, Column 1 O Tab Size: 4 Java 19:12 12-02-202020 2 Type here to search A O A 3 ENG

3 Computer Networking\EXTRA Difference between Virus, Worm and Trojan Horse (with Comparison Chart) - Tech Differences_files\Main.java - Sublime Text (UNREGISTERED) File Edit Selection Find View Goto Tools Project Preferences Help quick_sort.java Main.java int temp=a[i+1]; a[i+1]=a[high]; a[high]-temp; return i+1; static void sort(int a[], int Low, int high) { if(low<high) { int pi=partition(a,low, high); sort(a,low,pi-1); sort(a, pi+1, high); static void print_array(int a[]){ int i; int n=a.length; for(i=0;i<n; ++i) System.out.print(a[i]+" "); System.out.println(; public static void main(String args[]) { int n; Scanner sc=new Scanner(System.in); System.out.print("Enter no. of elements you want in array:"); n=sc.nextInt(); int a[] = new int[n]; System.out.println("Enter all the elements:"); for(int i=0;i<n;i++){ a[i]=sc.nextInt(); sort(a, a, n-1); System.out.print("sorted array: "); print_array(a); 48 } Line 48, Column 2 Tab Size: 4 Java 19:12 12-02-202020 2 Type here to search A O A 3 ENG

Output :

input Enter no. of elements you want in array:10 Enter all the elements: 10 5 60 53 45 3 25 37 39 48 sorted array : 3 5 10 25 37 39 45 48 53 60 ... Program finished with exit code o Press ENTER to exit console.]

Code :

import java.util.Scanner;
class Main{
   static int partition(int a[],int low,int high){
       int j;
       int pivot=a[high];
       int i=low-1;
       for(j=low;j<high;j++){
           if(a[j]<pivot){
           i++;
               int temp=a[i];
               a[i]=a[j];
               a[j]=temp;
           }
       }
       int temp=a[i+1];
       a[i+1]=a[high];
       a[high]=temp;
       return i+1;
   }
   static void sort(int a[],int low,int high){
       if(low<high){
           int pi=partition(a,low,high);
           sort(a,low,pi-1);
           sort(a,pi+1,high);
       }
   }
   static void print_array(int a[]){
       int i;
       int n=a.length;
       for(i=0;i<n;++i)
           System.out.print(a[i]+" ");
       System.out.println();
   }
   public static void main(String args[]){
int n;
Scanner sc=new Scanner(System.in);
System.out.print("Enter no. of elements you want in array:");
n=sc.nextInt();
int a[] = new int[n];
System.out.println("Enter all the elements:");
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
       sort(a, 0, n-1);
       System.out.print("sorted array : ");
       print_array(a);
   }
}

------------------------------------------------------------------------------------

c)RADIX SORT :

• Radix Sort sort an array in linear time.
• It uses counting sort as subroutine to sort.

Screenshot:

F:\Computer Networking\EXTRA Difference between Virus, Worm and Trojan Horse (with Comparison Chart) - Tech Differences_files\Main.java - Sublime Text (UNREGISTERED) File Edit Selection Find View Goto Tools Project Preferences Help 1 //function to get maximum value in array quick_sort.java . Main.java import java.io.*; import java.util.*; class Main static int getMax(int a[], int n){ int max=a[@]; int i; for(i=1;i<n;i++) if(a[i]>max) max=a[i]; return max; static void countSort(int a[], int n, int exp) { //function to do counting sort of array int output[]=new int[n]; // output array int i; int count[]=new int[10]; Arrays.fill(count,); for(i=0;i<n;i++) // Store count of occurrences in count[] count[(a[i]/exp)%10]++; //Change count[i] so that count[i] contains actual position of digit in output[] for(i=1;i<10; i++) count[i]+=count[i-1]; for (i = n - 1; i >= 0; i--){ // Build the output array output[count[ (a[i]/exp)%10 ] - 1] = a[i]; count[ (a[i]/exp) %10 ]--; //Copy the output array to arrll for(i=0;i<n;i++) a[i]=output[i]; static void sort(int a[], int n){ int m=getMax(a,n); //Find maximum to know number of digits for (int exp = 1; m/exp > 0; exp*= 10) // Do counting sort for every digit countSort(a,n, exp); static void print_array(int a[]){ int n = a.length; Line 53, Column 2 O Tab Size: 4 Java 19:19 12-02-202020 2 1 Type here to search A O A 3 ENG

F:\Computer Networking\EXTRA Difference between Virus, Worm and Trojan Horse (with Comparison Chart) - Tech Differences_files\Main.java. - Sublime Text (UNREGISTERED) File Edit Selection Find View Goto Tools Project Preferences Help quick_sort.java Main.java //Change count[i] so that count[i] contains actual position of digit in output[] for(i=1;i<10;1/1) so that count [47 count[i]+=count[i-1]; for (i = n - 1; i >= 0; i--){ // Build the output array output[count[ (a[i]/exp)%10 ] - 1] = a[i]; count[ (a[i]/exp) 10 ]--; for(i=0;i<n;i++) a[i]=output[i]; //Copy the output array to arr[] static void sort(int a[], int n){ int m=getMax(a,n); //Find maximum to know number of digits for (int exp = 1; m/exp > 0; exp *= 10) // Do counting sort for every digit countSort(a,n, exp); static void print_array(int a[]){ int n = a.length; for(int i=0; i<n; i++) System.out.print(a[i]+" "); public static void main(String args[]){ int n; Scanner sc=new Scanner(System.in); System.out.print("Enter no. of elements you want in array:"); n=sc.nextInt(); int a[] = new int[n]; System.out.println("Enter all the elements:"); for(int i=0;i<n;i++){ a[i]=sc.nextInt(); sort(a,n); System.out.print("sorted array: "); print_array(a); 53 O Line 53, Column 2 Tab Size: 4 1 Type here to search Java 19:19 12-02-202020 2 A O A 3 ENG

OUTPUT:

input Enter no. of elements you want in array:10 Enter all the elements: 10 5 60 53 45 3 25 37 39 48 sorted array : 3 5 10 25 37 39 45 48 53 60 ... Program finished with exit code o Press ENTER to exit console.]

CODE :
import java.io.*;
import java.util.*;
class Main{
   static int getMax(int a[],int n){ //function to get maximum value in array
       int max=a[0];
       int i;
       for(i=1;i<n;i++)
           if(a[i]>max)
               max=a[i];
       return max;
   }
   static void countSort(int a[],int n,int exp){ //function to do counting sort of array
       int output[]=new int[n]; // output array
       int i;
       int count[]=new int[10];
       Arrays.fill(count,0);
       for(i=0;i<n;i++) // Store count of occurrences in count[]
           count[(a[i]/exp)%10]++;
       //Change count[i] so that count[i] contains actual position of digit in output[]
       for(i=1;i<10;i++)
           count[i]+=count[i-1];
       for (i = n - 1; i >= 0; i--){ // Build the output array
           output[count[ (a[i]/exp)%10 ] - 1] = a[i];
           count[ (a[i]/exp)%10 ]--;
       }
       for(i=0;i<n;i++) //Copy the output array to arr[]
           a[i]=output[i];
   }
   static void sort(int a[],int n){
       int m=getMax(a,n); //Find maximum to know number of digits
       for (int exp = 1; m/exp > 0; exp *= 10) // Do counting sort for every digit
           countSort(a,n,exp);
   }
   static void print_array(int a[]){
   int n = a.length;
       for(int i=0; i<n; i++)
           System.out.print(a[i]+" ");
   }
public static void main(String args[]){
int n;
Scanner sc=new Scanner(System.in);
System.out.print("Enter no. of elements you want in array:");
n=sc.nextInt();
int a[] = new int[n];
System.out.println("Enter all the elements:");
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
       sort(a,n);
       System.out.print("sorted array : ");
       print_array(a);
   }
}

-------------------------------------------------------------

PLEASE GIVE YOUR VALUABLE FEEDBACK AND ALSO RATE MY EFFORTS.

THANK YOU