Embercode: AI-powered software engineer course

1. Insertion sort runs on the reversed list [1000, 999, ..., 1] of 1000 numbers, and every shift is counted. How many shifts does it make?

Type a number.

2. Insertion sort runs on a list where every value is at most k places from its final position. What is its running time?

O(n squared), the same as reversed inputO(n times k), which is O(n) when k is a small fixed numberO(n log n), because the list is split into halvesO(log n), because only a few values move

3. What does this program print? ``

python
def gapped_insertion(a, gap):
    for i in range(gap, len(a)):
        value = a[i]
        j = i
        while j >= gap and a[j - gap] > value:
            a[j] = a[j - gap]
            j -= gap
        a[j] = value

a = [7, 2, 9, 4, 1, 8, 3, 6]
gapped_insertion(a, 4)
print(a)

``

[1, 7, 2, 8, 3, 9, 4, 6][1, 2, 3, 4, 7, 8, 6, 9][7, 8, 9, 6, 1, 2, 3, 4][1, 2, 3, 4, 7, 8, 9, 6]

4. What does this program print? ``

python
moves = 0

def gapped_insertion(a, gap):
    global moves
    for i in range(gap, len(a)):
        value = a[i]
        j = i
        while j >= gap and a[j - gap] > value:
            a[j] = a[j - gap]
            moves += 1
            j -= gap
        a[j] = value

a = [5, 4, 3, 2, 1, 6]
gapped_insertion(a, 2)
gapped_insertion(a, 1)
print(a, "moves=" + str(moves))

``

[1, 2, 3, 4, 5, 6] moves=4[1, 2, 3, 4, 5, 6] moves=10[5, 4, 3, 2, 1, 6] moves=0[1, 2, 3, 4, 5, 6] moves=7

5. For a list of length 20, Knuth's rule gives which gap list?

[13, 4, 1][10, 5, 2, 1][4, 1][15, 7, 3, 1]

Nearly sorted and shell