java / data structures and algorithms/ sorting part In the questions below, assu

Question

java / data structures and algorithms/ sorting part

In the questions below, assume that sorting refers to sorting into ascending order unless specied otherwise.

(a) Consider the array 15 14 13 12 11 10 9 8765 4 3 2 1]. Carry out a Shell sort on the array with subarrays defined by the values h1 1,h2 = 3,h3-5. (That is, sort in the same way as in the lecture slide example: split into 5 subarrays and do a 5-sort; then (b) Determine the total number of comparisons (between elements of the array) made during (c) Determine the total number of comparisons that would be made if an insertion sort were (d) (Harder) Consider an array in descending order Inn-1 n-2...1] for some n divisible split into 3 subarrays and do a 3-sort; then do a 1-sort on the whole array.) the Shell sort in (la) above carried out on the whole array from (la) above. by 5; that is, n 5k for some integer k > 1 i. Determine the total number of comparisons that would be made in a Shell sort with h1-1,h2 = 5 (that is, a 5-sort followed by a 1-sort). Express your answer as a function of k sort. Express your answer as a function of k. for any valid n? Why or why not? ii. Determine the total number of comparisons that would be made by an insertion iii. Is the Shell sort always as good as or better than insertion sort on this type of array, The last part of the question is harder, but have a go at it anyway For (la), format your answer in the same way as in the lecture slides / textbook. A text file containing the answers will be satisfactory; if you submit a Word document, use a fixed-width font like Courier so that alignment of subarrays is clear.

Explanation / Answer

import java.util.Random; public class Shell_Sort { public static int N = 20; public static int[] sequence = new int[N]; public static void shellSort() { int increment = sequence.length / 2; while (increment > 0) { for (int i = increment; i = increment && sequence[j - increment] > temp) { sequence[j] = sequence[j - increment]; j = j - increment; } sequence[j] = temp; } if (increment == 2) increment = 1; else increment *= (5.0 / 11); } } static void printSequence(int[] sorted_sequence) { for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.