1 Programming Practice Programming Style C 1 Names of functions classes structures variables and constants Use names which are informative concise memorable and pronounceable The broader the scope of a variable the more information should be conveyed by its name use descriptive names for globals short names for locals Functions classes and structures should have names that suggest their role in a program Use consistent naming conventions i Active names for functions e g get time ii Names of pointers that begin or end with p or ptr e g head ptr iii Global variables start with capital letters e g Table iv Constants are written with capitals e g INITIAL SIZE v Private variables start with an underscore e g size Define constant numbers as constants use const keyword 2 Expressions and statements Indent to show structure Use the natural form for expressions Parenthesize to resolve ambiguity Break up complex expressions Use conventional idioms Use cascaded if else statements for multi way decisions Use the language to calculate the size of an object 3 Comments Write short comments that help to read the program Comments should add information that is not evident from the code or that is spread through the source Comments should not report self evident information Comment functions and global data 2 C STL vector class STL merge algorithm STL sorting algorithm timing recursive version of Merge Sort algorithm in pseudo code Standard Template Library of C merge algorithm sort algorithm timing Basic components of STL containers algorithms and iterators Online documentation links http www sgi com tech stl Merge algorithm OutputIterator merge InputIterator1 first1 InputIterator1 last1 InputIterator2 first2 InputIterator2 last2 OutputIterator result Merge combines two sorted ranges first1 last1 and first2 last2 into a single sorted range That is it copies elements from first1 last1 and first2 last2 into result result last1 first1 last2 first2 such that the resulting range is in ascending order The return value is result last1 first1 last2 first2 Example The code is located in the directory stl merging include iostream include vector include algorithm using namespace std int main typedef vector int IntVector typedef IntVector iterator IntVectorIt size t n m cout Enter the size of the first array for merging endl cin n cout endl cout Enter the size of the second array for merging endl cin m cout endl Allocate vectors of sizes n m and n m Define iterators and their initial and terminal values IntVector Vector1 n IntVectorIt start1 end1 it1 start1 Vector1 begin end1 Vector1 end IntVector Vector2 m IntVectorIt start2 end2 it2 start2 Vector2 begin end2 Vector2 end IntVector Vector3 n m IntVectorIt start3 end3 it3 start3 Vector3 begin end3 Vector3 end Enter n consecutive even numbers into vector 1 int i 0 for it1 start1 it1 end1 it1 it1 2 i i Output numbers stored in vector 1 cout The content of vector 1 endl for it1 start1 it1 end1 it1 cout it1 cout endl Enter m consecutive odd numbers into vector 2 i 0 for it2 start2 it2 end2 it2 it2 2 i 1 i Output numbers stored in vector 2 cout The content of vector 2 endl for it2 start2 it2 end2 it2 cout it2 cout endl Perform merging of vectors 1 and 2 into vector 3 merge start1 end1 start2 end2 start3 Print out the result of merging cout The content of vector 3 after merging endl for it3 start3 it3 end3 it3 cout it3 cout endl return 0 Sort Algorithm void sort RandomAccessIterator first RandomAccessIterator last Sort sorts the elements in first last into ascending order meaning that if i and j are any two valid iterators in first last such that i precedes j then j is not less than i Example The code is located inside directory stl sorting include ctime include cstdlib include iostream include vector include algorithm using namespace std int main typedef vector int IntVector typedef IntVector iterator IntVectorIt size t n Seed the random number generator with current time so that the numbers will be different every time we run srand unsigned time NULL cout Enter the size of the random array to be sorted endl cin n cout endl IntVector NumbersVector n IntVectorIt startv endv itv startv NumbersVector begin endv NumbersVector end Enter random numbers into NumbersVector for itv startv itv endv itv itv rand n Start timing sorting procedure clock t start clock sort startv endv Stop timing sorting procedure clock t stop clock Print out elapsed time in miliseconds cout The elapsed time cout 1000 stop start CLOCKS PER SEC endl return 0 Merge Sort algorithm a recursive version with arrays without implementation of merge function void mergesort int a int s int r if r s return int m r s 2 mergesort a s m mergesort a m 1 r merge a s m r Merge operation merge a s m r performs merging of the segments a s m a m 1 r and stores the result in a s r Example s 0 r 11 a 8 7 6 5 2 3 4 11 9 10 12 1 The tree of recursive calls 8 7 6 2 1 The original data 7 6 5 2 After merging on level 3 8 6 2 5 After merging on level 2 7 8 2 3 After merging on level 1 3 5 6 7 After merging on level 0 2 3 4 5 3 4 11 9 10 12 1 3 4 11 9 10 12 1 5 4 9 11 1 10 12 8 1 4 9 10 11 12 6 7 8 9 10 11 12
View Full Document
Unlocking...