Deck 8: Sorting

Question 1

The number of comparisons for a selection sort is represented by the series: (n - 1) + (n - 2) + ... + 3 + 2 + 1

Answer 1

True

Question 2

Insertion sort is considered a quadratic sort.

Answer 2

True

Question 3

With respect to selection sort, the number of comparisons is O(n).

Answer 3

False

Question 4

The improvement of Shell sort over insertion sort is much more significant for small arrays.

Question 5

The method sort(int[] items), in class java.util.Arrays, sorts the array item in ascending order.

Question 6

A class that implements the Comparable interface must define a(n) ____________________ method that determines the natural ordering of its objects.

Question 7

____________________ sorts an array by making several passes through the array, selecting the next smallest item each time and placing it where it belongs in the array.

Question 8

In the best case, selection sort makes O(______) comparisons.

Question 9

With respect to merge sort, additional space usage is O(___________________).

Question 10

The idea behind ____________________ sort is to sort many smaller subarrays using insertion sort before sorting the entire array.

Question 11

____________________ sort has O(n^3/2) or better performance.

Question 12

Whenever a recursive method is called, a copy of the local variables is saved on the run-time ____________________.

Question 13

The Java API ____________________ provides a class Arrays with several overloaded sort methods for different array types.

Question 14

Insertion sort is an example of a(n) ____________________ sorting algorithm.

Question 15

You can think of the ____________________ sort as a divide-and-conquer approach to insertion sort.

Question 16

The following represents the ____ sort algorithm.
Set the initial value of gap to n / 2.
While gap > 0
For each array element from position gap to the last element
Insert this element where it belongs in its subarray.
If gap is 2, set it to 1.
Else gap = gap/2.2.

A) Shell
B) Heap
C) Insertion
D) Quick

Question 17

The following is the ____ algorithm.
Access the first item from both sequences.
While not finished with either sequence
Compare the current items from the two sequences, copy the smaller current item to the output sequence, and
Access the next item from the input sequence whose item was copied
Copy any remaining items from the first sequence to the output sequence.
Copy any remaining items from the second sequence to the output sequence.

A) Shell sort
B) Selection sort
C) Merge sort
D) Heapsort

Question 18

The following is the ____ algorithm
For fill = 0 to n - 2 do
Set posMin to the subscript of the smallest item starting at subscript fill.
Exchange the item at posMin with the one at fill.

A) Heapsort
B) Insertion sort
C) Selection sort
D) Merge sort

Question 19

In merge sort, the total effort to reconstruct the sorted array through merging is ____.

A) O(1)
B) O(log₂n)
C) O(n log n)
D) O(n²)

Question 20

Which of the following sorts is not O(n lg(n))

A) selection
B) heap
C) merge

Question 21

The best sorting algorithms provide ____ average-case behavior and are considerably faster for large arrays.

A) O(1)
B) O(n)
C) O(n²)
D) O(n log n)

Question 22

Which of the following generally gives the worst performance?

A) Selection sort
B) Bubble sort
C) Insertion sort
D) Shell sort

Question 23

Shell sort is ____ if successive powers of 2 are used for gap.

A) O(log n)
B) O(1)
C) O(log₂n)
D) O(n²)

Question 24

The following represents the algorithm for ____ sort.
For each array element from the second (nextPos = 1) to the last
Insert the element at nextPos where it belongs in the array, increasing
The length of the sorted subarray by 1 element.

A) merge
B) shell
C) selection
D) insertion

Question 25

The following is the ____ algorithm.
Build a heap by rearranging the elements in an unsorted array.
While the heap is not empty
Remove the first item from the heap by swapping it with the last item in the heap
And restoring the heap property.

A) Quicksort
B) Bubble sort
C) Merge sort
D) In-Place Heapsort