Algorithms C++ Merge Sort Project Example solved

$35.00

Category: You will receive a download link of the .ZIP file upon Payment

Description

5/5 - (1 vote)

0. Objectives
This small example shows you what a C++ project look like using the merge sort that we teach
in class. You will learn coding style, directory structure, compilation flow, naming convention,
and etc. Although you do not have to submit anything, you are strongly recommended to run
this example on EDA union lab machines before you start working on your PA.
1. Readme
It is a good habit to write a README file to tell people the basic information of this software
project. The README file should contain the copyright, directory structure, compilation
information, revision history, and etc.
1. This is a mergesort example for NTUEE Algorithms students.
2. Author: created by CM Li, NTUEE
3. History: 2/16/2012 revised
4. =====
5. DIRECTORY
6. bin/ executable binary
7. doc/ documents
8. lib/ library files about time and memory usage
9. src/ source C++ codes
10. README This file
11. ======
12. GETTING STARTED
13. Please read the word file in doc/mergesort.doc.
14. To start the demo (debug version), simply follow the following steps
15. cd lib
16. make lib
17. cd ../src
18. make demo_dbg
19. cd ../bin
20. ./demo_dbg
21.
22. To use the optimized version,
23. make demo_opt
24. cd ../bin
25. ./demo_opt
26. ======
27. CONTACT
28. If any question, please email: cmli@cc.ee.ntu.edu.tw or TA.
README
2. Time and Memory Usage
A software package is a collection of related classes. Many useful classes are provided in
library so that programmers can reuse them easily. Library can be dynamic or static. In this
example, we show how to generate a useful static library for time and memory usage. A static
library contains an archive of many object files (lib*.a) and a user interface file (*.h).
2.1 tm_usage.h
First, enter the lib directory and read the tm_usage.h header file, which provides an interface of
the TmUsage library, please type:
cd lib
NTUEE Fall, 2019
2/10
1. // **************************************************************************
2. // File [ tm_usage.h ]
3. // Author [ littleshamoo ]
4. // Synopsis [ Get CPU time and Memory usage ]
5. // Date [ Ver 2.0 started 2010/03/23 ]
6. // History [ created TmStat structure to store usage ]
7. // **************************************************************************
8.
9. #ifndef _COMMON_TM_USAGE_H_
10. #define _COMMON_TM_USAGE_H_
11.
12. namespace CommonNs {
13.
14. // define a data structure to store time and memory usage
15. struct TmStat {
16. long vmSize; // in kilobytes
17. long vmPeak; // in kilobytes
18. long vmDiff; // in kilobytes
19. long rTime; // real time in micro seconds
20. long uTime; // user time in micro seconds
21. long sTime; // system time in micro seconds
22. };
23.
24. class TmUsage {
25. public:
26. TmUsage();
27. ~TmUsage();
28.
29. bool totalStart(); // start the total timer. this is called only once.
30. bool periodStart(); // start the period timer. this can be called many times
31. bool getTotalUsage(TmStat &st) const; // get the total tm usage
32. bool getPeriodUsage(TmStat &st) const; // get the priod tm usage
33. bool checkUsage(TmStat &st) const; //
34.
35. private:
36. TmStat tStart_;
37. TmStat pStart_;
38. };
39. }; // namespace
40.
41. #endif
42.
43. // **************************************************************************
44. // HOW TO USE TMUSAGE?
45. // ….
tm_usage.h
Lines 1-7: title of this .h file. Keep information about author, synopsis, and revision date.
This is a good habit to write this information for reusability and portability.
Lines 9-10: these two lines are compiler preprocessor that prevent a redundant inclusion of
tm_usage.h. Note that _TM_USAGE_H_ start and end with underscores ‘_’. This
naming tells us that this word is not a regular variable. The reason for defining this
_TM_USAGE_H_ is to prevent the compiler for including the same header file again
(in case some other programmer also includes this header file in his code.)
Line 12: Define the name space, CommonNs. This is to avoid other programmers use same
names in other codes. This is useful when many programmers work together in a
large project.
Lines 15-22: Declare a data structure to store time and memory usage. Please note that we
have three different time:
real time: the real-world time
NTUEE Fall, 2019
3/10
user time: the time to run your code in your program
system time: that time to run system jobs (such as memory allocation, file I/O) called
by your program.
Normally, we use user time + system time as the total run time of your program.
Line 24: Declare class TmUsage. Please note that the class name starts with a capital letter.
Each subsequent word also starts with a capital letter.
Lines 25-33: Define the public functions. Please add comments so that users know how to call
these functions. We add const to these functions so that they can not change values
of any variables.
Lines 35-37: Define the private variable that are used only in the TmUsage class. You can add
underscores behind the variable names to remind the programmers that these variables
are private.
Lines 43-: Show how to use this TmUsage (not fully shown).
2.3 tm_usage.cpp
The implementation of TmUsage is in the tm_usage.cpp.
1. //**************************************************************************
2. // File [ tm_usage.cpp ]
3. // Author [ littleshamoo ]
4. // Synopsis [ functions to calculate CPU time and memory usage ]
5. // Date [ Ver 3.0 started 2010/12/20 ]
6. //**************************************************************************
7. #include // for getrusage()
8. #include // for gettimeofday()
9. #include
10. #include
11. #include
12.
13. #include “tm_usage.h”
14.
15. using namespace std;
16. using namespace CommonNs;
17.
18. TmUsage::TmUsage() {
19. tStart_.uTime = 0; tStart_.sTime = 0; tStart_.rTime = 0;
20. tStart_.vmSize = 0; tStart_.vmPeak = 0; tStart_.vmDiff = 0;
21. pStart_.uTime = 0; pStart_.sTime = 0; pStart_.rTime = 0;
22. pStart_.vmSize = 0; pStart_.vmPeak = 0; pStart_.vmDiff = 0;
23. }
24.
25. TmUsage::~TmUsage() {}
26.
27.
28. bool TmUsage::totalStart() {
29. return checkUsage(tStart_);
30. }
31.
32. bool TmUsage::periodStart() {
33. return checkUsage(pStart_);
34. }
35.
36. bool TmUsage::getTotalUsage(TmStat &st) const {
37. if (!checkUsage(st))
38. return false;
39. st.uTime -= tStart_.uTime;
40. st.sTime -= tStart_.sTime;
41. st.rTime -= tStart_.rTime;
42. st.vmDiff = st.vmSize – tStart_.vmSize;
43. st.vmPeak = st.vmPeak > tStart_.vmPeak ? st.vmPeak : tStart_.vmPeak;
44. return true;
45. }
46.
NTUEE Fall, 2019
4/10
bool TmUsage::getPeriodUsage(TmStat &st) const {
47. if (!checkUsage(st))
48. return false;
49. st.uTime -= pStart_.uTime;
50. st.sTime -= pStart_.sTime;
51. st.rTime -= pStart_.rTime;
52. st.vmDiff = st.vmSize – pStart_.vmSize;
53. st.vmPeak = st.vmPeak > pStart_.vmPeak ? st.vmPeak : pStart_.vmPeak;
54. return true;
55. }
56.
57. //…. (details skipped)
tm_usage.cpp
If you want to know the details, you can read this .cpp file and see how we obtain the run time
and memory of the program. But if you are not interested, you can only read the .h header file.
This is why we want to separate the implementation (cpp) and header (.f) file.
2.3 Compile library
To compile the tm_usage library, please type:
make lib
1. ###########################################################
2. # File [Makefile]
3. # Author [sleepyoala]
4. # Synopsis [an example Makefile to generate tm_usage package]
5. # Date [Ver. 1.0 started 2010/02/23]
6. ###########################################################
7.
8. # CC and CFLAGS are varilables
9. CC = g++
10. CFLAGS = -c -g
11. # -c option ask g++ to compile the source files, but do not link.
12. # -g option is for debugging
13.
14. AR = ar
15. ARFLAGS = rcv
16.
17. lib: libtm_usage.a
18.
19. libtm_usage.a: tm_usage.o
20. $(AR) $(ARFLAGS) libtm_usage.a tm_usage.o
21.
22. tm_usage.o: tm_usage.h tm_usage.cpp
23. $(CC) $(CFLAGS) tm_usage.cpp
24.
25. # clean all the .o and executable files
26. clean:
27. rm -rf *.o *.a
makefile (for tm_usage library)
Line 22-23: compile the object file tm_usage.o from tm_usage.cpp and tm_usage.h
Line 19-20: archive tm_usage.o into a static library file libtm_usage.a. Please note that library
must start with lib and ends with .a.
Line 17: this small library has only one objet file. In a big library, more than one objective
files can be archived into a single lib*.a file like this
ar rcv libx.a file1.o [file2.o …]
In a big project, the libraries are usually pre-compiled by library developers so you usually do
NTUEE Fall, 2019
5/10
not compile the library by yourself.
3. Merge Sort
After the library is ready, please change directory to src.
cd ../src
3.1 mergeSort.h
Let’s look at the coding style of the mergeSort.h header file. It provides an interface of the
MergeSort class. The actual implementation is in another file, mergeSort.cpp. This
separation provides the user a convenient way to quickly know how to use the class without
actually bothering the implementation details.
1. // ******************************************************************
2. // File [mergeSort.h]
3. // Author [Deitel How to program C++, 5ed. Ch 20, Fig. 20.05]
4. // Synopsis [The header file for a MergeSort Class]
5. // Modify [2010/02/21 CM Li]
6. // ********************************************************************
7. #ifndef _MERGESORT_H_
8. #define _MERGESORT_H_
9. #include
10. using std::vector;
11. // MergeSort class definition
12. class MergeSort
13. {
14. public:
15. MergeSort( int ); // constructor initializes vector
16. void sort(); // sort vector using merge sort
17. void displayElements() const; // display vector elements
18. private:
19. int size; // vector size
20. vector< int > data; // vector of ints
21. void sortSubVector( int, int ); // sort subvector
22. void merge( int, int, int, int ); // merge two sorted vectors
23. void displaySubVector( int, int ) const; // display subvector
24. }; // end class SelectionSort
25. #endif
mergeSort.h
Line 1-6: title of this .h file. Provide author and a short synopsis.
Line 7-8: these two lines are compiler preprocessor that prevent a redundant inclusion of
mergeSort.h. Note that _MERGESORT_H_ start and end with underscores ‘_’.
This naming tells us that this word is not a regular variable.
Line 12: Define the class MergeSort. Please note that the class name starts with a capital
letter. Each subsequent word also starts with a capital letter.
Line 14-17: public member functions. Please note that the function names starts with small
letters. Each subsequent word also starts with a capital letter. Do add comments to
describe the function briefly so that users know how to call these functions.
Line 17: displayElements() is a constant so that this function cannot change the values of the
object.
Lines 18-23: define private variables and functions. Variables have no parenthesis ‘()’ but
NTUEE Fall, 2019
6/10
functions do.
3.2 mergeSort.cpp
This file actually implements the MergeSort class. You are encouraged to read the
implementation and compare it with the pseudo code of our text book. Note that the vector is a
container that is defined in STL (standard template library). Using STL helps you to quickly
develop your project without worrying about the data structure implementation. Please refer to
our reference reading for more information about STL.
1. // **************************************************************************
2. // File [mergeSort.cpp]
3. // Author [Deitel How to program C++, 5ed. Ch 20, Fig. 20.06]
4. // Synopsis [The implementation of the MergeSort Class]
5. // Modify [2010/02/21 CM Li]
6. // **************************************************************************
7.
8. #include
9. using std::cout;
10. using std::endl;
11.
12. #include
13. using std::vector;
14.
15. #include // prototypes for functions srand and rand
16. using std::rand;
17. using std::srand;
18.
19. #include // prototype for function time
20. using std::time;
21.
22. #include “mergeSort.h” // class MergeSort definition
23.
24. // constructor fill vector with random integers
25. MergeSort::MergeSort( int vectorSize )
26. {
27. size = ( vectorSize > 0 ? vectorSize : 10 ); // validate vectorSize
28. srand( time( 0 ) ); // seed random number generator using current time
29.
30. // fill vector with random ints in range 10-99
31. for ( int i = 0; i < size; i++ ) 32. data.push_back( 10 + rand() % 90 ); 33. } // end MergeSort constructor 34. 35. // split vector, sort subvectors and merge subvectors into sorted vector 36. void MergeSort::sort() 37. { 38. sortSubVector( 0, size - 1 ); // recursively sort entire vector 39. } // end function sort 40. 41. // recursive function to sort subvectors 42. void MergeSort::sortSubVector( int low, int high ) 43. { 44. // test base case; size of vector equals 1 45. if ( ( high - low ) >= 1 ) // if not base case
46. {
47. int middle1; // calculate middle of vector
48. int middle2; // calculate next element over
49. /*TODO : assign middle1 and middle2
50.
51.
52. */
53. // output split step
54.
55. #ifdef _DEBUG_ON_
56. cout << "split: "; 57. displaySubVector( low, high ); 58. cout << endl << " "; 59. displaySubVector( low, middle1 ); 60. cout << endl << " "; 61. displaySubVector( middle2, high ); 62. cout << endl << endl; 63. #endif 64. 65. /*TODO : recursive function call to split vector in half; sort each half (recursive calls) 66. // first half of vector NTUEE Fall, 2019 7/10 67. // second half of vector 68. */ 69. 70. // merge two sorted vectors after split calls return 71. merge( low, middle1, middle2, high ); 72. } // end if 73. } // end function sortSubVector 74. 75. // merge two sorted subvectors into one sorted subvector 76. void MergeSort::merge( int left, int middle1, int middle2, int right ) 77. { 78. int leftIndex = left; // index into left subvector 79. int rightIndex = middle2; // index into right subvector 80. int combinedIndex = left; // index into temporary working vector 81. vector< int > combined( size ); // working vector
82.
83. // output two subvectors before merging
84. #ifdef _DEBUG_ON_
85. cout << "merge: "; 86. displaySubVector( left, middle1 ); 87. cout << endl << " "; 88. displaySubVector( middle2, right ); 89. cout << endl; 90. #endif 91. 92. /*TODO : merge vectors until reaching end of either 93. while ( leftIndex <= middle1 && rightIndex <= right ) 94. { 95. // place smaller of two current elements into result 96. // and move to next space in vector 97. 98. } // end while 99. 100. if ( leftIndex == middle2 ) // if at end of left vector 101. { 102. // copy in rest of right vector 103. 104. } // end if 105. else // at end of right vector 106. { 107. // copy in rest of left vector 108. 109. } // end else 110. */ 111. 112. /*TODO : copy values back into original vector 113. 114. */ 115. 116. // output merged vector 117. #ifdef _DEBUG_ON_ 118. cout << " "; 119. displaySubVector( left, right ); 120. cout << endl << endl; 121. #endif 122. } // end function merge 123. 124. // display elements in vector 125. void MergeSort::displayElements() const 126. { 127. displaySubVector( 0, size - 1 ); 128. } // end function displayElements 129. 130. // display certain values in vector 131. void MergeSort::displaySubVector( int low, int high ) const 132. { 133. // output spaces for alignment 134. for ( int i = 0; i < low; i++ ) 135. cout << " "; 136. 137. // output elements left in vector 138. for ( int i = low; i <= high; i++ ) 139. cout << " " << data[ i ]; 140. } // end function displaySubVector 141. 142. mergeSort.cpp Lines 55-63: These lines are debug messages. These lines are compiled only if the NTUEE Fall, 2019 8/10 _DEBUG_ON_ is defined when we envoke g++ ; otherwise, these lines are NOT compiled for speed optimization. 4. Main 4.1 global.h This file contains the definition of global variables and constants. The constants are named in all capital letters (such as VECTOR_SIZE) to remind the programmer this is not a regular variable. It is a good habit to define global variables and constants in a head file, instead of the .cpp files, for easy maintenance. 1. // ******************************************************************* 2. // File [global.h] 3. // Author [CM Li] 4. // Synopsis [define global variables] 5. // Modify 6. // ******************************************************************* 7. 8. #ifndef _GLOBAL_H_ 9. #define _GLOBAL_H_ 10. 11. #define VECTOR_SIZE 10 // define the vector size 12. 13. #endif global.h 3.2 main.cpp This file is the main function of the project. Because most jobs are defined in the library and the class, the main file itself is quite simple. 1. //************************************************************************** 2. // File [main.cpp] 3. // Author [Deitel How to program C++, 5ed. Ch 20, Fig. 20.07] 4. // Synopsis [The main program of this demo] 5. // Modify [2010/02/21 CM Li] 6. //************************************************************************** 7. 8. #include
9. using std::cout;
10. using std::endl;
11.
12. #include “global.h” // glabl variables
13. #include “mergeSort.h” // class MergeSort definition
14. #include “tm_usage.h” // the tm_usage library
15.
16. int main()
17. {
18. CommonNs::TmUsage tmusg;
19. CommonNs::TmStat stat;
20. tmusg.periodStart();
21.
22. // create object to perform merge sort
23. MergeSort sortVector( VECTOR_SIZE );
24.
25. cout << "Unsorted vector:" << endl; 26. sortVector.displayElements(); // print unsorted vector 27. cout << endl << endl; 28. 29. sortVector.sort(); // sort vector 30. 31. cout << "Sorted vector:" << endl; 32. sortVector.displayElements(); // print sorted vector 33. cout << endl; 34. 35. tmusg.getPeriodUsage(stat); 36. cout <<"user time:" << stat.uTime / 1000000.0 << "s" << endl; // print period user time in seconds 37. cout <<"system time:" << stat.sTime / 1000000.0 << "s" << endl; // print period systemtime in seconds 38. cout <<"user+system time:" << (stat.uTime + stat.sTime) / 1000000.0 << "s" << endl; 39. return 0; 40. } // end main main.cpp 4.3 Compile the debug version Please type the following commands, make demo_dbg cd ../bin ./demo_dbg Please go to the src directory and read the sample makefile. 1. # CC and CFLAGS are varilables 2. CC=g++ 3. CFLAGS = -c 4. # -c option ask g++ to compile the source files, but do not link. 5. # -g option is for debugging version 6. # -O2 option is for optimized version 7. DBGFLAGS = -g -D_DEBUG_ON_ 8. OPTFLAGS = -O2 9. 10. 11. # DEBUG Version 12. demo_dbg : mergeSort_dbg main_dbg 13. $(CC) $(DBGFLAGS) mergeSort.o main.o -ltm_usage -L../lib -o ../bin/demo_dbg 14. main_dbg : ../lib/tm_usage.h global.h main.cpp 15. $(CC) $(CFLAGS) main.cpp -I../lib 16. mergeSort_dbg : mergeSort.cpp mergeSort.h 17. $(CC) $(CFLAGS) $(DBGFLAGS) mergeSort.h mergeSort.cpp 18. 19. # optimized version 20. demo_opt : mergeSort_opt main_opt 21. $(CC) $(OPTFLAGS) mergeSort.o main.o -ltm_usage -L../lib -o ../bin/demo_opt 22. main_opt : ../lib/tm_usage.h global.h main.cpp 23. $(CC) $(CFLAGS) main.cpp -I../lib 24. mergeSort_opt: mergeSort.cpp mergeSort.h 25. $(CC) $(CFLAGS) $(OPTFLAGS) mergeSort.h mergeSort.cpp 26. 27. # clean all the .o and executable files 28. clean: 29. rm -rf *.o demo makefile Lines 11-17: Compile the debug version when we type ‘make demo_dbg’. This version invokes options ‘-g’ (for DDD debugger) and also ‘-D_DEBUG_ON_’ to enable the printing of arrays in mergeSort.cpp. Lines 19-25: Compile the optimization version when we type ‘make demo_opt’. This version invokes options ‘-O2’ for speed improvement. Also ‘_DEBUG_ON_’ is not defined to disable the printing of arrays in mergeSort.cpp. 4.4 Compile the optimized version Please type the following commands, cd ../src NTUEE Fall, 2019 10/10 make demo_opt cd ../bin ./demo_opt We can summarize the compilation of the whole project in this figure. implementation implementation interface class interface library tm_usage.cpp tm_usage.h main.cpp mergeSort.h mergeSort.cpp mergeSort.o tm_usage.o main.o libtm_usage.a demo other.o (if available) compile archive link compilation flow of this project 5. Exercise (NO need to submit) Please finish all TODO to run mergesort example completely. 6. References about STL: H. Deiltel, How to Program C++, 5ed. Prentice Hall. CPLUSPLUS http://www.cplusplus.com/reference/stl/ C++ STL Tutorial http://www.yolinux.com/TUTORIALS/LinuxTutorialC++STL.html SGI STL Programmer’s Guide http://www.sgi.com/tech/stl/ About Coding Style http://geosoft.no/development/cppstyle.html H. Sutter, C++ coding standards, 101 rules, guidelines and best practice, Addison Wesley.