Question

Consider the algorithm below (won't fit in this tiny question box, even though it is a very simple algorithm)

1. What loop invariant does this algorithm maintain?
2. Why does it (specifically, the outer loop) only need to run for only the first \(n-1\) elements rather than for all \(n\) elements?
3. Give the best case and word case running times of selection sort in \(\big{\Theta}\) notation

Answer 1

\(\huge{\Theta}\) notation
\[#
def selection_sort(sequence):
"""
selection_sort(sequence) -> elements sorted in ascending order.

sequence -> an iterable (mutable) to be sorted in ascending order.

Implements the selection sort algorithm to perform
an in-place sorting of the elements of the sequence
A of length N such that A[0] <= A[1] <= ... <= A[N-1]
"""
for left in xrange(len(sequence)-1):
minimum = min(xrange(left, len(sequence)), key=sequence.__getitem__)
sequence[left], sequence[minimum] = sequence[minimum], sequence[left]\]

Answer 2

http://ideone.com/2spX5

Answer 3

Outer-loop runs for N iterations in both best and worst case

Answer 4

so what invariant does this loop maintain?

Answer 5

Is it that the elements from 0 to left-1 are sorted?

Answer 6

yes, but it's actually stronger than that

Answer 7

and they are the smallest elements in the array?

Answer 8

right, that's it

Answer 9

so to rephrase, the elements in sequence[0..left-1] consist of the smallest elements in the sequence, in sorted order (ascending)

Answer 10

at every point the first "left" elements in the array are the minimum elements in sorted order, so when left reaches n the entire array is sorted

Answer 11

and it only needs to run for n-1 elements, since the last 'unsorted' element once the outer-loop terminates is the largest (or among the largest if there are repeating elements in the sequence) element in the sequence, and so it will be in its correct position

Answer 12

right

Answer 13

I think the algorithm is \(\large{\Theta}(n^2)\) both best and worst case

Answer 14

yes, in this algorithm the running time is completely independent of the input so the best and worst (and average) cases are all the same

Answer 15

it takes n+n-1+n-2+n-3.....1 operations, which is O(n^2)

Answer 16

Thanks! I've got a similar question on linear search.. which I'll just post here
\[#
def linear_search(sequence, item):
"""
linear_search(iterable, object) -> int/NoneType

sequence -> An iterable to be searched
item -> The item to be found in sequence.

Returns the index of the first instance of item in the
sequence, or None if item does not exist in sequence.
"""
for index in xrange(len(sequence)):
if item == sequence[index]:
return index
return None\]

On average, how many elements of the sequence need to be checked?

Answer 17

I think it's n/2 assuming all elements are equally likely to be searched. and the worst case is n elements.

Answer 18

yep

Answer 19

in Theta notation, both worst and average case are \( \large{\Theta}(n)\)

Answer 20

right