Week 4

Question 1

What are the three simple algorithms?

Answer 1

Bubble sort, selection sort, insertion sort.

Question 2

What are the two complex sorting algorithms.

Answer 2

Merge sort and quick sort.

Question 3

What is the complexity for the best case of insertion sort?

Answer 3

The best case complexity is O(n)

Question 4

What is the complexity for the average and worst case for insertion sort.

Answer 4

The worst case is O(n^2) and the average case is O(n^2).

Question 5

What is the theoretical best running time we can achieve for a comparision based sort?

Answer 5

O(n log(n)) for the worst and average cases.

Question 6

What is Quick Sort?

Answer 6

It is another divide and conquer based technique.

Choose one array element to be the pivot and partitions the array into 2 sub arrays such that,
* subarray 1 contains only elements less than or equal to the pivot
* Sub array 2 contains only elements greater than or equal to the pivot
* The pivot stays in place and is in its final position.

Question 7

For quick sort, why is it inefficient if the pivot is the first or last element?

Answer 7

The algorithm will fare poorly when the array is nearly in sorted order.

Try to choose pivots that divide the array into nearly equal halves.

Question 8

During quick sort what happens when we exchange the first or the last element?

Answer 8

During partitioning, the pivot is sometimes moved out of the way by exchanging with the first or last element.

To avoid index bound checks, the largest element is put into the last array position. This is done before the actual sort.

Question 9

In quick sort do we care if we choose the partition as the first, last or middle? (Assume the data is random).

Answer 9

No since the data is random, the choice won’t matter.

Question 10

When does the worst case occur in quick sort?

Answer 10

It occurs when the pivot is the largest or the smallest element.

Results in a sub array of size 0 and another of size n -1.

Complexity of O(n^2)

Question 11

When does the best case occur for quick sort?

Answer 11

The best case occurs when the pivots always create equal sized subarrays. The complexity is O(nlog(n))

Question 12

For quick sort what is the average case complexity?

Answer 12

The average case complexity is O(nlog(n)).

Question 13

What are the advantages of quick sort vs merge sort?

Answer 13

Quick sort is normally the quickest algorthm, (unless the pivot is chosen as the smallest or largest).

Unlike merge sort, quick sort does not need extra memory.

Quick sort is not appropriate for an array that is less than 30 items. (In this case an insertion sort is better).

Question 14

What is an internal sort?

Answer 14

Data is kept in primary memory.

Question 15

What is an external sort?

Answer 15

Data is kept in secondary storage. Used when data is too large to be loaded to memory at once.

Not all elements are accessible.

Question 16

What is an inplace sort.

Answer 16

A sort achieved by exchanging items in place within an array.

Does not use extra memory.

Question 17

What is a stable sort?

Answer 17

A stable sort is a sort that preserves the order of equal keys.

This may be important if there are duplicate key values.

Question 18

What do we consider for sorting

Answer 18

Comparisons

Data movements, exchanges or swaps.

Question 19

What is a bubble sort?

Answer 19

Compares successive pairs of items
* The largest item bubbles up to the end
* The next largest bubbles up, etc.

Question 20

True or false, in a bubble sort, the number of comparisons is the same for best, average and worst cases.

Answer 20

This is true.

Question 21

What is the complexity for a bubble sort?

Answer 21

It is O(n^2) regardless of input order.

Question 22

What is a selection sort?

Answer 22

Works by selecting the smallest item above the current item in the array and swaps them.

This is repeated up to the second last item.

Question 23

True or false, for a selection sort, the number of comparisions is the same for the best, average and worst cases.

Answer 23

This is true.

Question 24

What is an insertion sort?

Answer 24

Starts from the 2nd element of the sequence, and compares the item to the left.

If the current is higher, it does nothing, but if it is less, it traverses backwards to find the correct position.

Question 25

What is the complexity for a selection sort?

Answer 25

The worst case is O(n^2).
The best case is when it is already sorted: no index update.
The average case is O(n^2)

Question 26

Is a selection sort stable?

Answer 26

No, it is unstable.