6. Given the following array of characters: REALITYSHOWShow how this array will be sorted with the...

6. Given the following array of characters: REALITYSHOWShow how this array will be sorted with the help of : (a) insertion sort; (b) selection sort; (c) bubble sort with swaps counting; (d) bubble sort without swaps counting

subject design and analysis of algorithms

answer should be like eg p u r p l e

p r u p l e

Expert Solution

i) Insertion Sort

       Pass 0:       R E A L I T Y S H O W       [Unsorted]
       Pass 1:       E R A L I T Y S H O W
       Pass 2:       A E R L I T Y S H O W
       Pass 3:       A E L R I T Y S H O W
       Pass 4:       A E I L R T Y S H O W
       Pass 5:       A E I L R S T Y H O W
       Pass 6:       A E H I L R S T Y O W
       Pass 7:       A E H I L O R S T Y W
       Pass 8:       A E H I L O R S T W Y       [Sorted]

ii) Selection Sort

       Pass 0:       R E A L I T Y S H O W       [Unsorted]
       Pass 1:       A E R L I T Y S H O W
       Pass 2:       A E H L I T Y S R O W
       Pass 3:       A E H I L T Y S R O W
       Pass 4:       A E H I L O Y S R T W
       Pass 5:       A E H I L O R S Y T W
       Pass 6:       A E H I L O R S T Y W
       Pass 7:       A E H I L O R S T W Y       [Sorted]

iii) Bubble Sort with swap counting

       Pass 0:       R E A L I T Y S H O W       [Unsorted]
       Pass 1:       E A L I R T S H O W Y
       Pass 2:       A E I L R S H O T W Y
       Pass 3:       A E I L R H O S T W Y
       Pass 4:       A E I L H O R S T W Y
       Pass 5:       A E I H L O R S T W Y
       Pass 6:       A E H I L O R S T W Y
       Pass 7:       A E H I L O R S T W Y
       Pass 8:       A E H I L O R S T W Y
       Pass 9:       A E H I L O R S T W Y
       Pass 10:   A E H I L O R S T W Y       [Sorted]

Total swaps: 19

iv) Bubble Sort without swap counting

       Pass 0:       R E A L I T Y S H O W       [Unsorted]
       Pass 1:       E A L I R T S H O W Y
       Pass 2:       A E I L R S H O T W Y
       Pass 3:       A E I L R H O S T W Y
       Pass 4:       A E I L H O R S T W Y
       Pass 5:       A E I H L O R S T W Y
       Pass 6:       A E H I L O R S T W Y
       Pass 7:       A E H I L O R S T W Y
       Pass 8:       A E H I L O R S T W Y
       Pass 9:       A E H I L O R S T W Y
       Pass 10:   A E H I L O R S T W Y       [Sorted]

venereology answered 1 year ago

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array...

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time. Return that integer. Input: arr = [1,2,2,6,6,6,6,7,10] Output:

Please explain how the frequencies of characters were gotten, how they were sorted, and how the...

Please explain how the frequencies of characters were gotten, how they were sorted, and how the codes were gotten for the program below. #include <iostream> #include <vector> #include <queue> #include <string> using namespace std; class Huffman_Code { struct New_Node { char value; size_t frequencies; New_Node* left; New_Node* right; New_Node(char value, size_t frequencies) : value(value), frequencies(frequencies), left(NULL), right(NULL) {} ~New_Node() { delete left; delete right; } }; struct compare { bool operator()(New_Node* l, New_Node* r) { return (l->frequencies > r->frequencies); }...

We are given a non sorted array so that the values are not pairwise disjoint (the...

We are given a non sorted array so that the values are not pairwise disjoint (the same values may appear in many entries). Say that we can find the k-th smallest element number in the array in time O(n) for any 1 <= k <= n. Give an algorithm that finds if there is a value that appears at least n/3 times. Please explain the algorithm in words and analyze the run time.

in java code In the class Hw2, write a method removeDuplicates that given a sorted array,...

in java code In the class Hw2, write a method removeDuplicates that given a sorted array, (1) removes the duplicates so that each distinct element appears exactly once in the sorted order at beginning of the original array, and (2) returns the number of distinct elements in the array. The following is the header of the method: public static int removeDuplicates(int[ ] A) For example, on input A=0, 0, 1, 1, 1, 2, 2, 3, 3, 4, your method should:...

Given a sorted array with lot of duplicates, write a problem to search specific element m....

Given a sorted array with lot of duplicates, write a problem to search specific element m. If it’s included in the A, return its minimal index, otherwise return -1. For example A = {0, 0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 4}, if we search 4, you program should return 8. You are only allowed to use binary search. Linear search is not allowed here.

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice...

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example 1: Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn't matter what you leave beyond the returned...

Given an array of n numbers, not necessarily in sorted order, we wish to find: (i)...

Given an array of n numbers, not necessarily in sorted order, we wish to find: (i) the range (max - min) and (ii) the interquartile range (IQR) of the numbers. IQR is defined as the difference between the number at the 25% percentile and the number at the 75% percentile. What is the exact number of comparisons needed for computing the range and why? Using any algorithm from the chapters of the textbook covered so far as a subroutine, give...

Suppose you are given the following array X = [7, 9, 1, 6] Sort the array...

Suppose you are given the following array X = [7, 9, 1, 6] Sort the array in ascending order using the selction sort algorithm. Write the state of the array after each pass. Pass1: Pass2: Pass3: Suppose you are given the following array X = [7, 9, 1, 6] Sort the array in ascending order using the selction sort algorithm. Write the state of the array after each pass. Pass1: Pass2: Pass3:

Create an array of 10,000 elements, use sorted, near sorted, and unsorted arrays. Implement find the...

Create an array of 10,000 elements, use sorted, near sorted, and unsorted arrays. Implement find the kth smallest item in an array. Use the first item as the pivot. Compare sets of results using a static call counter. Reset counter before running another search. Create a Test drive to exhaustively test the program. // Assume all values in S are unique. kSmall(int [] S, int k): int (value of k-smallest element) pivot = arbitrary element from S: let’s use the first...

Assume that the incoming array is sorted and adjust the algorithm below to allow for faster...

Assume that the incoming array is sorted and adjust the algorithm below to allow for faster exit if the searched for value is not in the list. void linearsearch (int n, int Arr[], int a, int& index){ index = 1; while (index <= n && Arr[index] != a) index++; if (index > n) index = 0; }

Question