CSCI 362: Elementary Sorting Algorithms

Handout

Grab the handout tarfile from Autolab

You can extract a tarfile with the following command:

tar xvf handout.tar

Overview

Implement optimized bubble sort, insertion sort, and selection sort, and compare their performance. Implement each as a separate function that takes a vector<T> by reference.

  1. Input the following:

  1. After you populate the initial vector (‘A’), use it to construct ONE additional vector named ‘ACopy’.

  2. Sort ‘A’ with the algorithm the user specifies, and ‘ACopy’ with std::sort.

  3. Check that your sorting algorithm is correct by comparing ‘A’ with ‘ACopy’ using operator== for vector. If you do NOT do this, your sorting algorithms will be considered incorrect!

  4. To better understand the efficiency of each algorithm, count the number of KEY comparisons and swaps each sort performs. Count ONLY comparisons in which one key is compared to another key (e.g., A[i] < A[j]), and NOT comparisons to check if a subscript is in bounds.

ENSURE all of your sorts are correct. An incorrect sort will result in a MAJOR deduction.

AVOID global variables and USE standard C++ range conventions [ begin, end ).

Input Specification

  1. size of the vector (‘N’, of type size_t)
  2. the sorting algorithm (‘algorithm’, of type std::string: USE ‘bubble’, ‘insertion’, or ‘selection’)
  3. the sequence type (‘type’, of type char: USE ‘a’ for ascending, ‘d’ for descending, and ‘r’ for random).
    • If the sequence type is ‘r’, input a non-negative seed.

Use PRECISELY the format below with the EXACT same SPACING and SPELLING.

N         ==> <UserInput>
Algorithm ==> <UserInput>
Type      ==> <UserInput>
Seed      ==> <UserInput> // ONLY if Type is 'r'

Output Specification

Output the number of key comparisons, the number of swaps, and whether the algorithm correctly sorted the input vector, by comparing ‘A’ to the result produced by std::sort. If the vectors are the same, output ‘yes’, otherwise output ‘no’.

Use PRECISELY the format below with the EXACT same SPACING and SPELLING.

Sample Output

N         ==> 1000
Algorithm ==> insertion
Type      ==> d

# Compares: 499500
# Swaps   : 0
Sort ok?    yes

Required Methods

Include at LEAST the following methods.

// Perform an optimized bubble sort on 'v'
// Update the number of comparisons and swaps performed
template <typename T>
void
bubbleSort (vector<T>& v, Statistics& stat);

// Perform an insertion sort on 'v'
// Update the number of comparisons performed
template <typename T>
size_t
insertionSort (vector<T>& v), Statistics& stat);

// Perform a selection sort on 'v'
// Update the number of comparisons and swaps performed
template <typename T>
void
selectionSort (vector<T>& v, Statistics& stat);

Hints

The sort routines should initialize the two member fields of Statistics ‘numCompares’ and ‘numSwaps’ to zero.

To correctly count the number of comparisons in ‘insertionSort’ you’ll have to introduce an ‘if’ statement.

Use operator== to test if your sort results match those of std::sort. Do NOT use any other method.

Style

Use good programming style:

Submission

Please submit a tarball containing two files: driver.cpp and sort.hpp to autolab

You can generate this tarfile (called handin.tar) by invoking the following command:

make handin

Grading

This lab is graded out of 75 points