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 10 months ago

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); }...

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.

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

Python Question: Write a function that checks to see if an array of integers is sorted...

Python Question: Write a function that checks to see if an array of integers is sorted in an increasing fashion, returning true if it is, false otherwise. Test it with at least4 arrays - 2 sorted and 2 not sorted. Use a CSV formatted input file as described in the previous question to run your program through some tests, where again the filename is passed as an argument. Heres what I have so far: import sys # command line arguement...

Design an algorithm that will read an array of 200 characters and display to the screen...

Design an algorithm that will read an array of 200 characters and display to the screen a count of the occurrences of each of the five vowels (a, e, i, o, u) in the array. Your string is: The quick brown fox jumped over the lazy dog That is the question for my pseudo code question, I don't know if I have this correct can i have someone look this over and finish this and explain what i needed to...

In C++ write an implementation of the ADT sorted list that uses a resizable array (vector...

In C++ write an implementation of the ADT sorted list that uses a resizable array (vector class of C++ STL) to represent the list items.

Write a program to compute intersection of two sorted array of integers and compute the CPU...

Write a program to compute intersection of two sorted array of integers and compute the CPU time for different sets of unsigned integers generated by a random number generator. Test this using the same data sets: atleast 3 of size 1000 integers, atleast 3 of size 10000 integers, atleast 3 of size 100000 integers, atleast 3 of one million integers and atleast 3 of size 10 million integers DONT FORGET CPU TIME FOR EACH ONE NO HASH SET

Question