Nov 22, 2012

Insertion Sort in C++ using templates

Insertion Sort
An efficient elementary sort method which places each element in it's proper place among the elements which are already placed
  1 #include <iostream>
  2 #include <string.h>
  3 
  4 template <typename T>
  5 class InsertionSort
  6 {
  7     public:
  8         InsertionSort();
  9         ~InsertionSort();
 10 
 11         void sort(T arr[], int size);
 12     private:
 13         void compareExchange(T arr[], int l, int r);
 14         bool greater(T left, T right);
 15 };
 16 
 17 //Constructor
 18 template <typename T>
 19 InsertionSort<T>::InsertionSort(){}
 20 
 21 //Destructor
 22 template <typename T>
 23 InsertionSort<T>::~InsertionSort(){}
 24 
 25 template <typename T>
 26 void InsertionSort<T>::sort(T arr[], int size)
 27 {
 28     for(int i = 1; i < size; ++i)
 29     {
 30         for(int j = i; j > 0; --j)
 31         {
 32             compareExchange(arr, j-1, j);
 33         }
 34     }
 35 }
 36 
 37 template <typename T>
 38 void InsertionSort<T>::compareExchange(T arr[], int l, int r)
 39 {
 40     if(greater(arr[l], arr[r]))
 41     {
 42         T temp = arr[l];
 43         arr[l] = arr[r];
 44         arr[r] = temp;
 45     }
 46 }
 47 
 48 template <typename T>
 49 bool InsertionSort<T>::greater(T left, T right)
 50 {
 51     return left > right;
 52 }
 53 
 54 template <>
 55 bool InsertionSort<const char*>::greater(const char *left, const char *right)
 56 {
 57     return strcmp(left, right) > 0;
 58 }
 59 
 60 template <typename T>
 61 void print(T arr[], int size)
 62 {
 63     for(int i = 0; i < size; ++i)
 64         std::cout << arr[i] << " ";
 65     std::cout << std::endl;
 66 }
 67 
 68 template <>
 69 void print(std::string arr[], int size)
 70 {
 71     for(int i = 0; i < size; ++i)
 72         std::cout << arr[i].c_str() << " ";
 73     std::cout << std::endl;
 74 }
 75 
 76 template <>
 77 void print(const char *ptrArray, int size)
 78 {
 79     for(int i = 0; i < size; ++i)
 80         std::cout << ptrArray[i] << " ";
 81     std::cout << std::endl;
 82 }
 83 
 84 int main()
 85 {
 86     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
 87     InsertionSort<int> isInt;
 88     isInt.sort(arr, 9);
 89     print(arr, 9);
 90 
 91     std::string strArr[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin" };
 92     InsertionSort<std::string> isString;
 93     isString.sort(strArr, 8);
 94     print(strArr, 8);
 95 
 96     const char* ptrArray[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin", "george"};
 97     InsertionSort<const char*> isPtr;
 98     isPtr.sort(ptrArray, 9);
 99     print(ptrArray, 9);
100 
101     return 0;
102 }

No comments :

Post a Comment