import java.io.*;
import java.util.*;
public class Arraysort{
int[] list;
int n;
public Arraysort(int n){
this.n=n;
list=new int[n];
}
public void Mergesort(){
System.out.println("merge sort");
mergesort(0,n-1);
print();
}
public void QuickSort(){
System.out.println("Quick sort");
quickSort(0,n-1);
print();
}
public void readFile() throws IOException{
Scanner filesean=new Scanner(new FileReader("inputtext.txt"));
int i=0;
while(filesean.hasNext() && i<n){
list[i]=filesean.nextInt();
i++;
}
System.out.println("input array");
for(int j=0;j<n;j++){
System.out.print(list[j]+" ");
}
System.out.println();
filesean.close();
}
public void mergesort(int l,int r){
if(l<r){
int mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
merge(l,mid,r);
}
}
private void merge(int l, int m, int r) {
int i=l; int j=m+1; int k=0;
int[] temp=new int[r-l+1];
while(i<=m && j<=r){
if(list[i]<list[j])temp[k++]=list[i++];
else temp[k++]=list[j++];
}
while(i<=m) temp[k++]=list[i++];
while(j<=r) temp[k++]=list[j++];
for(k=0;k<r-l+1;k++) list[l+k]=temp[k];
}
public void quickSort(int p,int q){
int j;
if(p<q){
j=partition(p,q);
quickSort(p,j-1);
quickSort(j+1,q);
}
}
private int partition(int p, int q) {
int i=p;
int j=q+1;
int pivot=list[p];
do{
do{ i++;
}while(list[i]<pivot);
do{j--;
}while(list[j]>pivot);
if(i<j){
swap(i,j);}
}while(i<j);
swap(p,j);
return j;
}
private void swap(int i, int i0){
int temp=list[i];
list[i]=list[i0];
list[i0]=temp;
}
public void print(){
for(int j=0;j<n;j++){
System.out.print(list[j]+" ");
}
System.out.println();
}
public static void main(String[] args) throws IOException{
Arraysort s=new Arraysort(15);
s.readFile();
s.Mergesort();
System.out.println();
s.QuickSort();
}
}
/* Output
input array
1 5 3 2 6 4 9 1 6 8 22 78 25 46 11
merge sort
1 1 2 3 4 5 6 6 8 9 11 22 25 46 78
Quick sort
1 1 2 3 4 5 6 6 8 9 11 22 25 46 78
*/
No comments:
Post a Comment