Question

I have this program, it sorts a file using shell sort and quick sort then prints amount of comparisons and swaps. I need to add the bubble sort algorithm. Here is the code. The language is Java.

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;
        }
    }
}

Answer 1

Program: In this program, we add the bubble sort function, which keeps count of the total number of comparisons and swaps made during the sorting. The total number of comparisons made in a bubble sort is (n*(n-1))/2.

Below is the implementation:

Code:

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];
            int array[] = new int[n];
            for(i=0;i<n;i++) {
                arr[i] = values[i];
                array[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);

            numOfComps = 0;
            numOfSwaps = 0;

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

            // Sort the array.
            bubbleSort(array);

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


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

        }
        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;
        }
    }

    // Bubble Sort
    public static void bubbleSort(int[] array)
    {
        int n = array.length;

        // Create a for loop till array.length - 1
        for (int i = 0; i < n-1; i++)
        {
            // Compare each element with its next element
            for (int j = 0; j < n-i-1; j++)
            {
                // Increment number of Comparisons
                numOfComps++;
                if(array[j] > array[j+1])
                {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;

                    // If a swap is made then increment number of swaps
                    numOfSwaps++;
                }
            }
        }
    }
}

Output: