 |
Project 1 |
| CSC 220 |
using differing initial arrays and vectors of differing sizes
Assignment
Investigate and find some interesting and significant conclusions about the usefulness of at least two different sorts, using at least three different initial configurations, and at least four different sizes of both vectors and arrays. You may use as many additional sorts, initial distributions, and sizes as you want. You may also include the sort routine from the Standard Template Library, if you wish. Then create a program that does the sorts and prints out the results in a table form that illustrates your conclusions. You will be supplied with the code that creates a testing platform for you to investigate your various sorting routines (see below).
Of the two sorts, both must be your code, and not the supplied code. Both sorts must be different from the supplied sorts, or a significant variation on a supplied sort. You may use any three of the supplied initial configurations, or create one of your own.
You must use at least four different array sizes from an increasing progression such as:
125, 250, 500, 1000, 2000, 4000, 8000, 16000, 32000, 64000, 128000, 256000, 512000, 1024000, 2048000, 4096000, 8192000
100, 316, 1000, 3162, 10000, 31622, 100000, 316228, 1000000, 3162277 10000000
(these are logarithmic values of 10 — 2.0 2.5 3.0 3.5 4.0 etc.)
250, 1000; 4000; 16000; 64000, 256000, 1024000, 4096000
Use the same progression for all your sorts, but since some sorts are much faster than others you may have to use the smaller sizes for the slow sorts, and the larger sizes for the faster sorts. Pick sizes that keep your sorts between about a second to about 20 seconds in duration. There is a utility Timer class, with a function, check(), that you can include in your outer loops to time and limit the sort.
Your program must run all the required sorts in real time and then print the results in appropriate tables to illustrate your conclusion. The conclusion must be a significant fact or comparison between the two sorts, not just the fact that a sort of order O(n) is significantly slower than a sort of order O(n log n).
You may run the program to gather data on any computer you want, but make sure you generate the data consistently. Particularly make sure that your data is not corrupted by outside influences such as thrashing of the operating system. Also make sure that you do all of the tests with no other programs running in a Windows system, or with no other users logged on to a Linux system. You are encouraged to check your values by doing multiple runs on different computers.
The program you hand in must be the supplied in a Project1 directory, with the void main() program in a file called Project1.cpp. Your Project must run on Visual C++, as set up in the M22x labs, using a supplied default workspace. It must be written in good Object Oriented ANSI C++, with no Win32 or Linux specific extensions.
Supplied Testing Code
The files in the Project1 directory on Faculty on Wrath provide a basis for you to compare various different sort functions, using both arrays and vectors in various different initial states. It is designed so that you can use some of the classes directly without modification, such as Displayer and Tester. Some of the classes are meant for you to modify extensively, like Sorter. The class Parser is a test bed for you to get an idea of the time it takes to sort various arrays and vectors, and is not meant to be part of your final project.
The Project1.cpp testing program is currently partially configured for the following sorts:
Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, Quick Sort
using the following configurations of initial integer arrays:
totally random, partially random, some scattered random, shuffled, backwards, alternating, peaking in the middle, highly repetitious.
There is also a stub function which you can use to code an additional initial configuration, currently creating totally sorted arrays, which you can modify to be a custom initial configurations:
newarray
Example distributions with 10 integers
|
Totally Random |
can have duplicates |
4 |
8 |
2 |
9 |
1 |
8 |
3 |
2 |
7 |
9 |
|
Partially Random |
can have duplicates |
2 |
1 |
5 |
3 |
6 |
7 |
7 |
6 |
9 |
10 |
|
Some Random |
can have duplicates |
1 |
2 |
3 |
4 |
9 |
6 |
7 |
8 |
9 |
10 |
|
Shuffled |
no duplicates |
2 |
3 |
7 |
9 |
1 |
6 |
5 |
10 |
4 |
8 |
| Forwards | no duplicates | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
Backwards |
no duplicates |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
|
Alternating |
no duplicates |
1 |
10 |
2 |
9 |
3 |
8 |
4 |
7 |
5 |
6 |
|
Peaking in Middle |
no duplicates |
1 |
3 |
5 |
7 |
9 |
10 |
8 |
6 |
4 |
2 |
|
Repetitious |
has many duplicates |
2 |
1 |
1 |
3 |
2 |
3 |
3 |
1 |
1 |
2 |
Grading
Project 1 is worth 8 points toward the final grade. It will be graded according to the criteria on the Project 1 Grade Report. You will be given a hard-copy of your Grade Report during the Interactive Grading (see Date immediately following). You are required to keep the Grade Reports for all your projects until you have your final grade at the end of the semester, in case there is a question about the grade of any of your projects.
Your project will be interactively graded on Monday, October 1st. On Wednesday, September 29th., each student will sign up for a specific 10 minute period for grading on the following Monday. You may have your project graded before October 1st, if you like, by making arrangements with the instructor. You will have until the interactive grading date of Project 3 to upgrade any deficiencies in your Project 2.
 |
Office: M233a | Phone: 353-2250 | sbadman@parkland.edu | |