Question

Design a program in JAVA that allows you to experiment with different sort algorithms. The algorithms are shell sort and quick sort. Assume that input data is stored in a text file.

Experimenting with a prototype data (integers from 1 to 10) to ensure that your implementation works correctly and the results match expectations. The program will sort what is in the text file and print the amount of comparisons and exchanges for both algorithms.

Answer 1

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class Sort
{
   public static int numOfComps = 0,numOfSwaps = 0;

    public static void main(String[] args)
   {
    
   try{
       Scanner scanner = new Scanner(new File("a.txt"));//your text file here
      
       int [] values = new int [100];
       int i = 0;
       while(scanner.hasNextInt())
       {
           values[i++] = scanner.nextInt();
       }
       int n=i;
       int arr[]=new int[n];
              for(i=0;i<n;i++)
               arr[i]=values[i];

      
               System.out.println("\n\nQuick Sort:");
           // Display the array's contents.
              System.out.println("\nOriginal order: ");
              for(i=0;i<n;i++)
               System.out.print(arr[i] + " ");

              // Sort the array.
              quickSort(arr,n);

              // Display the array's contents.
              System.out.println("\nSorted order: ");
              for(i=0;i<n;i++)
               System.out.print(arr[i] + " ");

              System.out.println("\n\nNumber of comps = " + numOfComps);
               System.out.println("Number of swaps = " + numOfSwaps);
              
           numOfComps = 0;
           numOfSwaps = 0;
          
           System.out.println("\n\nShell Sort:");
           // Display the array's contents.
              System.out.println("\nOriginal order: ");
              for(i=0;i<n;i++)
               System.out.print(values[i] + " ");

          
              // Sort the array.
              shellSort(values,n);

              // Display the array's contents.
              System.out.println("\nSorted order: ");
              for(i=0;i<n;i++)
               System.out.print(values[i] + " ");

              System.out.println("\n\nNumber of comps = " + numOfComps);
              System.out.println("Number of swaps = " + numOfSwaps);
          
              System.out.println();
      

      }
       catch (FileNotFoundException e) {
           e.printStackTrace();
       }

   }

   public static void quickSort(int array[],int n )
   {
      doQuickSort(array, 0, n- 1);
   }

   private static void doQuickSort(int array[], int start, int end)
   {
      int pivotPoint;

      if (start < end)
      {
         //numOfComps++;

         // Get the pivot point.
         pivotPoint = partition(array, start, end);

         // Sort the first sub list.
         doQuickSort(array, start, pivotPoint - 1);

         // Sort the second sub list.
         doQuickSort(array, pivotPoint + 1, end);
      }
   }

   private static int partition(int array[], int start, int end)
   {
      int pivotValue;    // To hold the pivot value
      int endOfLeftList; // Last element in the left sub list.
      int mid;           // To hold the mid-point subscript

      // Find the subscript of the middle element.
      // This will be our pivot value.
      mid = (start + end) / 2;

      // Swap the middle element with the first element.
      // This moves the pivot value to the start of
      // the list.
      swap(array, start, mid);

      // Save the pivot value for comparisons.
      pivotValue = array[start];

      // For now, the end of the left sub list is
      // the first element.
      endOfLeftList = start;

      // Scan the entire list and move any values that
      // are less than the pivot value to the left
      // sub list.
      for (int scan = start + 1; scan <= end; scan++)
      {

         if (array[scan] < pivotValue)
         {
            endOfLeftList++;
            swap(array, endOfLeftList, scan);

                numOfSwaps ++;
         }
         numOfComps++;
      }

      // Move the pivot value to end of the
      // left sub list.
      swap(array, start, endOfLeftList);

      // Return the subscript of the pivot value.
      return endOfLeftList;
   }

   private static void swap(int[] array, int a, int b)
   {
      int temp;

         temp = array[a];
         array[a] = array[b];
         array[b] = temp;
    }
  
  
//shell sort

    public static void SegmentedInsertionSort (int[] array, int N, int gap)
    {
        for (int index = gap ; index < N ; index++)
        {
            int temp;
            int j = index - gap;
            while (j >= 0)
            {
                  numOfComps++;
                  if (array[j]>array[j+gap])
                  {
                       temp = array[j];
                       array[j] = array[j + gap];
                       array[j + gap] = temp;
                       j = j - gap;
                       numOfSwaps++;
                  }
                  else j = -1;
            }
        }
    }

    public static void shellSort (int[] array,int n)
    {
        int N = n;
        int gap = N/2;
        while (gap > 0)
        {
            SegmentedInsertionSort(array, N, gap);
            gap = gap / 2;
        }
    }
}

------------------------------------------------------------------------------------------------------

a.txt

------------------------------------------------------------------

5
2
3
4
1

=================================

output

-------------------------------------------------------

Quick Sort:

Original order:
5 2 3 4 1
Sorted order:
1 2 3 4 5

Number of comps = 6
Number of swaps = 2

Shell Sort:

Original order:
5 2 3 4 1
Sorted order:
1 2 3 4 5

Number of comps = 8
Number of swaps = 3

==================================