hi..i am new progarmmer for c++ and i really need help coz i have lots of problom while doing progamming in c++. i need guidance how i can implement my code or if someone could start the code for so it might be easy to continue. i need everything in details..coz if there is soe code line then i nee dto know why it does like that and so on..im attaching a file of my assignmnet
maggz Newbie Poster
Generic Dynamic Array with Sorting Algorithm
Perspective
Understand the use of a generic container in a specific context. Understand efficiency of an algorithm.
Assignment
For the use in a generic library your array should be expanded.
At this point you are not expected to know the impact on the design of the array why the some basic design requirements follows.
intensive insert and delete operations anywhere in the container
different kind of sorting algorithms will be used
first when the application is designed the actual type to be stored is known (and that may be any type)
The customer finds it hard to develop algorithms to sort items in the list. Therefore you are requested to make a sort() algorithm in your list.
Hint: Choose a simple one like insert sort or selection sort; more efficient algorithms like quick sort, heap sort, and merge sort are more complicated to implement (will be covered in a later session).
For each design decision you must argue for your choice, pre-and cons.
Algorithm Efficiency
As part of efficiency measurements you have to analyze the running time (O notation) of your algorithms, best-case, average-case and worst-case.
Your management wants a comparison among different techniques:
o Sorting a vector (from the STL) using selection sort and quick sort
o Sorting your array using newly developed algorithm
In order to make it possible to compare the different containers/algorithms you must (of course) use the same data to all of them.
a) create a vector with random numbers (v_rand)
b) create a new vector, copy a) hereto and sort it in ascending order (v_ascend)
c) create a new vector, copy a) hereto and sort it in descending order (v_descend)
It may be reasonably to assume that best-case and worst-case may arise if the data is already ordered as b) and c), but this is not always true.
In turn copy a), b) and c) to the container under test and start the measurement:
o start the stopwatch
o do the sorting
o stop the stopwatch and read the time elapsed
In a non-real-time environment (as in your Windows PC) time measurements will not be accurate. Therefore you should relate the measurements e.g.:
J2C++ Mandatory Assignment 3 Spring 207
Data Structures and Algorithm Generic Dynamic Array
time_relation = time(500.000 elements)/time(10.000 elements)
and relate the the corresponding O for the algorithm used e.g.:
O(n2) -> O_relation = (500.000/10.000)2
Compare the time_relation and the O_relation.
Do the calculations lead to expected results? (Eventually why not?)
Tools
ls:
o Selection sort
o Quick sort
o Random.h (0 231 -1) [The standard random generator has max. span 0215-1]
To find corresponding Os please consult the book Data Structures with C++
o An example in how to use above
Test
The test should be divided into two
1. Test insert and retrieve and delete of a number of elements anywhere in the list
2. Test the efficiency of your sorting algorithm. Estimate the O() with proper documentation (ref. Algorithm Efficiency above)
Documentation
All classes and functions must be documented in such a way that any other software developer will be able to use your solution.
The names of the developers must be stated in the head of all classes together with dates and revision number.
All prototypes of the functions (in header file) should have stated the pre and post
- 2 Contributors
- forum1 Reply
- 63 Views
- 6 Hours Discussion Span
- comment Latest Post by Ancient Dragon
Ancient Dragon 5,243
>>if someone could start the code for so it might be easy to continue
Start with this:
#include <iostream>
using std::cout;
int main()
{
// put your code here
return 0;
}