1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Yuki888 [10]
3 years ago
14

Assume the existence of an UNSORTED ARRAY of n characters. You are to trace the CS111Sort algorithm (as described here) to reord

er the elements of a given array. The CS111Sort algorithm is an algorithm that combines the SelectionSort and the InsertionSort following the steps below: 1. Implement the SelectionSort Algorithm on the entire array for as many iterations as it takes to sort the array only to the point of ordering the elements so that the last n/2 elements are sorted in increasing (ascending) order. 2. Implement the InsertionSort Algorithm to sort the first half of the resulting array elements so that these elements are sorted in decreasing (descending) order.
Computers and Technology
1 answer:
makvit [3.9K]3 years ago
6 0

Answer:

class Main {

  public static void main(String[] args) {

      char arr[] = {'T','E','D','R','W','B','S','V','A'};

      int n = arr.length;

      System.out.println("Selection Sort:");

      System.out.println("Iteration\tArray\tComparisons");

      long comp1 = selectionSort(arr);

      System.out.println("Total comparisons: "+comp1);

      System.out.println("\nInsertion Sort:");

      System.out.println("Iteration\tArray\tComparisons");

      long comp2 = insertionSort(arr);

      System.out.println("Total Comparisons: "+comp2);

      System.out.println("\nOverall Total Comparisons: "+(comp1+comp2));

  }

  static long selectionSort(char arr[]) {

      // applies selection sort for n/2 elements

      // returns number of comparisons

      int n = arr.length;

      long comparisons = 0;

 

      // One by one move boundary of unsorted subarray

      for (int i = n-1; i>=n-n/2; i--) {

              // Find the minimum element in unsorted array

              int max_idx = i;

              for (int j = i-1; j>=0; j--) {

                      // there is a comparison everytime this loop returns

                      comparisons++;

                      if (arr[j] > arr[max_idx])

                              max_idx = j;

              }

              // Swap the found minimum element with the first

              // element

              char temp = arr[max_idx];

              arr[max_idx] = arr[i];

              arr[i] = temp;

              System.out.print(n-1-i+"\t");

              printArray(arr);

              System.out.println("\t"+comparisons);

      }

     

      return comparisons;

  }

  static long insertionSort(char arr[]) {

      // applies insertion sort for n/2 elements

      // returns number of comparisons

      int n = arr.length;

      n = n-n/2;   // sort only the first n/2 elements

      long comparisons = 0;

      for (int i = 1; i < n; ++i) {

          char key = arr[i];

          int j = i - 1;

          /* Move elements of arr[0..i-1], that are

                  greater than key, to one position ahead

                  of their current position */

          while (j >= 0) {

              // there is a comparison everytime this loop runs

              comparisons++;

              if (arr[j] > key) {

                  arr[j + 1] = arr[j];

              } else {

                  break;

              }

              j--;

          }

          arr[j + 1] = key;

          System.out.print(i-1+"\t");

          printArray(arr);

          System.out.println("\t"+comparisons);

      }

      return comparisons;

  }  

  static void printArray(char arr[]) {

      for (int i=0; i<arr.length; i++)

          System.out.print(arr[i]+" ");

  }

}

Explanation:

Explanation is in the answer.

You might be interested in
What does the following code print?
Crank

Answer:

It throws an error.

the public class needs a name.

like this:

public class G{ public static void main(String[] args) {

   int x=5 , y = 10;

   if (x>5 && y>=2) System.out.println("Class 1");

   else if (x<14 || y>5) System.out.println(" Class 2");

   else System.out.println(" Class 3"); }// end of main

   }

if you give the class a name and format it, you get:

Class 2

Explanation:

3 0
3 years ago
Describe the difference between Global knowledge and personal idea. Why is it important to give credit to others by citing their
sergejj [24]

Global knowledge is like common sense, people know these things, but their may be someone else with the same idea. One person can come up with the idea but their is also another with same so don't give someone to much credit.

7 0
3 years ago
Disadvantages assembly level language for programming ​
Alisiya [41]
It takes a lot of time and effort to write the code for the same. It is very complex and difficult to understand. The syntax is difficult to remember. It has a lack of portability of program between different computer architectures.

Hope that helps
7 0
3 years ago
Read 2 more answers
At higher doses what behaves like PCP causing feelings of power and invulnerability
ser-zykov [4K]
I don't think any answer would be correct, if you have an option "none of the above" then that would be the correct answer
5 0
3 years ago
In the RGB color model, what do numbers 0-255 represent
Ludmilka [50]

In the RGB (Red, Green, Blue) color model, the numbers 0-255 represent  the intensities of each color beam .Each number represents an intensity value is on a scale of 0 to 255, It can be also written in hexadecimal form, from 00 to FF.

RGB values are encoded as 8-bit integers, which range from 0 to 255.

3 0
3 years ago
Other questions:
  • Given positive integer numInsects, write a while loop that prints that number doubled without reaching 100. Follow each number w
    8·1 answer
  • Write a program that asks the user to enter two dates (in YYYY-MM-DD format), and then prints which date is earlier. Your progra
    15·1 answer
  • Given an int variable k, an int array incompletes that has been declared and initialized, an int variable studentID that has bee
    10·1 answer
  • On five lane roadways, the center lane is designated for __________ and is used by vehicles traveling in both directions.A. Thro
    15·1 answer
  • A computer is a multipurpose device that accepts input, processes data, stores data, and produces output, all according to a ser
    9·1 answer
  • I will upvote....
    10·1 answer
  • What should be used to keep a tablet dry?
    13·1 answer
  • If each integer occupies one 64-bit memory cell and is stored using sign/magnitude notation, what are the largest (in terms of a
    12·1 answer
  • A drive is small enough to be carried in one's pocket.
    6·1 answer
  • What is the key difference between a class and an object
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!