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 bubble() //Bubblesort
{
System.out.print("(bubblesort)\n\n");
display();
for(int i=1;i<n;i++)
for(int j=1;j<=n-i;j++)
if(a[j]>a[j+1])
{
swap(j,j+1);
display();
}
}
public void swap(int x,int y)
{
int temp=a[x];
a[x]=a[y];
a[y]=temp;
}
public void selection() //selectionsort
{
System.out.print("(selectionsort)\n\n");
display();
for(int i=1;i<n;i++)
{
int min=i;
for(int j=i+1;j<=n;j++)
if(a[j]<a[min])
min=j;
swap(i,min);
display();
}
}
public void insertion() //insertionsort
{
System.out.print("(insertionsort)\n\n");
display();
for(int j=2;j<=n;j++)
{
int key=a[j];int i=j-1;
while((i>0)&&(a[i]>key))
{
a[i+1]=a[i];
i--;
}
a[i+1]=key;
display();
}
}
public void quick(int first,int last) //quicksort
{
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);
}
}
public void merge(int low,int high) //mergesort
{
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();
}
public void buildheap() //heapsort
{
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;
}
public void nidhi()
{
System.out.print("\t\t\t\t\t\t* www.2k8618.blogspot.com *\n");
}
public void end()
{
System.out.println("\n\n\t\t\t*** ***\n\t\t\t***** ***\n\t\t\t*** *** ***\n\t\t\t*** *****\n\t\t\t*** ****\n");
System.out.print("\n\t\t<<<<SORTING ALGORITHMS>>>>\n");
char z=177;
System.out.print("\t\t"+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z);
char y=2;
System.out.print("\n\t\t\t @ 2010 - www.2k8618.blogspot.com -\n\t\t2k8618@gmail.com,S4-CSE,GCEK\n");
for(int x=1;x<=75;x++)
System.out.print(""+y);
System.out.print("\n");
}
}
class nsort
{
public static void main(String arg[]) throws IOException
{
int exit=1;arraylist ob;
System.out.println("\n\n\t\t\t*** ***\n\t\t\t***** ***\n\t\t\t*** *** ***\n\t\t\t*** *****\n\t\t\t*** ****\n");
System.out.print("\n\t\t<<<<SORTING ALGORITHMS>>>>\n");
char z=177;
System.out.print("\t\t"+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z);
do{
DataInputStream x1= new DataInputStream(System.in);
System.out.print("\nEnter the number of elements:");
int na=Integer.parseInt(x1.readLine());
ob=new arraylist(na+1);
System.out.println("Enter the elements:");
for (int k=1;k<=na;k++)
ob.insert(Integer.parseInt(x1.readLine()));
ob.nidhi();
System.out.println("Before sorting:\n");
ob.display();
System.out.println("Enter your choice:\n\n\t1.BUBBLESORT\n\t\t2.SELECTIONSORT\n\t\t\t3.INSERTIONSORT\t\n\t4.QUICKSORT\n\t\t5.MERGESORT\n\t\t\t6.HEAPSORT\t\t*www.2k8618.blogspot.com*\n\t\t\t\t\t7.Exit>>>\n");
int turn=Integer.parseInt(x1.readLine());
if(turn>=1 && turn <=6)
System.out.println("Sorting.............");
ob.nidhi();
switch(turn)
{
case 1:
ob.bubble();
System.out.println("After sorting:\n");
break;
case 2:
ob.selection();
System.out.println("After sorting:\n");
break;
case 3:
ob.insertion();
System.out.println("After sorting:\n");
break;
case 4:
System.out.print("(QuickSort)\n\n");
ob.display();
ob.quick(1,na);
System.out.println("After sorting:\n");
break;
case 5:
System.out.print("(MergeSort)\n\n");
ob.display();
ob.merge(1,na);
System.out.println("After sorting:\n");
break;
case 6:
System.out.print("(HeapSort)\n\n");
ob.display();
ob.heapsort();
System.out.println("After sorting:\n");
break;
case 7:
exit=0;
System.out.println("Not sorted:\n");
break;
default:
System.out.println("Not sorted:\n");
break;
}
ob.display();ob.nidhi();
System.out.println("\nPress 1 to continue...");
exit=Integer.parseInt(x1.readLine());
}while(exit==1);
ob.end();
}
}
Output:
nn@linuxmint ~ $ javac nsort.java
Note: nsort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java nsort
*** ***
***** ***
*** *** ***
*** *****
*** ****
<<<<SORTING ALGORITHMS>>>>
±±±±±±±±±±±±±±±±±±±±±±±±±±
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
1
Sorting.............
* www.2k8618.blogspot.com *
(bubblesort)
5 4 3 2 1
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5
After sorting:
1 2 3 4 5
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
2
Sorting.............
* www.2k8618.blogspot.com *
(selectionsort)
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
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
3
Sorting.............
* www.2k8618.blogspot.com *
(insertionsort)
5 4 3 2 1
4 5 3 2 1
3 4 5 2 1
2 3 4 5 1
1 2 3 4 5
After sorting:
1 2 3 4 5
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
4
Sorting.............
* www.2k8618.blogspot.com *
(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
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
5
Sorting.............
* www.2k8618.blogspot.com *
(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
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
6
Sorting.............
* www.2k8618.blogspot.com *
(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
* www.2k8618.blogspot.com *
Press 1 to continue...
2
*** ***
***** ***
*** *** ***
*** *****
*** ****
<<<<SORTING ALGORITHMS>>>>
±±±±±±±±±±±±±±±±±±±±±±±±±±
@ 2010 - www.2k8618.blogspot.com -
2k8618@gmail.com,S4-CSE,GCEK
nn@linuxmint ~ $
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 bubble() //Bubblesort
{
System.out.print("(bubblesort)\n\n");
display();
for(int i=1;i<n;i++)
for(int j=1;j<=n-i;j++)
if(a[j]>a[j+1])
{
swap(j,j+1);
display();
}
}
public void swap(int x,int y)
{
int temp=a[x];
a[x]=a[y];
a[y]=temp;
}
public void selection() //selectionsort
{
System.out.print("(selectionsort)\n\n");
display();
for(int i=1;i<n;i++)
{
int min=i;
for(int j=i+1;j<=n;j++)
if(a[j]<a[min])
min=j;
swap(i,min);
display();
}
}
public void insertion() //insertionsort
{
System.out.print("(insertionsort)\n\n");
display();
for(int j=2;j<=n;j++)
{
int key=a[j];int i=j-1;
while((i>0)&&(a[i]>key))
{
a[i+1]=a[i];
i--;
}
a[i+1]=key;
display();
}
}
public void quick(int first,int last) //quicksort
{
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);
}
}
public void merge(int low,int high) //mergesort
{
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();
}
public void buildheap() //heapsort
{
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;
}
public void nidhi()
{
System.out.print("\t\t\t\t\t\t* www.2k8618.blogspot.com *\n");
}
public void end()
{
System.out.println("\n\n\t\t\t*** ***\n\t\t\t***** ***\n\t\t\t*** *** ***\n\t\t\t*** *****\n\t\t\t*** ****\n");
System.out.print("\n\t\t<<<<SORTING ALGORITHMS>>>>\n");
char z=177;
System.out.print("\t\t"+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z);
char y=2;
System.out.print("\n\t\t\t @ 2010 - www.2k8618.blogspot.com -\n\t\t2k8618@gmail.com,S4-CSE,GCEK\n");
for(int x=1;x<=75;x++)
System.out.print(""+y);
System.out.print("\n");
}
}
class nsort
{
public static void main(String arg[]) throws IOException
{
int exit=1;arraylist ob;
System.out.println("\n\n\t\t\t*** ***\n\t\t\t***** ***\n\t\t\t*** *** ***\n\t\t\t*** *****\n\t\t\t*** ****\n");
System.out.print("\n\t\t<<<<SORTING ALGORITHMS>>>>\n");
char z=177;
System.out.print("\t\t"+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z+z);
do{
DataInputStream x1= new DataInputStream(System.in);
System.out.print("\nEnter the number of elements:");
int na=Integer.parseInt(x1.readLine());
ob=new arraylist(na+1);
System.out.println("Enter the elements:");
for (int k=1;k<=na;k++)
ob.insert(Integer.parseInt(x1.readLine()));
ob.nidhi();
System.out.println("Before sorting:\n");
ob.display();
System.out.println("Enter your choice:\n\n\t1.BUBBLESORT\n\t\t2.SELECTIONSORT\n\t\t\t3.INSERTIONSORT\t\n\t4.QUICKSORT\n\t\t5.MERGESORT\n\t\t\t6.HEAPSORT\t\t*www.2k8618.blogspot.com*\n\t\t\t\t\t7.Exit>>>\n");
int turn=Integer.parseInt(x1.readLine());
if(turn>=1 && turn <=6)
System.out.println("Sorting.............");
ob.nidhi();
switch(turn)
{
case 1:
ob.bubble();
System.out.println("After sorting:\n");
break;
case 2:
ob.selection();
System.out.println("After sorting:\n");
break;
case 3:
ob.insertion();
System.out.println("After sorting:\n");
break;
case 4:
System.out.print("(QuickSort)\n\n");
ob.display();
ob.quick(1,na);
System.out.println("After sorting:\n");
break;
case 5:
System.out.print("(MergeSort)\n\n");
ob.display();
ob.merge(1,na);
System.out.println("After sorting:\n");
break;
case 6:
System.out.print("(HeapSort)\n\n");
ob.display();
ob.heapsort();
System.out.println("After sorting:\n");
break;
case 7:
exit=0;
System.out.println("Not sorted:\n");
break;
default:
System.out.println("Not sorted:\n");
break;
}
ob.display();ob.nidhi();
System.out.println("\nPress 1 to continue...");
exit=Integer.parseInt(x1.readLine());
}while(exit==1);
ob.end();
}
}
Output:
nn@linuxmint ~ $ javac nsort.java
Note: nsort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java nsort
*** ***
***** ***
*** *** ***
*** *****
*** ****
<<<<SORTING ALGORITHMS>>>>
±±±±±±±±±±±±±±±±±±±±±±±±±±
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
1
Sorting.............
* www.2k8618.blogspot.com *
(bubblesort)
5 4 3 2 1
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5
After sorting:
1 2 3 4 5
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
2
Sorting.............
* www.2k8618.blogspot.com *
(selectionsort)
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
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
3
Sorting.............
* www.2k8618.blogspot.com *
(insertionsort)
5 4 3 2 1
4 5 3 2 1
3 4 5 2 1
2 3 4 5 1
1 2 3 4 5
After sorting:
1 2 3 4 5
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
4
Sorting.............
* www.2k8618.blogspot.com *
(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
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
5
Sorting.............
* www.2k8618.blogspot.com *
(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
* www.2k8618.blogspot.com *
Press 1 to continue...
1
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
* www.2k8618.blogspot.com *
Before sorting:
5 4 3 2 1
Enter your choice:
1.BUBBLESORT
2.SELECTIONSORT
3.INSERTIONSORT
4.QUICKSORT
5.MERGESORT
6.HEAPSORT *www.2k8618.blogspot.com*
7.Exit>>>
6
Sorting.............
* www.2k8618.blogspot.com *
(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
* www.2k8618.blogspot.com *
Press 1 to continue...
2
*** ***
***** ***
*** *** ***
*** *****
*** ****
<<<<SORTING ALGORITHMS>>>>
±±±±±±±±±±±±±±±±±±±±±±±±±±
@ 2010 - www.2k8618.blogspot.com -
2k8618@gmail.com,S4-CSE,GCEK
nn@linuxmint ~ $
0 comments:
Post a Comment