D.2. Sample Program for Profiling

A selection sort program is used to demonstrate the profiling process. A selection sort is a general-purpose sort that is a variation of an exchange sort. Basically, this sort passes through a list of elements and finds the index (location) of the smallest (least) element. It exchanges the data at this index with the data stored in the first element of the list. It then repeats the selection process with the remaining list to find the second smallest element, and exchanges the data at this index with the data stored in the second element of the list. The process is repeated until the list is ordered.

There are numerous ways to code a selection sort. Below is a C++ version of this sort.

File : ss.cxx #include using namespace std; // Function prototypes void Get_Data ( int [], int ); void Display ( int [], int ); + void Do_S_Sort ( int [], int ); int Find_Least( const int [], int, int ); int Compare ( const int & , const int & ); void Swap ( int &, int & ); int 10 main( ) { const int max = 10; int List[max]; Get_Data ( List, max ); // Obtain data cout << "Initial list" << endl; + Display ( List, max ); // Show it Do_S_Sort( List, max ); // Sort it cout << "Sorted list" << endl; Display ( List, max ); // Show it again return 0; 20 } // Obtain data to sort from standard input void Get_Data(int a[], int n) { cout << "Please enter " << n << " integers" << endl; + for(int i=0; i < n; ++i) cin >> a[i]; } // Display the current contents of list void 30 Display(int a[], int n) { for(int i=0; i < n; ++i) cout << " " << a[i]; cout << endl; } + // Do the Selection Sort, Display after each pass void Do_S_Sort( int a[], int n ){ int index; for (int i=0; i < n-1; ++i){ 40 index=Find_Least( a, i, n ); if ( i != index ) Swap( a[i], a[index] ); cout << "After pass " << i+1 << " : "; Display( a, n ); + } } // Find the index of the least element in list int Find_Least( const int a[], int start, int stop ){ 50 int Index_of_Least = start; for (int i=start+1; i < stop; ++i ) if ( Compare(a[i], a[Index_of_Least]) ) Index_of_Least = i; return Index_of_Least; + } // Compare two data elements int Compare( const int &a, const int &b ){ return ( a < b ); 60 } // Exchange two data elements void Swap( int &a, int &b ){ int temp; + temp = a; a = b; b = temp; }

As shown, six functions are used to implement the sort

At first glance, using so many functions for such a simple algorithm may seem to be overkill. However, coding some statements (such as the compare in line 52) as a function call will facilitate referencing when generating profile information with gprof .

A good portion of the work done by the selection sort is actually performed by the Find_Least function (see line 49). This function is passed the list and two integer values. The first integer value is the starting point for the search through the remainder of the list. The second value is the size of the list (which in this case reflects its end or stopping point). This function works by storing, in the variable Index_of_Least , the index of the element having the smallest value. Initially, this is the index of the current start of the list (see line 50). It then uses a for loop to pass through the reminder of the list, checking each location against the current smallest value to determine if it has found a lesser value. Each check is carried out by the Compare function. If the value is less, the index (not the value) of the location is stored. When the loop finishes, the index of the element with the smallest value is returned to the calling function. If the returned index is not the index of the current head of list, the two values are exchanged by calling the Swap function. If the current value is already in order, no exchange is needed.