Question

In: Math

13 25 40 20 28 48 19 14 Complete the following: a) Use the bubble sort...

13 25 40 20 28 48 19 14

Complete the following:

a) Use the bubble sort (page 214) to sort the values showing the order of the values in the list after every pass of the sorting algorithm.

b) What is the time complexity of the sort (use the number of comparisons required as a measure of time.)

c) Modify the algorithm so it stops if there are no swaps in a complete pass. How many comparisons would be needed in your specific example?

d) Choose one of the following properties of Algorithms and show that the bubble sort has the given property:

Input: an algorithm has input values;

Output: from each set of input values an algorithm produces output values that are a solution to the problem;

Definiteness: the steps in an algorithm must be precisely defined;

Correctness: an algorithm must produce the correct output values for each set of input values;

Finiteness: an algorithm should produce the output after a finite number of steps;

Effectiveness: it must be possible to perform each step in the algorithm in a finite amount of time;

Generality: the algorithm must be applicable to a category of problems, not a single set of input values

Solutions

Expert Solution


Related Solutions

Given the following numbers:   25 16 61 18 15 20 15 20 24 17 19 28,...
Given the following numbers:   25 16 61 18 15 20 15 20 24 17 19 28, derive the mean, median, mode, variance, standard deviation, skewness, kurtosis, range, minimum, maximum, sum, and count. Interpret your results. What is the empirical rule for two standard deviations of the data?
Given the following numbers: 25 16 61 18 15 20 15 20 24 17 19 28,...
Given the following numbers: 25 16 61 18 15 20 15 20 24 17 19 28, derive the mean, median, mode, variance, standard deviation, skewness, kurtosis, range, minimum, maximum, sum, and count. Interpret your results. What is the empirical rule for two standard deviations of the data?
Sort the following set of numbers using bubble sort, insertion sort, and selection sort. Show the...
Sort the following set of numbers using bubble sort, insertion sort, and selection sort. Show the process step-by-step, and find the time complexity in Big-O notation for each method. For sorting, use ascending order. 49, 7, 60, 44, 18, 105
Please use the code I provided!! Use either bubble sort or selection sort!! Thank you in...
Please use the code I provided!! Use either bubble sort or selection sort!! Thank you in advance This lab involves adding a sorting function to an existing C++ template. In this module, a file is provided for you -- SortableBag.h -- that implements a simple "bag" (unsorted collection of numbers) structure with array storage. Part 1 Add a sort() method to this template, which should not return any values or take any arguments ('void' for both the return type and...
Use Quicksort algorithm to sort the following sequences: a.10, 80, 3, 19, 14, 7, 5, 12...
Use Quicksort algorithm to sort the following sequences: a.10, 80, 3, 19, 14, 7, 5, 12 b.Choose your sequence with 100different(random)integer numbers c.Choose your sequence with 1000different(random)integer numbers Please include your pseudocode, input sequence, and output in the report. Also, you need to analyze the computational time for different partition methods(e.g., best/worst/average cases)for sequences b and c. Will rate! design analysis and algorithms
1) Use insertion sort to sort: 25, 17, 31, 13, 2. Show your work step-by-step. 2)...
1) Use insertion sort to sort: 25, 17, 31, 13, 2. Show your work step-by-step. 2) Use Euclidean algorithm to find gcd(248, 198) 3) (ABCDEF)16 to binary, octal and decimal
Question 12 (1 point) X 28 23 30 48 40 25 26 Y 91 106 112...
Question 12 (1 point) X 28 23 30 48 40 25 26 Y 91 106 112 192 155 130 101 The coefficient of determination for the above bivariate data is: Question 12 options: 0.60 0.70 0.80 0.90
Resident Commuter 22 25 27 23 26 28 26 24 18 20 19 18 22 25...
Resident Commuter 22 25 27 23 26 28 26 24 18 20 19 18 22 25 24 35 25 20 26 24 27 26 18 19 23 18 23 22 28 25 20 24 18 30 26 18 18 19 32 23 26 30 22 22 22 21 18 20 19 19 18 29 19 22 18 22 19 26 35 19 19 18 19 32 26 19 19 21 23 18 20 18 29 23 21 19 36 27...
Neck (Y) Waist (X) 13 30 14 36 12 28 14 27 15 28 15 33...
Neck (Y) Waist (X) 13 30 14 36 12 28 14 27 15 28 15 33 16 36 13 31 16 40 13 30 14 37 13 33 14 35 12 24 14 35 15 35 17 43 14 36 13 29 13 31 * If you are able to can you please type out and number the answers to each one so it's easier to understand. Thank you! 1) T-statistic, degree of freedom and P-value (assume a=0.05) 2) Explain...
Neck (Y) Waist (X) 13 30 14 36 12 28 14 27 15 28 15 33...
Neck (Y) Waist (X) 13 30 14 36 12 28 14 27 15 28 15 33 16 36 13 31 16 40 13 30 14 37 13 33 14 35 12 24 14 35 15 35 17 43 14 36 13 29 13 31 * If you are able to can you please type out and number the answers to each one so it's easier to understand. Thank you! 1) T-statistic, degree of freedom and P-value (assume a=0.05) 2) Explain...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT