There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.

#define _SECURE_SCL 0
#define _SECURE_SCL_THROWS 0

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

#include <boost/timer.hpp>
using boost::timer;

template< typename Func, typename Cont >
double sort_timing( Cont c, Func f )
{
    timer t1;
    f( c.begin(), c.end() );
    return t1.elapsed();
}

#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/mersenne_twister.hpp>

template< typename Dist, typename Cont, typename Arg >
Cont generate_random( typename Cont::size_type size, Arg arg1, Arg arg2 )
{
    static boost::mt11213b gen( std::time(0) );
    boost::variate_generator< boost::mt11213b&, Dist > rand_gen( gen, Dist( arg1, arg2 ) );

    Cont c;
    generate_n( back_inserter( c ), size, rand_gen );
    return c;
}

template< typename Cont >
Cont& make_almost_sorted( Cont& cont, double swap_percent )
{
    sort( cont.begin(), cont.end() );
    using namespace boost;
    static mt11213b gen( std::time(0) );
    variate_generator< mt11213b&, uniform_int<> > rand_gen( gen, uniform_int<>( 0, cont.size() - 1 ) );
    for ( int i = 0, N = swap_percent * cont.size() / 2; i < N; ++i )
        swap( cont[ rand_gen() ], cont[ rand_gen() ] );
    return cont;
}

template<class Iterator>
void insertion_sort( Iterator First, Iterator Last )
{
    for( Iterator i = First; i < Last; ++i )
        for( Iterator j = i; First < j && *j < *(j - 1); --j )
            std::iter_swap( (j - 1), j );
}

template<class Iterator>
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *i > *(i + 1) )
                std::iter_swap( (i + 1), i );
}

template<class Iterator>
void selection_sort( Iterator First, Iterator Last )
{
    for( ; First < Last; ++First )
    {
        Iterator min = First;
        for( Iterator i = First; i < Last; ++i )
            if ( *i < *min )
                min = i;
        std::iter_swap( First, min );
    }
}

template<class Iterator>
void heap_sort( Iterator First, Iterator Last )
{
    partial_sort( First, Last, Last );
}

int main()
{
    typedef std::vector< int > vt;
    typedef void (*SORT_FUNC)( vt::iterator, vt::iterator );
    struct Func { SORT_FUNC func; const char* name; };
    Func sort_functions[] =
    {
        { &sort< vt::iterator >, "std::sort" }
        , { &stable_sort< vt::iterator >, "merge_sort" }
        , { &heap_sort< vt::iterator >, "heap_sort" }
        , { &insertion_sort< vt::iterator >, "insertion_sort" }
        , { &bubble_sort< vt::iterator >, "bubble_sort" }
        , { &selection_sort< vt::iterator >, "selection_sort" }
    };

    const double pc_min = 0.001, pc_max = 0.1, pc_step = 10;
    for( double i = pc_min; i <= pc_max; i *= pc_step )
    {
        cout << "Sort an almost sorted vector with " << 100*i << "% exchanged elements\n";
        cout << setw(8) << left << "size";
        for ( int fn = 0; fn < sizeof(sort_functions)/sizeof(Func); ++fn )
            std::cout << setw(16) << left << sort_functions[fn].name;
        cout << endl;

        const int min = 16000, max = 128000, step = 2;
        for( vt::size_type n = min; n <= max; n *= step )
        {
            cout << setw(8) << left << n;
            vt cont = generate_random< boost::uniform_int<>, vt, int >( n, 0, INT_MAX );
            make_almost_sorted( cont, i );
            for ( int fn = 0; fn < sizeof(sort_functions)/sizeof(Func); ++fn )
                std::cout << setw(16) << left << sort_timing( cont, sort_functions[fn].func );
            cout << endl;
        }      
        cout << endl;
    }
}

Sort an almost sorted vector with 0.1% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
16000   0               0               0.015           0               0.172           0.141
32000   0               0               0               0               0.703           0.61
64000   0               0.016           0               0.016           2.75            2.453
128000  0               0.016           0.015           0.016           11.125          9.797

Sort an almost sorted vector with 1% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
16000   0               0               0               0               0.188           0.156
32000   0               0               0               0.015           0.735           0.64
64000   0               0               0.016           0.031           3               2.5
128000  0               0.016           0.015           0.157           11.765          9.813

Sort an almost sorted vector with 10% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
16000   0               0               0               0.032           0.265           0.157
32000   0               0               0               0.094           1.062           0.609
64000   0.016           0               0               0.344           4.25            2.438
128000  0.015           0.016           0.016           1.422           17.015          9.813

_>>template<class Iterator>
_>>void bubble_sort( Iterator First, Iterator Last )
_>>{
_>>    while( First < --Last )
_>>        for( Iterator i = First; i < Last; ++i )
_>>            if ( *i > *(i + 1) )
_>>                std::iter_swap( (i + 1), i );
_>>}
_>>

template< typename Iterator >
void bubble_sort1( Iterator First, Iterator Last )
{
    bool test = true;
    for( --Last; First < Last && test; --Last )
    {
        test = false;
        for( Iterator j = First; j < Last; ++j )
            if( *(j + 1) < *j )
                std::iter_swap( j, j + 1 ), test = true;
    }
}

Sort an almost sorted vector with 0.1% exchanged elements
size        std::sort       insertion_sort  bubble_sort     bubble_sort1
4000        0               0               0.031           0.015
8000        0               0               0.079           0.046
16000       0               0               0.172           0.157
32000       0               0               0.687           0.594
64000       0               0.016           2.719           2.625

Sort an almost sorted vector with 1% exchanged elements
size        std::sort       insertion_sort  bubble_sort     bubble_sort1
4000        0               0               0               0.016
8000        0               0               0.047           0.047
16000       0               0.015           0.172           0.188
32000       0               0.015           0.719           0.719
64000       0.016           0.031           2.875           2.844

Sort an almost sorted vector with 10% exchanged elements
size        std::sort       insertion_sort  bubble_sort     bubble_sort1
4000        0               0.015           0.016           0.015
8000        0               0               0.063           0.062
16000       0               0.016           0.265           0.25
32000       0               0.078           1.047           1.031
64000       0               0.359           4.141           4.094

Sort an almost sorted vector with 100% exchanged elements
size        std::sort       insertion_sort  bubble_sort     bubble_sort1
4000        0               0.015           0.031           0.047
8000        0               0.032           0.156           0.14
16000       0               0.125           0.594           0.594
32000       0               0.5             2.406           2.422
64000       0               2.031           9.828           9.75

template< typename T >
int int_compare( const void* left, const void* right )
{
    return *static_cast<const T*>(left) - *static_cast<const T*>(right);
}

template<class Iterator>
void quick_sort( Iterator First, Iterator Last )
{
    typedef typename iterator_traits< Iterator >::value_type value_t;
    qsort( &*First, distance( First, Last ), sizeof( value_t ), &int_compare< value_t > );
}

Sort an almost sorted vector with 0.1% exchanged elements
size        std::sort       insertion_sort  bubble_sort     quick_sort
32000       0               0               0.719           0.015
64000       0               0               2.719           0
128000      0.015           0.016           10.875          0.016

Sort an almost sorted vector with 1% exchanged elements
size        std::sort       insertion_sort  bubble_sort     quick_sort
32000       0               0.016           0.719           0
64000       0               0.047           2.906           0.016
128000      0               0.157           11.562          0.016

Sort an almost sorted vector with 10% exchanged elements
size        std::sort       insertion_sort  bubble_sort     quick_sort
32000       0.015           0.078           1.063           0
64000       0               0.359           4.187           0.016
128000      0               1.422           16.656          0.016

Sort an almost sorted vector with 100% exchanged elements
size        std::sort       insertion_sort  bubble_sort     quick_sort
32000       0               0.515           2.391           0
64000       0               2.047           9.641           0.015
128000      0.016           8.203           38.437          0.032

_>Sort an almost sorted vector with 0.1% exchanged elements
_>size        std::sort       insertion_sort  bubble_sort     bubble_sort1
_>4000        0               0               0.031           0.015
_>8000        0               0               0.079           0.046
_>16000       0               0               0.172           0.157
_>32000       0               0               0.687           0.594
_>64000       0               0.016           2.719           2.625

_>Sort an almost sorted vector with 1% exchanged elements
_>size        std::sort       insertion_sort  bubble_sort     bubble_sort1
_>4000        0               0               0               0.016
_>8000        0               0               0.047           0.047
_>16000       0               0.015           0.172           0.188
_>32000       0               0.015           0.719           0.719
_>64000       0.016           0.031           2.875           2.844

_>Sort an almost sorted vector with 10% exchanged elements
_>size        std::sort       insertion_sort  bubble_sort     bubble_sort1
_>4000        0               0.015           0.016           0.015
_>8000        0               0               0.063           0.062
_>16000       0               0.016           0.265           0.25
_>32000       0               0.078           1.047           1.031
_>64000       0               0.359           4.141           4.094

_>Sort an almost sorted vector with 100% exchanged elements
_>size        std::sort       insertion_sort  bubble_sort     bubble_sort1
_>4000        0               0.015           0.031           0.047
_>8000        0               0.032           0.156           0.14
_>16000       0               0.125           0.594           0.594
_>32000       0               0.5             2.406           2.422
_>64000       0               2.031           9.828           9.75
_>

Sort an almost sorted vector with 0.1% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
4       0.046875        0.460938        0.171875        0.015625        0.015625        0.0546875
8       0.09375         0.507812        0.335938        0.03125         0.03125         0.21875
16      0.164062        1.00781         0.71875         0.0546875       0.046875        0.570312
32      0.382812        1.46875         1.67969         0.09375         0.109375        1.67188
64      0.945312        2.71094         4.08594         0.179688        0.203125        5.3125

Sort an almost sorted vector with 1% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
4       0.101562        0.484375        0.1875          0.0625          0.0546875       0.101562
8       0.125           0.53125         0.351562        0.0703125       0.0625          0.226562
16      0.179688        1.01562         0.742188        0.0859375       0.0859375       0.578125
32      0.375           1.48438         1.70312         0.109375        0.109375        1.67188
64      0.945312        2.71094         4.08594         0.179688        0.203125        5.3125

Sort an almost sorted vector with 10% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
4       0.101562        0.484375        0.1875          0.0546875       0.0546875       0.101562
8       0.125           0.53125         0.351562        0.0703125       0.0625          0.226562
16      0.1875          1.01562         0.742188        0.0859375       0.0859375       0.578125
32      0.382812        1.46094         1.71094         0.117188        0.226562        1.6875
64      1.46094         3.4375          4.39844         0.851562        7.75781         5.4375

V>Sort an almost sorted vector with 0.1% exchanged elements
V>size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
V>4       0.046875        0.460938        0.171875        0.015625        0.015625        0.0546875
V>

V>size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
V>8       0.125           0.53125         0.351562        0.0703125       0.0625          0.226562
V>

Sort an almost sorted vector with 10% exchanged elements
size        std::sort       insertion_sort  bubble_sort     bubble_sort1    quick_sort      
4           0.038           0.014           0.019           0.013           0.059           
8           0.044           0.023           0.149           0.023           0.267           
16          0.083           0.041           0.409           0.041           0.585           
32          0.220           0.182           1.424           0.784           1.370           

Sort random vector
size        std::sort       insertion_sort  bubble_sort     bubble_sort1    quick_sort      
4           0.058           0.048           0.049           0.051           0.112           
8           0.148           0.146           0.236           0.252           0.392           
16          0.369           0.402           0.852           0.875           1.102           
32          0.888           1.169           2.893           2.986           2.713

V>>8 наносекунд — это сферический конь в вакууме. попробуйте запустить этот тест на 20MHz risc-процессоре и посчитайте разницу во времени

Sort an almost sorted vector with 10% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
8       0.226562        1.03906         0.6875          0.09375         0.078125        0.4375
16      0.351562        2.00781         1.45312         0.117188        0.117188        1.14062

Sort an almost sorted vector with 25% exchanged elements
size    std::sort       merge_sort      heap_sort       insertion_sort  bubble_sort     selection_sort
4       0.171875        0.945312        0.34375         0.078125        0.0703125       0.140625
8       0.226562        1.03906         0.6875          0.0859375       0.078125        0.4375

_DA>>Не в тему, но.. всегда интересовало, почему в качестве самой простой (ну или первой в книге) сортировки приводят bubble sort. IMHO, не знающему алгоритмов сортировки школьнику придет в голову скорее алгоритм: находим минимум, меняем с первым, и т.д. Обычный selection sort, простой как топор, еще и эффективнее, чем пузырек.

Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.[1]

The Jargon file, which famously calls bogosort "the archetypical perversely awful algorithm", also calls bubble sort "the generic bad algorithm".[2] Donald Knuth, in his famous The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he discusses therein.

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort.

_FR>>Не раз видел, когда при необходимости всего-то найти пересечение двух множеств (заданных массивом\IList\IEnumerable, не важно) делался foreach по одному списку, а внутри него — по другому И на все пожелания сделать правильно отвечалось, что "нечего преждевременной оптимизацией заниматься", тогда как дело попросту в незнании более эффективных алгоритмов (что, к счастью, поправимо) и нежелании их узнать (с чем уже ничего не поделать)

КЛ>а правильно это как? что может быть быстрее на неотсортированной коллекции

  using System;
  using System.Collections.Generic;
  using System.Linq;

  internal static class Program
  {
    private static void Main() {
      var first = Enumerable.Range(1, 10);
      var second = Enumerable.Range(5, 10);
      var intersect = first.Intersect(second, null);
      foreach(var item in intersect) {
        Console.WriteLine(item);
      }//for
    }

    private static IEnumerable<T> Intersect<T>(this IEnumerable<T> left, IEnumerable<T> right, IEqualityComparer<T> comparer) {
      var set = new HashSet<T>(comparer ?? EqualityComparer<T>.Default);
      foreach(var item in left) {
        set.Add(item);
      }//for
      foreach(var item in right) {
        if(set.Contains(item)) {
          yield return item;
        }//if
      }//for
    }
  }

int
array_max(int *array, size_t size) {
  int r;
  size_t i;

  assert(array != NULL);
  assert(size != 0);

  r = array[0];
  for (i = 1; i < size; i++) {
    if (array[i] > r) {
      r = array[i];
    }
  }
  return r;
}

template< typename ForwardIterator >
ForwardIterator max( ForwardIterator first, ForwardIterator last )
{
    if ( first == last )
        return first;

    ForwardIterator result = first;
    while( ++first != last )
        if ( *result < *first )
            result = first;
    return result;
}

    static int find(int[] a) throws Exception
    {
        if (a == null)
            throw new NullPointerException("Array is empty");
        
        if (a.length == 0)
            throw new IndexOutOfBoundsException("length is 0");
        
        if (a.length == 1)
            return a[0];
        
        int max = a[0];
        for (int i = 1; i < a.length; i++)
        {
            if (a[i] > max)
                max = a[i];
        }
        return max;
    }

{
   a = new int[0];
   max = find(a)
}

std::cout << "max element: " << *max_element(a.begin(), a.end()) << std::endl;

map< A, B > m;
try {
  B b = m.find( a );
  // do something if a found
}
catch( SomeException const& e ) {
  // do something if a not found
}

template< typename Iterator >
... some_algorithm( Iterator first, Iterator last, ... )
{
    if ( first == last )
        throw ...;
    ...
}

_>template< typename Iterator >
_>... some_algorithm( Iterator first, Iterator last, ... )
_>{
_>    if ( first == last )
_>        throw ...;
_>    ...
_>}
_>

max_element (where: COLLECTION[T]): T
  requires
    non_empty_collection: 0 /= where.size
  ...

template< class ITERATOR >
typename ITERATOR::value_type
max_element( ITERATOR begin, ITERATOR end ) { ... }

template< class ITERATOR >
ITERATOR
max_element_ref( ITERATOR begin, ITERATOR end ) { ... }

E>>Вроде как автор max_element -- он же тут чистенький, весь такой в белом, у него код корректный. А то, что он создает своим корректным кодом лишние заботы пользователю -- так это проблема пользователя

// Бросает исключение в случае пустой последовательности.
T max_element( FI begin, FI end );
// Не бросает исключений, но вызывает abort.
T max_element( FI begin, FI end, nothrow );
// Возвращает ссылку на максимальный элемент или end.
// Не бросает исключений.
FI max_element_reference( FI begin, FI end );

// Бросают исключение.
template< class T >
T & max_element( T * begin, T * end ) { ... }
template< class T >
const T & max_element( const T * begin, const T * end ) { ... }
template< class FI >
typename FI::reference_type max_element( FI begin, FI end ) { ... }
... аналогично остальные функции ...

std::vector< int > v;
... какие-то действия, которые, по мнению разработчика, заполняют v...
std::vector< int >::iterator m = std::max_element( v.begin(), v.end() );
if( m == v.end() )
  // Что за оно вааще?!!

// Бросают исключение.
template< class T >
T & max_element( T * begin, T * end ) { ... }
template< class T >
const T & max_element( const T * begin, const T * end ) { ... }
template< class FI >
typename FI::reference_type max_element( FI begin, FI end ) { ... }
... аналогично остальные функции ...

template< typename ForwardIterator >
typename std::iterator_traits< ForwardIterator >::reference max_element( ForwardIterator first, ForwardIterator last )
{
    ForwardIterator result = first;
    if ( first != last )
        while( ++first != last )
            if ( *result < *first )
                result = first;
    return *result;
}

template< typename T > T& max_element( T* first, T* last );
template< typename I > typename I::reference max_element( I first, I last );

template< typename I > typename std::iterator_traits<I>::reference max_element( I first, I last );

template< typename ForwardIterator >
typename std::iterator_traits< ForwardIterator >::reference max_element_value( ForwardIterator first, ForwardIterator last )
{
    if ( first == last )
        throw std::runtime_error( "empty range" );
    return *std::max_element( first, last );
}

template< typename ForwardIterator >
void selection_sort( ForwardIterator first, ForwardIterator last )
{
    while( first < --last )
        std::iter_swap( last, std::max_element( first, last + 1 ) );
}

void f(const std::nothrow_t&);
//...
f(std::nothrow);

ЮЖ>>void f(const std::nothrow_t&);
ЮЖ>>//...
ЮЖ>>f(std::nothrow);
ЮЖ>>

// Бросает исключение в случае пустой последовательности.
T max_element( FI begin, FI end );
// Не бросает исключений, но вызывает abort.
T max_element( FI begin, FI end, nothrow );