Question

In: Computer Science

I have this program, it sorts a file using shell sort and quick sort then prints...

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

Solutions

Expert Solution

Code For Above Problem:


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

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

                        // Sort the array.
                        insertionSort(arr1, 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 array.
                        doQuickSort(array, start, pivotPoint - 1);

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

        private static int partition(int array[], int start, int end) {
                int pivotValue; // To hold the pivot value
                int endOfLeftarray; // Last element in the left sub array.
                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 array.
                swap(array, start, mid);

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

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

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

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

                                numOfSwaps++;
                        }
                        numOfComps++;
                }

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

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

        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;
                }
        }
        
        
    public static void insertionSort(int[] array,int n) {
        
        for(int i = 1; i < n; i++) {
        
          int j = i;      
                
          // compare i with sorted elements and insert it
          // sorted elements: [0..i-1]
          while (j > 0 && array[j] < array[j - 1]) {
            
            int temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
            
            numOfSwaps++;
            numOfComps++;  // loop condition true
            j--;
          }
          numOfComps++; // checking loop condition when false
        }
    }
}

Output Of Code:



Quick Sort:

Original order: 
42 899 747 807 445 39 478 500 338 838 852 391 38 447 673 900 727 718 965 619 810 11 970 228 742 847 414 831 152 5 891 968 97 539 489 374 274 380 557 391 680 276 210 282 777 679 574 88 214 702 888 343 115 975 821 501 545 816 690 549 685 903 772 817 930 689 475 21 713 501 973 19 521 572 519 681 417 376 573 995 289 862 179 173 89 721 604 58 585 68 439 514 584 252 531 291 745 256 655 711 
Sorted order: 
5 11 19 21 38 39 42 58 68 88 89 97 115 152 173 179 210 214 228 252 256 274 276 282 289 291 338 343 374 376 380 391 391 414 417 439 445 447 475 478 489 500 501 501 514 519 521 531 539 545 549 557 572 573 574 584 585 604 619 655 673 679 680 681 685 689 690 702 711 713 718 721 727 742 745 747 772 777 807 810 816 817 821 831 838 847 852 862 888 891 899 900 903 930 965 968 970 973 975 995 

Number of comps = 569
Number of swaps = 335


Shell Sort:

Original order: 
42 899 747 807 445 39 478 500 338 838 852 391 38 447 673 900 727 718 965 619 810 11 970 228 742 847 414 831 152 5 891 968 97 539 489 374 274 380 557 391 680 276 210 282 777 679 574 88 214 702 888 343 115 975 821 501 545 816 690 549 685 903 772 817 930 689 475 21 713 501 973 19 521 572 519 681 417 376 573 995 289 862 179 173 89 721 604 58 585 68 439 514 584 252 531 291 745 256 655 711 
Sorted order: 
5 11 19 21 38 39 42 58 68 88 89 97 115 152 173 179 210 214 228 252 256 274 276 282 289 291 338 343 374 376 380 391 391 414 417 439 445 447 475 478 489 500 501 501 514 519 521 531 539 545 549 557 572 573 574 584 585 604 619 655 673 679 680 681 685 689 690 702 711 713 718 721 727 742 745 747 772 777 807 810 816 817 821 831 838 847 852 862 888 891 899 900 903 930 965 968 970 973 975 995 

Number of comps = 822
Number of swaps = 371


Insertion Sort:

Original order: 
42 899 747 807 445 39 478 500 338 838 852 391 38 447 673 900 727 718 965 619 810 11 970 228 742 847 414 831 152 5 891 968 97 539 489 374 274 380 557 391 680 276 210 282 777 679 574 88 214 702 888 343 115 975 821 501 545 816 690 549 685 903 772 817 930 689 475 21 713 501 973 19 521 572 519 681 417 376 573 995 289 862 179 173 89 721 604 58 585 68 439 514 584 252 531 291 745 256 655 711 
Sorted order: 
5 11 19 21 38 39 42 58 68 88 89 97 115 152 173 179 210 214 228 252 256 274 276 282 289 291 338 343 374 376 380 391 391 414 417 439 445 447 475 478 489 500 501 501 514 519 521 531 539 545 549 557 572 573 574 584 585 604 619 655 673 679 680 681 685 689 690 702 711 713 718 721 727 742 745 747 772 777 807 810 816 817 821 831 838 847 852 862 888 891 899 900 903 930 965 968 970 973 975 995 

Number of comps = 2694
Number of swaps = 2595

a.txt file:

42 899 747 807 445 39 478 500 338 838 852 391 38 447 673 900 727 718 965 619 810 11 970 228 742 847 414 831 152 5 891 968 97 539 489 374 274 380 557 391 680 276 210 282 777 679 574 88 214 702 888 343 115 975 821 501 545 816 690 549 685 903 772 817 930 689 475 21 713 501 973 19 521 572 519 681 417 376 573 995 289 862 179 173 89 721 604 58 585 68 439 514 584 252 531 291 745 256 655 711

Image Of InsertionSort Code;

Image Of Driver for InsertionSort in Main:

venereology answered 2 years ago
Next > < Previous

Related Solutions

I have this program, it sorts a file using shell sort and quick sort then prints...
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       ...
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
2 real-time examples on the Insertion sort, Bubble sort, Selection sort, Quick sort, Shell sort, Merge...
2 real-time examples on the Insertion sort, Bubble sort, Selection sort, Quick sort, Shell sort, Merge sort, Radix sort, Bucket sort, and Counting sort.
JAVA - Quick Sort .txt and Return ----------------------------------------------------------------------------- The program should input a .txt file like...
JAVA - Quick Sort .txt and Return ----------------------------------------------------------------------------- The program should input a .txt file like below and must use a Quick sort Algorithm ================ 6 10 4 19 10 12 8 6 0 1 2 3 ================ The first number "6" represents the index of the element to return after sort the second number on the top "10" represents the number of elements or size of array. The following numbers and lines are the elements that need to go...
Write a MIPS program using the Bubble Sort algorithm, that sorts an input list of integers...
Write a MIPS program using the Bubble Sort algorithm, that sorts an input list of integers by repeatedly calling a “swap” subroutine. The original unsorted list of integers should be received from the keyboard input. Your program should first prompt the user “Please input an integer for the number of elements:”. After the user enters a number and return, your program outputs message “Now input each element and then a return:”. For example, if the user enters 5 as the...
Write a program that computes and prints the average of numbers in a text file. I...
Write a program that computes and prints the average of numbers in a text file. I created a text file integers.txt that has the numbers 5,4,3,2,1. I need to define the average function Define the main function which will include the following things 1. prompt user for input of text file name 2. open and read input file, can be done before or inside high order functions 3. use two high order functions 4.calculate and display averages and original ist...
Write a MIPS program that uses an implementation of quick sort to sort an array of...
Write a MIPS program that uses an implementation of quick sort to sort an array of numbers (Translate the following code into (Mars Assembly language). Quicksort Implementation - C int partition(int arr [] , int left , int right) { int i=left, j=right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr [ i ] < pivot) i ++; while (arr [ j ] > pivot) j −−; if (i <= j)...
The quick sort algorithm always divides the list into two equal sized sublists, then sorts each...
The quick sort algorithm always divides the list into two equal sized sublists, then sorts each sublists, and then combines both sublists.. True of False
Create a quick and merge sort algorithm that sorts 6 9 8 12 3 1 7...
Create a quick and merge sort algorithm that sorts 6 9 8 12 3 1 7 In java please.
please write a C program that implements Quick Sort algorithm.
please write a C program that implements Quick Sort algorithm.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT