Lesson test: Elementary sorting

2.[3p]
Insertion sort's number of moves is exactly equal to

the number of inversions in the input

Correct

$n (n - 1) / 2$ , whatever the input

The answer is: the number of inversions in the input

the number of comparisons it makes

The answer is: the number of inversions in the input

the number of elements out of their final position

The answer is: the number of inversions in the input

4.[2p]
A random permutation of $n$ elements has, on average, how many inversions?

$n (n - 1) / 4$

Correct

$n (n - 1) / 2$

The answer is: $n (n - 1) / 4$

$n / 2$

The answer is: $n (n - 1) / 4$

$n \log_{2} n$

The answer is: $n (n - 1) / 4$

5.[3p]
Which of these are true of selection sort?

Select all that apply

It makes the same number of comparisons on every input of a given size

Correct

It makes at most $n - 1$ swaps

Correct

It is the right choice when moving an element is far more expensive than comparing two

Correct

It is stable as normally written

The answer is: It makes the same number of comparisons on every input of a given size, It makes at most $n - 1$ swaps, It is the right choice when moving an element is far more expensive than comparing two

6.[3p]
To order a table by department and, within each department, by surname, using a stable sort, you should

sort by surname first, then by department

Correct

sort by department first, then by surname

The answer is: sort by surname first, then by department

sort by department only, since stability does the rest

The answer is: sort by surname first, then by department

write one comparison function that compares both fields, since two passes cannot work

The answer is: sort by surname first, then by department

7.[2p]
Insertion sort runs in linear time on input whose inversion count is $O (n)$ .

True

Correct

False

The answer is: True

8.[2p]
An insertion sort takes 5.0 seconds on 100,000 random records. Roughly how many seconds does it take on 400,000 random records?

CorrectNot quite: 80

9.[3p]
Any algorithm that only swaps adjacent elements is stuck at $Θ (n^{2})$ on random input because

each adjacent swap removes at most one inversion, and there are $Θ (n^{2})$ of them

Correct

adjacent memory access is slower than random access

The answer is: each adjacent swap removes at most one inversion, and there are $Θ (n^{2})$ of them

it cannot be made stable

The answer is: each adjacent swap removes at most one inversion, and there are $Θ (n^{2})$ of them

comparisons of neighbours carry no information

The answer is: each adjacent swap removes at most one inversion, and there are $Θ (n^{2})$ of them

Sign in

Elementary sorting

1.[3p]
How many inversions does the array 5, 2, 4, 6, 1, 3 contain?

2.[3p]
Insertion sort's number of moves is exactly equal to

3.[2p]
How many comparisons does selection sort make on an array of 1000 elements that is already sorted?

4.[2p]
A random permutation of $n$ elements has, on average, how many inversions?

5.[3p]
Which of these are true of selection sort?

6.[3p]
To order a table by department and, within each department, by surname, using a stable sort, you should

7.[2p]
Insertion sort runs in linear time on input whose inversion count is $O (n)$ .

8.[2p]
An insertion sort takes 5.0 seconds on 100,000 random records. Roughly how many seconds does it take on 400,000 random records?

9.[3p]
Any algorithm that only swaps adjacent elements is stuck at $Θ (n^{2})$ on random input because

1.[3p] How many inversions does the array 5, 2, 4, 6, 1, 3 contain?

2.[3p] Insertion sort's number of moves is exactly equal to

3.[2p] How many comparisons does selection sort make on an array of 1000 elements that is already sorted?

4.[2p] A random permutation of n elements has, on average, how many inversions?

5.[3p] Which of these are true of selection sort?

6.[3p] To order a table by department and, within each department, by surname, using a stable sort, you should

7.[2p] Insertion sort runs in linear time on input whose inversion count is O(n).

8.[2p] An insertion sort takes 5.0 seconds on 100,000 random records. Roughly how many seconds does it take on 400,000 random records?

9.[3p] Any algorithm that only swaps adjacent elements is stuck at Θ(n2) on random input because

1.[3p]
How many inversions does the array 5, 2, 4, 6, 1, 3 contain?

2.[3p]
Insertion sort's number of moves is exactly equal to

3.[2p]
How many comparisons does selection sort make on an array of 1000 elements that is already sorted?

4.[2p]
A random permutation of $n$ elements has, on average, how many inversions?

5.[3p]
Which of these are true of selection sort?

6.[3p]
To order a table by department and, within each department, by surname, using a stable sort, you should

7.[2p]
Insertion sort runs in linear time on input whose inversion count is $O (n)$ .

8.[2p]
An insertion sort takes 5.0 seconds on 100,000 random records. Roughly how many seconds does it take on 400,000 random records?

9.[3p]
Any algorithm that only swaps adjacent elements is stuck at $Θ (n^{2})$ on random input because