Thursday, April 10, 2014

C++ STL Algorithms - Sort- Part-1

Sorting is one of the most widely used algorithmic primitive in programming. 

C++ Standard Template Library (STL) provides an efficient implementation of the sort algorithm. It is always better to use this algorithm instead of writing our own implementation because of the following benefits.
  • It's performance would surely be better than your own implementation. It's implementation conforms to the C++ standard bench marks and tested by a lot of people. The library version takes advantage of the combination of multiple sorting algorithms to achieve the maximum performance.
  • Writing our own version is error prone and bugs can easily be overlooked.
Here is a simple program which demonstrates the use of library sort() routine to sort an array as well as a vector. 

The sort() method at the minimum requires two parameters; the start of the list and the end of the list. Note that the end should always point to one element beyond the last element. It sorts the element ranging between [begin, end) i.e starting from the first element till the end excluding the last.

For arrays, we know that the array name indicates the address of the first element. If we add the size of the array to the starting address, we get the address of next to last element.

For vectors, there are built-in methods begin() and end() to indicate the starting and ending elements.


    #include <iostream>
    #include <algorithm> //included for using sort
    #include <vector> 
    #include <string>
    using namespace std;
    
    int main()
    {
     int arr[5] = {9, 6, 36, 24, 42};
     int arrSize = sizeof(arr)/sizeof(arr[0]);
    
     sort(arr, arr+arrSize); //sorts the given numbers in ascending order
    
     for( int i=0; i < arrSize; i++ )
     {
      cout << arr[i] << " ";
     }
     cout << endl;
    
     vector<string> names;
     names.push_back("Himalayas");
     names.push_back("Alphs");
     names.push_back("Vindhya");
     names.push_back("Aravali");
    
     sort( names.begin(), names.end());//sorts the names in alphabetical order
    
     for( int i = 0; i < names.size(); i++ )
     {
      cout << names[i] << " ";
     }
    
     cout << endl;
     
     return 0;
    
    }