CS 2 Lab Outline

Lab Two: Sorting and Run-Time Analysis

Purpose:

This lab will familiarize you with some basic sorting algorithms, particularly Selection Sort, Insertion Sort, and Bubble Sort. You will see how to apply these algorithms to more complicated objects. Additionally, you will be looking at ways of analyzing the running time of various algorithms.

Prerequisites:

You should understand the basics of O( ) notation. There is a discussion of Bubble Sort, Insertion Sort, and Selection Sort – these sorts are reviewed here, but a basic operating knowledge of them would be helpful.

Introduction:

One of the key topics in computer science is sorting data. There are many algorithms that have been developed for sorting. We looked at a couple of them in CS 1: selection sort and bubble sort (some of you may have seen insertion sort, depending on when you took CS 1). We will look at all three of these sorting algorithms in this lab, and later in the course we will look at some other sorting algorithms as well.

Another common topic of interest to computer scientists is run-time analysis. This is a mathematical procedure used to determine how long a program, function or algorithm takes to execute. This can be difficult in many cases, because the running time of an algorithm depends on many things:

· The speed of the computer on which the program is running.

· The processes running on the computer at the same time.

· The programming language used to write the program.

· The algorithm used to encode the program.

Since most of these factors are out of the control of the programmer, we need to focus on the algorithm. To look at the running time of algorithms independent of the machine on which they are running, we use something called O( ) notation. This is a mathematical construct that gives the running time of the algorithm not in terms of time, but in terms of the size of the input as a mathematical function.

For example, consider the following code:

for ( int i = 0; i < n; i++ ) {

array[i]++;

}

Assume that array is a valid array of numbers, how many times do we increment something in this code? We increment a number n times, so we say that this algorithm (or piece of algorithm) runs in O( n ) time. We will look at some running times in this lab.

Procedure:

1. Copy the project files for lab 2 into your directory.

2. The project file contains a completed version of insertion sort. Insertion sort is called this because the sort algorithm “grows” a sorted list on the left side of the array by inserting elements into the sorted portion of the array.

Consider the following example:

We begin by “creating” a sorted part of the list, consisting of the first element:

Now, we choose the 4, and insert it in the correct location in the sorted portion of the array.

Now, we do the same with the 23:

We continue this process, eventually arriving at a sorted array:

3. Run the program a few times and look at how the sort works. Choose different sizes of arrays and see how this affects the running time analysis. What do you think the running time of this algorithm is in O( ) notation?

4. The project file contains an incomplete version of bubble sort. Bubble sort is called this because the larger items “bubble” to the top (right) of the array. This is done by a sequence of comparisons between adjacent elements.

Consider the following example:

We begin by comparing the first two items in the array – in this case, the 15 and the 4. Since the 15 is bigger than the 4, we swap the two values:

Now, we compare the next two values – the 15 and the 23. Since the 15 is smaller than the 23, we don’t swap.

Now, compare the 23 and the 12. Since the 23 is bigger, we swap the two:

We continue this process, arriving at an array that looks like this:

This completes one pass of the bubble sort algorithm. We need to do n – 1 passes to guarantee that the sort is finished, where n is the number of items in the array.

Here are the results after passes two through seven:

Notice that the sort was complete before we stopped – this is something that can happen, but we need this many passes to make sure.

Complete the algorithm so that the sort works correctly, and so the algorithm reports the number of swaps and comparisons that it makes. How does this algorithm compare with insertion sort? What do you think the running time of this algorithm is in O( ) notation?

Be sure that you check your algorithm to make sure that it works correctly.

5. The project file also contains an incomplete version of selection sort. Selection sort is called this because the sort algorithm “selects” the smallest item in the unsorted portion of the array. It then moves this item to the left-most side of the unsorted portion of the array, merging it with the sorted portion that is growing to the left.

Consider the following example:

We begin by finding the smallest item in the array (the 3), and swapping it over to the left side of the array:

Now, find the next smallest item (skipping the 3, so we get the 4), and swap it into the place just to the right of the three. In this case, there is no movement.

We continue this process, eventually arriving at a sorted array:

Complete the algorithm so that the sort works correctly, and so the algorithm reports the number of swaps and comparisons that it makes. How does this algorithm compare with insertion sort and bubble sort? What do you think the running time of this algorithm is in O( ) notation? Be sure that you check your algorithm to make sure that it works correctly.

6. Now that you know how each sorting algorithm works, we are going to apply one of them to a more complicated object than an integer. First, save and close your lab 2 project files. Then, open your lab 1 project file for the library inventory program. We are going to add the ability to sort the book list in the library.

7. Add two command level options to the inventory program – sort the library book list by title and sort the list by author. You may use any sorting algorithm you want to implement the sort. Test the program to make sure that it works.

8. Save your files in the lab 1 directory.

/* lab2.cpp - This file demonstrates the workings of three methods

of sorting arrays of integers:

Selection Sort

Insertion Sort

Bubble Sort

Author: Scott Thede

Date: August 21, 2003

#include <iostream.h>

#include <stdlib.h>

#include <conio.h>

// Defines the size of the array we are sorting.

const int ARRAY_SIZE = 10;

// Parameters: An array of integers named array.

// Pre: None.

// Post: Each element of the array has been replaced with a random

// number between 1 and 100 (inclusive).

void randomizeArray( int array[] ) {

for ( int i = 0; i < ARRAY_SIZE; i++ )

array[i] = random( 100 ) + 1;

}

// Parameters: An array of integers named array.

// Pre: None.

// Post: Each element of the array has been printed, all of them

// on a single line.

void printArray( int array[] ) {

for ( int i = 0; i < ARRAY_SIZE; i++ )

cout << array[i] << " ";

cout << endl;

}

// Parameters: An integer first, and an array of integers named array.

// Pre: first is an index within the bounds of the array.

// Post: The index of the smallest item "to the right" of the index

// first is returned.

int findIndexSmallest( int first, int array[] ) {

int small = first;

for ( int j = first + 1; j < ARRAY_SIZE; j++ ) {

if ( array[j] < array[small] )

small = j;

}

return small;

}

// Parameters: Two integers, x and y, both reference parameters.

// Pre: None.

// Post: The values in x and y have been swapped.

void swap( int &x, int &y ) {

int temp = x;

x = y;

y = temp;

}

// Parameters: An array of integers named array.

// Pre: None.

// Post: The values in array have been sorted using insertion sort, and

// each step has been displayed.

void showInsertionSort( int array[] ) {

int nextItem;

int loc;

int countComps = 0, countSwaps = 0;

for( int unsorted = 1; unsorted < ARRAY_SIZE; unsorted++ ) {

nextItem = array[unsorted];

for( loc = unsorted; ( loc > 0 ) && ( array[loc-1] > nextItem ); loc-- ) {

array[loc] = array[loc - 1];

countComps++;

countSwaps++;

}

array[loc] = nextItem;

cout << "Current array status:" << endl;

printArray( array );

cout << "Press any key to continue." << endl;

getch();

}

cout << "Final array contents: " << endl;

printArray( array );

cout << "Number of comparisons required: " << countComps << endl;

cout << "Number of swaps required: " << countSwaps << endl;

cout << "Press any key to continue." << endl;

getch();

}

// Parameters: An array of integers named array.

// Pre: None.

// Post: The values in array have been sorted using bubble sort, and

// each step has been displayed.

void showBubbleSort( int array[] ) {

// You complete this.

}

// Parameters: An array of integers named array.

// Pre: None.

// Post: The values in array have been sorted using selection sort, and

// each step has been displayed.

void showSelectionSort( int array[] ) {

// You complete this.

}

// Parameters: None.

// Pre: None.

// Post: The menu of options has been printed to the screen.

void printMenu( ) {

clrscr( );

cout << "Choose one of these options: " << endl;

cout << endl;

cout << "1. Sort the array using Selection Sort." << endl;

cout << "2. Sort the array using Insertion Sort." << endl;

cout << "3. Sort the array using Bubble Sort." << endl;

cout << "4. Quit the program." << endl;

cout << endl;

cout << "Current array contents:" << endl;

}

// Parameters: None.

// Pre: None.

// Post: The user has entered an integer, which is returned.

int getChoice( ) {

int ch;

cout << "Enter your choice here: ";

cin >> ch;

return ch;

}

// Parameters: An integer ch, and an array of integers named array.

// Pre: None, although the user is assumed to have seen the choices

// and made one.

// Post: The action associated with the choice has been executed. If

// the choice was invalid, an error message is printed.

void processChoice( int ch, int array[] ) {

switch( ch ) {

// Choice 1: selection sort.

case 1:

showSelectionSort( array );

break;

// Choice 2: insertion sort.

case 2:

showInsertionSort( array );

break;

// Choice 3: bubble sort.

case 3:

showBubbleSort( array );

break;

// Choice 4: exit the program.

case 4:

cout << "Thank you for using the sorting program." << endl;

exit( 0 );

// Invalid choice.

default:

cout << "That was an invalid choice." << endl;

}

// Main program.

void main( ) {

int ch;

int array[ARRAY_SIZE];

// Loops forever, since the exit condition is handled in

// in the processChoice function.

while( 1 ) {

randomizeArray( array );

printMenu( );

printArray( array );

ch = getChoice( );

processChoice( ch, array );

}