Advertisement
markruff

Insertion Sort (template class)

Jan 4th, 2016
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. /*
  2.  * insertion sort
  3.  *
  4.  * insertion sort using template classes
  5.  *
  6.  * Author: Mark Ruff
  7.  */
  8.  
  9. template <class T>
  10. void insertion_sort( T* array, int size ) {
  11.  
  12.   // start at the SECOND element, if we're past the end of the array finish
  13.   for ( int i = 1 ; i < size ; i++ ) {
  14.     T current_value = array[i];
  15.     // compare to all elements prior to the currently selected, starting at the
  16.     // largest (furthest along the array). These will be sorted
  17.     for ( int j = i ; j >= 0  ; j-- ) {
  18.        // if we make it to the start, current must be the smallest element
  19.        if ( j == 0 ) {
  20.          array[j] = current_value;
  21.        }
  22.        // if the current element is smaller than the sorted element, shift
  23.        // the sorted element to the right
  24.        else if ( current_value < array[j - 1] ) {
  25.          array[j] = array [j - 1];
  26.        // otherwise the current element must be bigger, so slot it in here
  27.        // (any bigger elements have been  moved to the right already)
  28.        }
  29.        else {
  30.          array[j] = current_value;
  31.          break;
  32.        }
  33.     }
  34.   }
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement