Hvordan løsr jeg opgaven?

Understand the use of a generic container in a specific context. Understand efficiency of an algorithm.

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.

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).


Ville gerne have en løsning?