Lecture 15 - October 15, 2007

First we talked about our linked list interpretation of a queue.

We discussed the difference in our code if there were a showQueue procedure in our specification and body VS. what we would have to do to show the Queue in our test program if it wasn't there.

Searches

Binary Search

In order to perform this search elements had to be in order. In order to write a binary search, you need to know if the order is ascending or descending

Sequential Search

Elements do not have to be in order.

NOTE: the links in these notes do not work. The information below on the bubble, insertion and selection sorts comes from Wikipedia.

Sorts

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top (i.e. the beginning) of the list via the swaps. (Another opinion: it gets its name from the way greater elements "bubble" to the end.) Because it only uses comparisons to operate on elements, it is a comparison sort. This is the easiest comparison sort to implement.

A simple way to express bubble sort in pseudocode is as follows:

procedure bubbleSort( A : list of sortable items ) defined as:
 do
 swapped := false
 for each i in 0 to length( A ) - 2 do:
 if A[ i ] > A[ i + 1 ] then
 swap( A[ i ], A[ i + 1 ] )
 swapped := true
 end if
 end for
 while swapped
end procedure
 

9

20

8

14

10

6

60

11

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:

Simple to implement

Efficient on (quite) small data sets

Efficient on data sets which are already substantially sorted: it runs in O(n + d) time, where d is the number of inversions

More efficient in practice than most other simple O(n²) algorithms such as selection sort or bubble sort: the average time is n²/4 and it is linear in the best case

Stable (does not change the relative order of elements with equal keys)

In-place (only requires a constant amount O(1) of extra memory space)

A simple pseudocode version of the complete algorithm follows, where the arrays are zero-based:

 insertionSort(array A)
 for i <- 1 to length[A]-1 do
 value <- A[i] 
 j <- i-1
 while j >= 0 and A[j] > value do 
 A[j + 1] = A[j]
 j <- j-1
 A[j+1] <- value

9

20

8

14

10

6

60

11

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has Θ(n²) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations. It works as follows:

1. Find the minimum value in the list

2. Swap it with the value in the first position

3. Repeat the steps above for remainder of the list (starting at the second position)

9

20

8

14

10

6

60

11

Quicksort

Instead of reading wikipedia for this one, trace the code on pages 792 and 793 of our text with the following set of data. Note that the pivot element used in the algorithm is the first element in the array not the middle element.

9

20

8

14

10

6

60

11

Here is a nice URL for some sorting demos (this link should be live)

http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html

Big O

We talked about Big O notation for describing the amount of work done by an algorithm or a section of code.

We said

· that binary search is O(log₂n)

· that the code segment below

for j in 1..n loop

for k in 1.. n loop

….

end loop

end loop is O(n²)

· that sequential search is O( n )

· that bubble sort, selection sort, and insertion sort are all O(n²) algorithms

· that quicksort is O(nlog₂n)