Question

1) You must implement a recursive Quicksort algorithm that will read integers from the attached MyList.txt file. Your algorithm must sort the list(integers)in ascending order.

2)You must implement a recursive Mergesort algorithm that will read integers from the attached MyList.txt file. Your algorithm must sort the list(integers)in ascending order.

My List.txt Values

7

3

4

1

4

4

9

9

4

8

4

5

3

9

2

3

7

0

6

4

4

5

0

1

9

2

1

7

4

7

8

7

8

3

6

3

5

9

7

3

7

8

8

2

5

9

1

2

7

2

0

1

7

5

4

3

0

5

9

2

0

7

8

9

8

4

8

2

9

2

2

1

1

5

7

5

7

5

8

7

3

2

7

8

0

1

5

1

7

6

9

2

9

6

3

9

2

6

0

5

8

9

7

5

3

5

4

2

4

5

7

7

6

9

7

1

9

4

2

9

1

1

6

4

6

5

7

3

5

1

6

8

5

9

3

5

Answer 1

// QuickSort.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class QuickSort {

   // method to sort the input array of integers using quick sort in ascending order
   public static void quickSort(int[] array) {
       quickSort(array,0,array.length-1);
   }
  
   // recursive method to sort the array using quick sort
   private static void quickSort(int[] array, int begin, int end) {
       int pivotKey;
       // if begin index < end index
       if(begin < end)
       {
           pivotKey = partition(array,begin,end); // get the pivot index
           quickSort(array, begin, pivotKey-1); // call quick sort to sort the list from begin to pivotKey - 1
           quickSort(array, pivotKey+1, end); // call quick sort to sort the list from pivotKey+1 to end
       }
   }
  
   // Partition part of an array, and return the index where the pivot
   // ended up where pivot is the mid element of the array
   private static int partition(int[] array, int begin, int end) {
      
       int mid = (begin+end)/2; // get the index of mid element
       swap(array, begin, mid); // swap the begin and mid index elements
       int pivotkey = begin; // set pivotkey to begin
       int pivot = array[begin]; // get the element at pivot key
      
       // loop from begin+1 to end
       for(int i=begin+1;i<=end;i++)
       {
           // if ith element < pivot, swap elements at indices i and pivotkey+1 and increment pivotKey by 1
           if(array[i] < pivot)
           {
               swap(array, i, ++pivotkey);
              
           }
       }
      
       // after the loop, swap the elements at begin and pivotkey to place the pivot in its correct position
       swap(array, begin, pivotkey);
      
       return pivotkey; // return the pivotkey
   }
  
   // method to swap two elements in an array
   private static void swap(int[] array, int i, int j) {

       int x = array[i];
       array[i] = array[j];
       array[j] = x;
   }
      
   public static void main(String[] args) throws FileNotFoundException
   {
       String filename = "MyList.txt";
       File inFile = new File(filename);
       Scanner fileScan = new Scanner(inFile); // open input file
       int[] array = null;
       int num;
       // loop to populate the array with integers read from file
       while(fileScan.hasNext())
       {
           num = fileScan.nextInt();
           if(array == null) // array is not allocated
               array = new int[1]; // create an array of size 1
           else
           {   // expand the array by 1 element
               int temp[] = new int[array.length+1];
               for(int i=0;i<array.length;i++)
                   temp[i] = array[i];
               array = temp;
           }
             
           array[array.length-1] = num; // insert num at the end of array
       }
      
       fileScan.close(); // close the file
      
       // display the unsorted array with 10 elements in a line
       System.out.println("UNSORTED ARRAY: ");
       for(int i=0;i<array.length;i++)
       {
           System.out.printf("%5d",array[i]);
           if((i+1)%10 == 0)
               System.out.println();
       }
      
       System.out.println();
      
       quickSort(array); // sort the array using quick sort
      
       // display the sorted array with 10 elements in a line
       System.out.println("SORTED ARRAY: ");
       for(int i=0;i<array.length;i++)
       {
           System.out.printf("%5d",array[i]);
           if((i+1)%10 == 0)
               System.out.println();
       }
      
       System.out.println();
   }

}

//end of QuickSort.java

Output:

Input file: MyList.txt

Output:

// MergeSort.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MergeSort {
  
   // method to sort the input array in ascending order using merge sort
   public static void mergeSort(int[] array) {

       mergeSort(array,0,array.length-1);
   }
  
   // recursive merge sort method to sort the array in ascending order
   private static void mergeSort(int[] array, int begin, int end) {

       if(begin < end) // array has atleast 2 elements
       {
           int mid = (begin+end)/2; // get the index of mid element
           mergeSort(array, begin, mid); // call mergesort to sort the left subarray from begin to mid
           mergeSort(array,mid+1, end); // call mergesort to sort the right subarray from mid+1 to end
           merge(array,begin,mid,end); // merge and left and right sorted subarray to create the sorted array
       }
   }
  
   // method that merges the two sorted subarrays to create the sorted array
   private static void merge(int[] array, int low, int mid, int high) {

       // set l to starting index of sorted left subarray and h to starting index of sorted right subarray
       int l = low, h = mid+1;
       int n = low; // set n to low
      
       // create a temporary array of same size as array
       int brr[] = new int[array.length];

       // loop that continues till we reach end of left or right subarray
       for(; l <= mid && h <= high;)
       {
           // current element of left suarray <= current element of right subarray
           if(array[l] <= array[h])
           {
               brr[n] = array[l]; // add the element from left subarray to brr
               l++; // increment the index for left subarray
           }else // current element of left subarray > current element of right subarray
           {
               brr[n] = array[h]; // add the element from right subarray to brr
               h++; // increment the index for right subarray
           }
           n++; // increment index of brr
       }
      
       // copy the leftover elements from left subarray to brr
       for(;l<=mid;l++)
           brr[n++] = array[l];
      
       // copy the leftover elements from right subarray to brr
       for(;h<=high;h++)
           brr[n++] = array[h];
      
       // loop to copy the sorted elements from brr to array
       for(n=low;n<=high;n++)
       {
           array[n] = brr[n];
       }
   }
  
   public static void main(String[] args) throws FileNotFoundException
   {
       String filename = "MyList.txt";
       File inFile = new File(filename);
       Scanner fileScan = new Scanner(inFile); // open input file
       int[] array = null;
       int num;

       // loop to populate the array with integers read from file
       while(fileScan.hasNext())
       {
           num = fileScan.nextInt();
           if(array == null) // array is not allocated
               array = new int[1]; // create an array of size 1
           else
           {
               // expand the array by 1 element  
               int temp[] = new int[array.length+1];
               for(int i=0;i<array.length;i++)
                   temp[i] = array[i];
               array = temp;
           }
          
           array[array.length-1] = num; // insert num at the end of array
       }
      
       fileScan.close();// close the file

       // display the unsorted array with 10 elements in a line
       System.out.println("UNSORTED ARRAY: ");
       for(int i=0;i<array.length;i++)
       {
           System.out.printf("%5d",array[i]);
           if((i+1)%10 == 0)
               System.out.println();
       }
      
       System.out.println();
      
       mergeSort(array); // sort the array using merge sort
      
// display the sorted array with 10 elements in a line
       System.out.println("SORTED ARRAY: ");
       for(int i=0;i<array.length;i++)
       {
           System.out.printf("%5d",array[i]);
           if((i+1)%10 == 0)
               System.out.println();
       }
      
       System.out.println();
   }

}

//end of MergeSort.java

Output:

Input file: MyList.txt

Output: