Read values from a file and Sort the numbers using merge sort and quick sort algorithm in Java

Posted By: Java Examples - 9:34 PM

Share

& Comment


Merge sort algorithm

1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Otherwise, divide the unsorted list into 2 lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, combine (merge) both the lists back into one sorted list. 


Sort the numbers using merge sort algorithm :
package sort;

import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class ArrayQuickSort {
 int array[];
 int size;

 public ArrayQuickSort(int n) {
  size = n;
  // create array with size n+1
  array = new int[n + 1];
  // set the last element as big value
  array[n] = 99999;

 }

 public void readFile() throws IOException {
  Scanner filescan = new Scanner(new FileReader("input.txt"));
  int i = 0;
  while (filescan.hasNext() && i < size) {
   array[i] = filescan.nextInt();
   i++;
  }
  System.out.println("The Array of Element are :");
  for (int j = 0; j < size; j++) {
   System.out.print(array[j] + " ");

   filescan.close();
  }
  System.out.println();
 }

 public int partition(int p, int q) {
  int i = p;
  int j = q + 1;
  // Get the pivot element from the middle of the list
  int pivot = array[p];
  // Divide into two lists
  do {
   // If the current value from the left list is smaller then the pivot
   // element then get the next element from the left list
   do {
    i++;// As we not get we can increase i
   } while (array[i] < pivot);
   // If the current value from the right list is larger then the pivot
   // element then get the next element from the right list
   do {
    j--;// As we not get we can increase j
   } while (array[j] > pivot);
   // If we have found a values in the left list which is larger then
   // the pivot element and if we have found a value in the right list
   // which is smaller then the pivot element then we exchange the
   // values.
   if (i < j) {
    swap(i, j);
   }

  } while (i < j);
  // swap the pivot element and j th element
  swap(p, j);
  return j;
 }

 private void swap(int p, int j) {
  // exchange the elements
  int temp = array[p];
  array[p] = array[j];
  array[j] = temp;
 }

 public void quicksort() {
  // Recursion
  quicksort(0, size - 1);
 }

 public void quicksort(int p, int q) {
  int j;
  if (p < q) {
   // Divide into two lists
   j = partition(p, q);
   // Recursion
   quicksort(p, j - 1);
   quicksort(j + 1, q);
  }
 }

 public void print() {
  // print the elements of array
  for (int i = 0; i < size; i++) {
   System.out.print(array[i] + " | ");
  }
  System.out.println();

 }

 public static void main(String args[]) throws IOException {
  ArrayQuickSort q = new ArrayQuickSort(15);
  q.readFile();
  System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
  q.print();
  q.quicksort();
  System.out.println("After Sort > > > > > > > > > > > >");
  q.print();

 }
}
/****************************************************************************
 * Output of this program 
 * The Array of Element are : 66 83 65 19 50 92 90 72 71 19 54 37 84 95 14 
 * Before Sort <<<<<<<<<<<<<<<<<<<<<
 *  66 | 83 | 65 | 19 | 50 |92 | 90 | 72 | 71 | 19 | 54 | 37 | 84 | 95 | 14 | 
 * After Sort > > > > > > > > > > > >
 *  14 | 19 | 19 | 37 | 50 | 54 | 65 | 66 | 71 | 72 | 83 | 84 | 90 | 92 |95 |
 ****************************************************************************/

Sort the numbers using quick sort algorithm :
package sort;

import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

import java.util.Scanner;

public class ArrayMergeSort {

 int array[];
 int size;

 public ArrayMergeSort(int n) {
  array = new int[n];
  this.size = n;

 }

 private int getSize() {
  return size;
 }

 public void readFile() throws IOException {
  Scanner filescan = new Scanner(new FileReader("input.txt"));
  int i = 0;
  while (filescan.hasNext() && i < size) {
   array[i] = filescan.nextInt();
   i++;
  }
  System.out.println("The Array of Element are :");
  for (int j = 0; j < size; j++) {
   System.out.print(array[j] + " ");
   
   filescan.close();
  }
  System.out.println();
  
 }

 // merge sort start here
 public void merge(int left, int mid, int right) {
  int temp[] = new int[right - left + 1];
  int i = left;
  int j = mid + 1;
  int k = 0;
  while (i <= mid && j <= right) {
   if (array[i] <= array[j]) {
    temp[k] = array[i];
    k++;
    i++;
   } else {
    // array[i]>array[j]

    temp[k] = array[j];
    k++;
    j++;
   }
  }
  while (j <= right)
   temp[k++] = array[j++];
  while (i <= mid)
   temp[k++] = array[i++];

  for (k = 0; k < temp.length; k++)
   array[left + k] = temp[k];
  
 }

 public void merge_sort(int left, int right) {
  // Check if low is smaller then high, if not then the array is sorted
  if (left < right) {
   // Get the index of the element which is in the middle
   int mid = (left + right) / 2;
   // Sort the left side of the array
   merge_sort(left, mid);
   // Sort the right side of the array
   merge_sort(mid + 1, right);
   // Combine them both
   merge(left, mid, right);
  }

 }
public void MergeSort(){
 merge_sort(0, getSize() - 1);
 
 
}
 // merge sort end here

 public void print(){
  
  System.out.println("Contents of the Array");
  for (int k = 0; k < size; k++) {
   System.out.print(array[k] + " | ");
  }
  System.out.println();

 }

 public void WriteFile() throws IOException {
  PrintWriter fout = new PrintWriter(new FileWriter("Out.txt"));
  for (int k = 0; k < size; k++)
   fout.print(array[k] + " | ");
  fout.close();

 }
 public static void main(String args[]) throws IOException  {
  ArrayMergeSort m = new ArrayMergeSort(10);
  m.readFile();
  System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
  m.print();
  m.MergeSort();
  System.out.println("After Sort > > > > > > > > > > > >");
  m.print();
  m.WriteFile();
 }

}

/****************************************************************
 * Output of this Program 
 * The Array of Element are : 66 83 65 19 50 92 90 72 71 19 
 * Before Sort <<<<<<<<<<<<<<<<<<<<< 
 * Contents of the Array 
 * 66 | 83 | 65 | 19| 50 | 92 | 90 | 72 | 71 | 19 |
 *  After Sort > > > > > > > > > > > > Contents of the Array 
 *  19 | 19 | 50 | 65 | 66 | 71 | 72 | 83 | 90 | 92 |
 ****************************************************************/


About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

0 comments :

Post a Comment

Thank you for vising Java90.blogspot.com

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .