Nearly sorted and shell

Questions 1 to 5 of 7

1. 1. Insertion sort gets a list where every value is at most d places from its final spot, with d fixed. How does the number of shifts grow as the list gets longer?

   In step with n, so it is O(n)With n log n, so it is O(n log n)With n squared, so it is O(n^2)Only with log n, so it is O(log n)
2. 2. Insertion sort runs on the reversed list 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. How many shifts does it make?

   Type a number.

3. 3. Predict the output of this program. ``cpp #include <cstddef> #include <iostream> #include <vector> struct Counts { long long comparisons = 0; // times two values were compared long long shifts = 0; // times a value moved one slot to the right }; Counts insertion_sort(std::vector<int>& a) { Counts c; for (std::size_t i = 1; i < a.size(); ++i) { int key = a[i]; // the value to insert std::size_t j = i; // the slot it is moving into while (j > 0) { ++c.comparisons; if (a[j - 1] <= key) break; // the value on the left is small enough a[j] = a[j - 1]; // slide the bigger value one slot right ++c.shifts; --j; } a[j] = key; // drop the value into its slot } return c; } int main() { std::vector<int> a = {2, 1, 4, 3, 6, 5}; Counts c = insertion_sort(a); std::cout << "comparisons=" << c.comparisons << " shifts=" << c.shifts << '\n'; } ``

   comparisons=5 shifts=3comparisons=7 shifts=3comparisons=7 shifts=4comparisons=9 shifts=3
4. 4. Predict the output of this program. It runs one gap-3 pass and prints the vector. ``cpp #include <cstddef> #include <iostream> #include <vector> std::size_t gapped_insertion_pass(std::vector<int>& a, std::size_t gap) { std::size_t moves = 0; for (std::size_t i = gap; i < a.size(); ++i) { int current = a[i]; std::size_t j = i; while (j >= gap && a[j - gap] > current) { a[j] = a[j - gap]; ++moves; j -= gap; } a[j] = current; } return moves; } int main() { std::vector<int> a{6, 5, 4, 3, 2, 1}; gapped_insertion_pass(a, 3); for (int x : a) std::cout << x << ' '; std::cout << '\n'; } ``

   6 5 4 3 2 11 2 3 4 5 63 2 1 6 5 43 2 1 4 5 6
5. 5. Why is the final gap-1 pass in shell sort cheap?

   Gap 1 compares each value with the one at its far end, so it moves few valuesGap 1 skips equal values, so it never shifts anythingThe earlier passes already moved most values close to their final place, so insertion sort has little left to shiftThe gap-1 pass starts over from index 0 with an empty sorted part