FIU Programming Code for Different Sorting Algorithms Project

In this assignment, you will code for different sorting algorithms that we learned and experimentally compare their efficiencies.

1. Write six functions to code for the following six sorting algorithms in C++. Make your own header files to declare all the functions you need to implement each of these sorting algorithms. For example, for quicksort, you will have a header file such as “quicksort.h”, in which you will declare all the functions that you need to perform quicksort. Then you will include these header files in your main cpp program, in which you will implement and call all these functions. The input to all these sorts is the array of unsorted integers, the size of the array, and if required the start and end variables. The output of each of these sorts is the sorted array of integers printed on the console. Test these sorts with the unsorted array – A [89, 373, 1, 783, 23, 987, 12, 65, 28, 17].

a. Selection Sort

b. Bubble Sort

c. Insertion Sort

d. Merge Sort

e. Quick Sort

f. Heap Sort

2. Write a function to generate 10 unique dataset files of unsorted integers separated by a comma “,”. E.g., 34, 32421, 124124, 67, 92, … The sizes of these 10 datasets are (n) – 1000, 4000, 8000, 10000, 40000, 80000, 100000, 400000, 800000, 1000000. Generate random integers between 0 to 1,000,000 as the elements of each dataset. This function does not take any input arguments. This function generates and saves 10 “.txt” files. The output of this function is just a print statement to console that file generation completed.

3. Write a function to read the data from the above-generated files and construct 10 unsorted arrays. This function does not take any input arguments. This function declares 10 arrays of sizes sufficient to store the content of the above-generated files and constructs these arrays by reading these files. The output of this function is just a print statement to console that unsorted array generation completed.

4. Use the above-generated 10 arrays to give as the input to your six sorting functions and measure the duration of each function. Comment the statements you used to print the sorted array after each sorting function, as you need to measure only the time taken to sort. The output of each sort is the time taken in milliseconds to sort the given unsorted array. You can use “#include ” or “#include” to measure the duration of a function in C++. While measuring the time you only need to measure the time taken by each sorting algorithm to convert the unsorted array into a sorted array. Note: The additional time taken, such as to construct your input unsorted array and to print your sorted array to console should not be included while measuring the duration of the sort.

5. Repeat the above duration measurement of each sort 3 times to calculate the average duration of each sort for each array. Plot a graph for the duration of different sorting algorithms including Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, and Heap Sort. The x-axis of the graph will be the dataset size (n) (i.e., same as your array size), and the y-axis will be the average of the three executions for each dataset size. Thus, your x-axis will have ten labels and value of runtime on the y-axis for each label. Draw the above-described dataset size to runtime curve for the six sorting algorithms (Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, and Heap Sort) in the same graph sharing the same axis labels. Add Legend entry for each curve on the graph and use a different pattern like dotted, dashed, straight line, and different bullet dimensions and color for each curve of a sorting algorithm. Note: You have to generate datasets (i.e., unsorted arrays) only once and you can reuse the same datasets across three executions of each sort and also across different sorting algorithms.

Submit the PDF with your name, the image of the graph, and your pointwise explanations of your observations from everything you do in this assignment and the results you observe. You should also submit an additional zip folder within which you need to have all your code files, README file with the compile and execution instructions, and your pre-compiled “.exe” executable files. On top of all the files, you need to mention your name as comments. All submitted PDF files must be named as “_.pdf”. For example, it will be “jankibhimani_sorting.pdf” for Prof. Janki Bhimani. You need to submit the single main file that implements all the above functions and is named as “_sort.cpp”. All submitted code header files must be named as “_“. For example, “jankibhimani_quicksort.h”. The zip folder containing all the files except PDF should be named as “_code.zip”. For example, it will be “jankibhimani_code.zip”.

Please follow the “Guidelines for Software Engineering Techniques.pdf” and “Assignments and Project Style and Documentation Guidelines.pdf” made available to you in your Student Resources module for other document editing and code format guidelines.

Sample Graph (Note – your graph will have the curve showing the results you get by running the algorithms):

Guidelines for Software Engineering Techniques
Specification: You must first understand exactly what the problem is that you are solving. You
may get an initial program specification from a customer or another non-technical person, so
it may at first be imprecise. Specification requires that you have a complete understanding of
many issues including: what the input data is, what types of data are valid, what sort of interface
the program will have, what input errors need to be detected, what assumptions are made, what
special cases need to be handled, what is the output, what will be documented, what changes
might be made after completion, etc. Note that the specification should not include the method
of solving the problem.
Design: After you know exactly what problem is to be solved, a solution to the problem can
be designed, encompassing both algorithms and abstract data types. For large programs, this is
usually broken down into well-defined smaller problems that can be solved using modules that
are reusable and (somewhat) independent. (For example, a sorting routine can be used by many
programs but, aside from the interface, is independent of them.) A module can be a single
function or a group of functions. The input, output, purpose, and assumptions of each module
should be specified. The design should be independent of the implementation.
Verification: It is possible, in some cases, to prove that an algorithm is correct. For example,
design test cases with different input data and validating the expected output with the output
of algorithm.
EECE2560 Fundamentals of Engineering Algorithms
Department of Electrical and Computer Engineering
Style and Documentation Guidelines
All code you submit must meet the requirements listed below. The functions and declarations at
the bottom give examples of how your code should look.
• Each file should begin with a comment that explains what the file contains. The top of each
file should include your name and the problem set number.
• Your code and documentation should be no more than 80 columns wide. Text should also not
usually be wrapped around at a width of less than 80 columns. In other words, use the full
80 characters. Do not put function parameters or long expressions on separate lines unless
you have to.
• Each function must be documented as shown below. At the top of the function (or in the
prototype), precisely describe what the function does, what the input parameters are, and
what assumptions the function makes, if any. These comments should be placed immediately
after the function name or prototype. You do not need to document code in libraries that I
have given you.
• Within the code, put comments that describe how the function works.
• Put spaces on either side of arithmetic (⇤, /, +, ), logical (&&, ||, !), relational (=
, ==, ! =) and assignment operators (= + =, =, ⇤ =, / =), and the > operators.
• Put brackets { } on lines by themselves, and indent them as shown below.
• Avoid using global variables, except for certain constants. Global identifiers should be declared starting in the leftmost column. All other identifiers, including local variables, should
be indented at least 3 columns.
• All #include statements should be at the top of each file. Global variables should also be
placed at the top of each file.
• Comments on lines by themselves should be indented the same amount as the lines they refer
to, and should have a blank line before them. Multi-line comments usually should have an
empty space after them. For instance, instead of:
x = 0;
// list (no shift if index == size+1)
for (int pos = size; pos >= index; –pos)
items[translate(pos+1)] = items[translate(pos)];
// next code
use
x = 0;
// list (no shift if index == size+1)
for (int pos = size; pos >= index; –pos)
items[translate(pos+1)] = items[translate(pos)];
// next code
• if statements, for-loops, while-loops and do-while loops should be preceded by a blank line
and followed by a blank line (or a line with a bracket).
• Put spaces before, but not after, the arguments of for-loops, and put a space after the “if,”
“for,” and while keywords. For instance, instead of
for(int pos = size;pos>=index ;–pos)
use
for (int pos = size; pos >= index; –pos);
• Final brackets } that are more than about 10 lines from the initial bracket should be commented, as shown below.
• Comments within the class declarations (at the end of the lines) should be lined up as much
as possible.
• Do not put extra spaces between parentheses in expressions:
For example, instead of
while ( (x N) ),
use
while ((x N)).
• The commas separating the list of parameters in function calls and prototypes should be
followed by a space, as in the following:
void swap(int &x, int &y)
2
// Homework 1
Ningfang
Mi
Janki Bhimani
//
ningfang@ece.neu.edu
janki.bhimani@fiu.edu
//
// Main program file for homework 1. Contains declarations for Node,
// linkedListInsert, insert, and find.
//
#include “ListException.h”
#include
using namespace std;
typedef desired-item-type ItemType;
struct Node
// The basic Node type used in the linked list
{
ItemType item;
Node *next;
}; // end struct
void List::linkedListInsert(Node *headPtr, ItemType newItem)
// Inserts a new node containing item newItem into the list pointed
// to by headPtr.
{
int x,y;
float f = 1.2;
if ((headPtr == NULL) || (newItem < headPtr->item))
{
// base case: insert newItem at beginning
// of the linked list to which headPtr points
Node *newPtr = new Node;
if (newPtr == NULL)
{
cout
\\ getLength()+1.
{
success = bool( (index >= 1) && (index = index toward the end of the
// list (no shift if index == size+1)
for (int pos = size; pos >= index; –pos)
items[translate(pos+1)] = items[translate(pos)];
// insert new item
items[translate(index)] = newItem;
++size; // increase the size of the list by one
} // end if
} // end insert
ListNode * List::find(int index) const
// Locates a specified node in a linked list. Index is the number of the
// desired node. Returns a pointer to the desired node. If index < 1 or // index > the number of nodes in the list, returns NULL.
{
if ((index < 1) || (index > getLength()))
return NULL;
else // count from the beginning of the list
{
ListNode *cur = head;
for (int skip = 1; skip < index; ++skip) cur = cur->next;
return cur;
} // end if
} // end find
4
//
//
//
//
Header file TableH.h for the ADT table.
Hash table implementation.
Assumption: A table contains at most one item with a
given search key at any time.
#include “ChainNode.h”
#include “HashTableException.h”
typedef KeyedItem TableItemType;
class HashTable
{
public:
// constructors and destructor:
HashTable();
HashTable(const HashTable& table);
~HashTable();
// table operations:
virtual bool tableIsEmpty() const;
virtual int tableGetLength() const;
virtual void tableInsert(const TableItemType& newItem)
throw (HashTableException);
virtual bool tableDelete(KeyType searchKey);
virtual bool tableRetrieve(KeyType searchKey,
TableItemType& tableItem) const;
protected:
int hashIndex(KeyType searchKey); // hash function
private:
enum {HASH_TABLE_SIZE = 101};
// size of hash table
typedef ChainNode * HashTableType[HASH_TABLE_SIZE];
HashTableType table;
int Size;
}; // end HashTable class
// hash table
// size of ADT table
// End of header file.
5