Assignment 10 – Sorting Algorithms



Assignment 10 – Sorting Algorithms

Dean Zeller Due: Thursday, November 16th by 2:00 pm

CS33001 10 points

Fall, 2006

Objective: The student will implement various sorting algorithms and calculate the work required in terms of swaps and comparisons required.

Background: Sorting

One of the richest and most studied fields in computer science is sorting algorithms. Using comparisons to sort items is useful for nearly every algorithmic problem. In this assignment, you will implement and compare sorting algorithms and measure their efficiency in terms of swaps and comparisons. Your overall goal is to create a sort demonstration similar to those available on the Internet.

Program Architecture

Functions Use functions to modularize your code. The following is a suggestion on how to organize your functions.

customer.h header file for customer functions

customer.cpp implementation of the customer functions

custtable.h header file for table functions

custtable.cpp implementation of the table functions

sortdemo.cpp sorting demo interface

Documentation Each function must include a documentation block describing the input, output, and method of solving the problem. Create documentation for the main program describing the program overall. Use proper indentation and self-descriptive variable names.

Instructions

You have been given the skeleton code to implement a bubblesort algorithm on a set of customer data. In the process of completing a sort, the number of swaps and comparisons are recorded. You are to implement at least X additional sort algorithms following this template. Some algorithms will be discussed in class, and others are available on the Internet.

Interface

Input will be controlled by the user giving menu commands similar in style to the previous assignments. The program must accept the commands below from the user. Additional sorting algorithms implemented should have commands as well.

a or A Add a new customer to the table.

d or D Display. Use the display method to list the customers currently in the table.

u or U Unsort – randomly shuffle the order of the customers in the table

b or B Bubble sort

appropriate letters Additional sorting algorithms (see below)

x or X Exit the program

anything else Give an error message and print the interface options.

Grading

You will be graded on the following criteria:

Accuracy Correctly implementing and using the sorting algorithms

Readability Documentation, descriptive variable names, and indenting

Testing Ensuring the code works for a variety of inputs, showing all program features work properly

Creativity Using new methods to solve the problem

Extra Credit

This assignment is rife with extra credit opportunities. Because of the open-endedness of the assignment, write a report briefly explaining the features and algorithms implemented. If you don’t write a report, I will assume you didn’t do any extra credit. If enough extra credit is completed, I will consider replacing a previous grade. Extra points will be given for including the following features:

Analysis Complete the CS10051 sorting assignment

Quantity Additional sorting algorithms features

Flexibility Allow user to sort by customer name or an additional field, and in either ascending or descending order

Visual Provide a visual demonstration/animation showing each step of the sort

Turning in your assignment

1. Print all C++ and header files.

2. Print a test of your program with sufficient test input to demonstrate the functionality.

Sorting Algorithm Info

Websites







O(n2)-class algorithms

Bubble sort

Insertion sort

Selection sort

Shell sort

Shaker sort

O(nlgn)-class algorithms

Quick sort

Merge sort

Heap sort

Hybrid sort

Data specific O(n)-class algorithms

Bucket sort

Radix sort

Inefficient algorithms

Stooge sort (O(n2.67))

Bozo sort (O(())

Challenge

Create your own sort (Jump sort)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download