Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * insertion sort
- *
- * insertion sort using template classes
- *
- * Author: Mark Ruff
- */
- template <class T>
- void insertion_sort( T* array, int size ) {
- // start at the SECOND element, if we're past the end of the array finish
- for ( int i = 1 ; i < size ; i++ ) {
- T current_value = array[i];
- // compare to all elements prior to the currently selected, starting at the
- // largest (furthest along the array). These will be sorted
- for ( int j = i ; j >= 0 ; j-- ) {
- // if we make it to the start, current must be the smallest element
- if ( j == 0 ) {
- array[j] = current_value;
- }
- // if the current element is smaller than the sorted element, shift
- // the sorted element to the right
- else if ( current_value < array[j - 1] ) {
- array[j] = array [j - 1];
- // otherwise the current element must be bigger, so slot it in here
- // (any bigger elements have been moved to the right already)
- }
- else {
- array[j] = current_value;
- break;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement