ELECTRICAL NOTES -BRIDGES-S4

Heapsort - Sorting Algorithm - JAVA

Program:
import java.io.*;
class arraylist
{
    private int[] a;
    private int n;
    private int[] temp;
    public arraylist(int x)
    {
        a = new int[x];
        n=0;
        temp = new int[x];
    }
    public void insert(int e)
    {
        n++;
        a[n]=e;
    }
    public void display()
    {
        for(int i=1;i<=n;i++)
        System.out.print(a[i]+" ");
        System.out.println("\n");
    }
    public void swap(int x,int y)
    {
            int temp=a[x];
            a[x]=a[y];
            a[y]=temp;
    }
    public void buildheap()
    {
        for(int i=n/2;i>=1;i--)
        maxheapify(n,i);
    }
    public void maxheapify(int n,int i)
    {
        int largest;
        int l=left(i);
        int r=right(i);
        if(l<=n&&a[l]>a[i])
            largest=l;
        else
            largest=i;
        if(r<=n&&a[r]>a[largest])
            largest=r;
        if(largest!=i)
        {
            swap(i,largest);
            maxheapify(n,largest);
        }
    }
    public void heapsort()
    {
        buildheap();
        int heapsize=n;
        for(int i=heapsize;i>=2;i--)
        {
            swap(i,1);
            display();
            heapsize--;
            maxheapify(heapsize,1);
        }
    }
    public int left(int a)
    {
        return 2*a;
    }
    public int right(int b)
    {
        return 2*b+1;
    }
   
}

class heapsort
{
    public static void main(String arg[]) throws IOException
    {
        DataInputStream x1= new DataInputStream(System.in);
       
        System.out.print("\nEnter the number of elements:");
        int na=Integer.parseInt(x1.readLine());
        arraylist ob=new arraylist(na+1);
        System.out.println("Enter the elements:");
        for (int k=1;k<=na;k++)
                ob.insert(Integer.parseInt(x1.readLine()));
       
        System.out.println("Before sorting:\n");
        ob.display();
        System.out.println("Sorting.............");
        System.out.print("(HeapSort)\n\n");
            ob.display();ob.heapsort();
        System.out.println("After sorting:\n");
        ob.display();
    }
}

Output:
nn@linuxmint ~ $ javac heapsort.java
Note: heapsort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java heapsort

Enter the number of elements:5
Enter the elements:
5
4
3
2
1
Before sorting:

5 4 3 2 1

Sorting.............
(HeapSort)

5 4 3 2 1

1 4 3 2 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

After sorting:

1 2 3 4 5

nn@linuxmint ~ $

Mergesort - Sorting Algorithm - JAVA

Program:

import java.io.*;
class arraylist
{
    private int[] a;
    private int n;
    private int[] temp;
    public arraylist(int x)
    {
        a = new int[x];
        n=0;
        temp = new int[x];
    }
    public void insert(int e)
    {
        n++;
        a[n]=e;
    }
    public void display()
    {
        for(int i=1;i<=n;i++)
        System.out.print(a[i]+" ");
        System.out.println("\n");
    }
    public void merge(int low,int high)
    {
        if(low!=high)
        {
            int mid=(low+high)/2;
            merge(low,mid);
            merge(mid+1,high);
            rmerge(low,mid,high);
        }
    }
    public void rmerge(int low,int mid,int high)
    {
       
        int i=low;int j=mid+1;int k=low;
       
        while((i<=mid)&&(j<=high))
        {
            if(a[i]<=a[j])
                {
                    temp[k]=a[i];k++;i++;
                }
            else
                {
                    temp[k]=a[j];k++;j++;
                }
        }
        while(i<=mid)
        {
            temp[k]=a[i];k++;i++;
        }
        while(j<=high)
        {
            temp[k]=a[j];k++;j++;
        }
        for(i=1;i<=high;i++)
            a[i]=temp[i];
            display();

    }
   

}

class mergesort
{
    public static void main(String arg[]) throws IOException
    {
        DataInputStream x1= new DataInputStream(System.in);
       
        System.out.print("\nEnter the number of elements:");
        int na=Integer.parseInt(x1.readLine());
        arraylist ob=new arraylist(na+1);
        System.out.println("Enter the elements:");
        for (int k=1;k<=na;k++)
                ob.insert(Integer.parseInt(x1.readLine()));
        System.out.println("Before sorting:\n");
        ob.display();
        System.out.println("Sorting.............");
        System.out.print("(MergeSort)\n\n");
        ob.display();
        ob.merge(1,na);
        System.out.println("After sorting:\n");
        ob.display();
    }
}

Output:
nn@linuxmint ~ $ javac mergesort.java
Note: mergesort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java mergesort

Enter the number of elements:5
Enter the elements:
5
4
3
2
1
Before sorting:

5 4 3 2 1

Sorting.............
(MergeSort)

5 4 3 2 1

4 5 3 2 1

3 4 5 2 1

3 4 5 1 2

1 2 3 4 5

After sorting:

1 2 3 4 5

nn@linuxmint ~ $

Quicksort - Sorting Algorithm - JAVA

Program:

import java.io.*;
class arraylist
{
    private int[] a;
    private int n;
    private int[] temp;
    public arraylist(int x)
    {
        a = new int[x];
        n=0;
        temp = new int[x];
    }
    public void insert(int e)
    {
        n++;
        a[n]=e;
    }
    public void display()
    {
        for(int i=1;i<=n;i++)
        System.out.print(a[i]+" ");
        System.out.println("\n");
    }
    public void swap(int x,int y)
    {
            int temp=a[x];
            a[x]=a[y];
            a[y]=temp;
    }
    public void quick(int first,int last)
    {      
        if(last>first)
        {
            int i=first;int j=last+1;int pivot=a[first];
            do
            {
                do{
                    i=i+1;
                  }while((a[i]<=pivot)&&(i<last));
                do{
                    j=j-1;  
                  }while((a[j]>=pivot)&&(j>first));
                  
                if(i<j)
                {  
                  
                    swap(i,j);
                    display();
                }
            }while(i<j);
            swap(first,j);
            display();
            quick(first,j-1);
            quick(j+1,last);
        }
    }
  

}

class quicksort
{
    public static void main(String arg[]) throws IOException
    {
        DataInputStream x1= new DataInputStream(System.in);
      
        System.out.print("\nEnter the number of elements:");
        int na=Integer.parseInt(x1.readLine());
        arraylist ob=new arraylist(na+1);
        System.out.println("Enter the elements:");
        for (int k=1;k<=na;k++)
                ob.insert(Integer.parseInt(x1.readLine()));
      
        System.out.println("Before sorting:\n");
        ob.display();
        System.out.println("Sorting.............");
        System.out.print("(QuickSort)\n\n");
        ob.display();
        ob.quick(1,na);
        System.out.println("After sorting:\n");
        ob.display();
    }
}

Output:
nn@linuxmint ~ $ javac quicksort.java
Note: quicksort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java quicksort

Enter the number of elements:5
Enter the elements:
5
4
3
2
1
Before sorting:

5 4 3 2 1

Sorting.............
(QuickSort)

5 4 3 2 1

1 4 3 2 5

1 4 3 2 5

1 2 3 4 5

1 2 3 4 5

After sorting:

1 2 3 4 5

nn@linuxmint ~ $