Tuesday, February 28, 2012

• Read value from a file and sort the values use merge sort and quick sort in java

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