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 2 years 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:...

Python - You are given a sorted (from smallest to largest) array A of n distinct...

Python - You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative or zero. Design the fastest algorithm you can for deciding if there is an index i such that A[i] = i.

Written in MIPS assembly language If given an array which is sorted in ascending order, as...

Written in MIPS assembly language If given an array which is sorted in ascending order, as well as its length and a target value. You are asked to find the index of this target value in the array using binary search algorithm. Here is an example: array 1, 4, 6, 8, 10, 12 length 6 target 8 2 In this case, the returned result should be assigned to be 3, as array[3] is equal to target. (Note: The target will...

The following is the pseudocode of algorithm that searches a sorted array of n items by...

The following is the pseudocode of algorithm that searches a sorted array of n items by dividing it into three sub arrays of almost n/3 items (7pt). Hint: refer Mergesort algorithm) Input: Sorted array of Keys(A) indexed from 1 to n. Output: Location, the Location of K in array A (hint: return 0 if K is no in A) index location3 (int A[1…n ], index L, index H) { index m1, m2; if (L > H) return 0; else ...

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...

Question