2.3-6 Insertion Sort with Binary Search

<< Introduction to algorithms >> ( Second Edition )


2.3-6 Insertion Sort with Binary Search

Observe that the while loop of line 5-7 of the Insertion Sort precedure in
Section 2.1 uses a linear search to scan ( backward ) through the sorted subarray
A[ 1 .. j - 1 ]. Can we use a binary search ( see Exercise 2.3-5 ) instead to improve
the overall worst-case running time of insertion sort to O( nlgn ) ?


Solution:

// 声明：本代码旨在实现原文的思想
// copyleft 2004    http://blog.csdn.net/mskia
// email:    [email protected]

#ifndef Insertion_Sort_with_Binary_Search_by_mskia
#define Insertion_Sort_with_Binary_Search_by_mskia

namespace cc {
    template< class T >
    void insertion_sort_with_binary_search( T *first , T *last ) {
        for ( T *i = first + 1; i <= last; ++i ) {
            T *left = first , *right = i - 1;
            while ( left <= right ) {
                T *mid = left + ( ( right - left ) >> 1 );
                if ( *i < *mid ) {
                    if ( *( mid - 1 ) < *i ) {
                        T bac = *i;
                        for ( T *p = i; p > mid; --p ) {
                            *p = *( p - 1 );
                        }
                        *mid = bac;
                        break;
                    } else {
                        right = mid - 1;
                    }
                } else {
                    if ( *( mid + 1 ) > *i ) {
                        ++mid;
                        T bac = *i;
                        for ( T *p = i; p > mid; --p ) {
                            *p = *( p - 1 );
                        }
                        *mid = bac;
                         break;
                    } else {
                        left = mid + 1;
                    }
                }
            }
        }
     
        return;
     }
}

#endif

本文地址：http://com.8s8s.com/it/it27055.htm