Anne Dawson: CSCI201A_LAB8_FA04.htm

Last updated: Thursday 11th November 2004, 15:56 PT

This document is subject to change without notice.

Please report any errors or omissions in this document:

adawson@coquitlamcollege.com

Special instructions:

This is a timed lab and students will work as individuals.

For this lab only, team work is NOT allowed, but you may use the Internet,

your notes and your textbooks for research purposes.

For this lab only, instructor assistance is NOT available.

CSCI201A – Data and Program Organization (Data Structures)

Fall 2004

Lab Assignment 8

Date: Tuesday 16th November 2004.

Start time: 10:05am

End time: 12:05pm

The \Week11\Lab8 folder will be closed at 12:05pm precisely.

You must save your work before this time. Absolutely no late submissions are accepted.

Aim to complete as much as you can of the following:

Purpose: To implement and investigate the efficiency of two Bubblesort algorithms.

Specification : One of the simplest sorting algorithms is known as the bubblesort. The algorithm is as follows:

Beginning at the first element of the list, compare each element with the next element in the list. If an element is greater than its successor, swap the two elements. To completely sort the list, you need to perform this process n -1 times on a list of length n.

(a) Run through the bubblesort algorithm by hand on this list:

4 9 2 1 5

(Using a Microsoft Word document named Lab8.doc, write down the sequence of steps to sort the list)

(b) Write a C++ or Java program implementing the bubblesort algorithm on an array. Use your program to count the number of assignments and comparisons done by the algorithm on lists of lengths from 10 up to 1000.

(c) In Lab8.doc describe the graphs of number of comparison steps on the y axis against list length on the x axis, and of assignment steps on the y axis against list length on the x axis. If the two graphs differ or coincide, explain why. Use these graphs to deduce the complexity of the algorithm, and give your answer using big-oh notation.

(d) The bubblesort algorithm may be improved by noticing the following points:

· It is easy to detect when the list is completely sorted, since no swaps will be done on a given pass through the list. You can therefore reduce the number of comparisons required if you stop the algorithm after the first pass where no swaps are done.

· On the first pass, the largest element will be moved to its correct location in the list; on the second pass, the second largest element will be moved to its correct location, and so on. You therefore do not need to scan the entire list after the first pass; rather, on pass m, you need compare only elements 1 through n-m with their successors.

Modify your bubblesort program to implement these improvements and do the efficiency checks again. What effects do the changes have?

Assignment points will be based on the following marking scheme:

Category	Points	Description
Comments	10	Source code should be commented as recommended.
Output	10	Program prompts and/or outputs should be user-friendly.
Coding Style	10	The source code should be indented properly, use meaningful variable names, use good programming practices, etc. See the book, course web site and lectures for examples.
Part (a)	10	As per specification
Part (b)	20	Implemented as per specification
Part (c)	20	Implemented as per specification
Part (d)	20	Implemented as per specification

Source Code Format : As stated above, the source code should follow good programming style. In addition, each file should start with a comment block that contains the following information:

# File: lab8.cpp or lab8.java

# Purpose: Implementation of the Bubblesort algorithm

# Programmer: [your name]

# Course: CSCI201A

# Date:

# Test data: