Sorting and Searching

Question 1

Selection Sort: Operation

Answer 1

Find the smallest element in a and exchange it with a[0]. Repeat the process with the subarray a[1]…a[n-1]… then sort a[n-2] and a[n-1] at the end.

Question 2

Selection Sort: Passes to sort the array

Answer 2

An array of n elements is sorted after n-1 passes.

Question 3

Selection Sort: Elements sorted after k passes

Answer 3

After the kth pass, the first k elements are in their sorted positions.

Question 4

Selection Sort: Worst Case

Answer 4

Selection Sort always requires the same number of comparisons/moves

Question 5

Selection Sort: Best Case

Answer 5

Selection Sort always requires the same number of comparisons/moves

Question 6

Insertion Sort: Operation

Answer 6

The array consists of sorted and unsorted portions. Insertion sort moves elements from the unsorted subarray to their correct positions in the sorted subarray, moving elements in the sorted subarray as necessary.

Question 7

Insertion Sort: Passes to sort the array

Answer 7

An array of n elements is sorted after n-1 passes.

Question 8

Insertion Sort: Elements sorted after k passes

Answer 8

The elements in a[0]..a[k] are sorted with respect to each other (though not necessarily in their final positions).

Question 9

Insertion Sort: Worst Case

Answer 9

The array is sorted in reverse order (maximum possible number of comparisons and moves).

Question 10

Insertion Sort: Best Case

Answer 10

The array is already sorted in increasing order (each pass involves one comparison that confirms that the sort order is correct).

Question 11

Mergesort: Operation

Answer 11

Mergesort the left and right halves of an array, then merge the two sorted lists. In doing this, n subarrays of length 1 are created and then recursively merged to form the final sorted array.

Question 12

Mergesort: Disadvantages

Answer 12

Mergesort requires a temporary array of length n to sort an array of length n, so it may not be space-efficient.

Question 13

Mergesort: Worst Case

Answer 13

The performance of mergesort is not affected by the initial ordering of elements in the array.

Question 14

Mergesort: Best Case

Answer 14

The performance of mergesort is not affected by the initial ordering of elements in the array.

Question 15

Sequential Search: Operation

Answer 15

Start at the first element and compare the key to each element. If the list is known to be sorted, the search could be stopped early if the key is less than the current element.

Question 16

Sequential Search: Best Case

Answer 16

The key is in the first slot.

Question 17

Sequential Search: Worst Case

Answer 17

The key is in the last slot or not in the array.

Question 18

Sequential Search: Average Case

Answer 18

There are n/2 comparisons.

Question 19

Binary Search: Operation

Answer 19

Find the midpoint of the array at index k and compare it to the key. If the key is less than a[k], recursively search a[0]..a[k-1]. If it is greater than a[k], recursively search a[k+1]..a[n-1].

Question 20

Binary Search: Preconditions

Answer 20

The array is sorted on the search key.

Question 21

Binary Search: Best Case

Answer 21

The key is at the midpoint of the array (i.e. a[n/2]).

Question 22

Binary Search: Worst Case

Answer 22

The key is not in the list or is at either end of a subarray (subarrays must continually be divided until a subarray of length 1 is found and tested).