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 underlying concept is edge computing based on?
guajiro [1.7K]

Answer:

Edge computing was developed due to the exponential growth of IoT devices, which connect to the internet for either receiving information from the cloud or delivering data back to the cloud. And many IoT devices generate enormous amounts of data during the course of their operations.

Explanation:

8 0
2 years ago
Read 2 more answers
What mode is generally used when delivering a presentation to an audience?
dybincka [34]

Answer:

delivery mode

Explanation:

there it is

7 0
3 years ago
Read 2 more answers
Which type of ICS facility is used to temporarily position and account for personnel, supplies, and equipment awaiting assignmen
Black_prince [1.1K]

Answer:

C. Staging Area

Explanation:

According to my research on different ICS facilities, I can say that based on the information provided within the question the facility being described here is called a Staging Area. Like mentioned in the question a staging area is a location set up at an incident where resources and personnel can be placed while waiting on instructions to proceed with an operation or assignment.

I hope this answered your question. If you have any more questions feel free to ask away at Brainly.

6 0
3 years ago
A built-in tool that enables you to use text to type in commands for the operating system is called the _____ prompt.
Natalija [7]
Command prompt is the answer and on Apple devices it is called Terminal.
8 0
3 years ago
Read 2 more answers
A ____________________ can be used to hierarchically represent a classification for a given set of objects or documents. A. taxo
neonofarm [45]

Answer:

A. taxonomy

Explanation:

A taxonomy can be used to hierarchically represent a classification for a given set of objects or documents.

3 0
3 years ago
Other questions:
  • Which one is not among standard creation committee?
    9·1 answer
  • Notice in the topology there are 3 network ranges that would be translated based on the ACL created. What will happen if more th
    6·1 answer
  • A noisy signal has been uploaded to D2L in the files fft_signal.mat and fft_signal.txt.Write a program to estimate the power spe
    10·1 answer
  • Design and implement an algorithm that gets a list of k integar values N1, N2,...Nk as well as a special value SUM. Your algorit
    10·1 answer
  • An email message containing a warning related to a non-existent computer security threat, asking a user to delete system files f
    6·1 answer
  • Describe the different
    12·1 answer
  • Brainly is brainly am I correct ​
    11·2 answers
  • What are the four different orchestral instrument families?
    6·2 answers
  • Write a program that generates 100 random numbers and keeps a count of how many of those random numbers are even and how many of
    15·1 answer
  • What makes a recipe for a meal an example of an algorithm?
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!