Простейшие алгоритмы сортировки

Хотя программирование в чистом виде и не является основной целью нашего портала, все же для реализации мыслей о будущем, особенно технических, неплохо бы владеть и программированием. Поэтому по мере сил и времени, постараюсь публиковать тут описание различных алгоритмов и методик разработки программного обеспечения. Мне очень нравится язык С++, поэтому примеры кода я буду публиковать именно на этом языке. Для тех кто умеет программировать, язык как таковой становится не таким важным понятием, поэтому надеюсь, что примеры кода будут понятны.

Сегодня начну с простых вещей. Во-первых, на простых вещах строятся более сложные понятия и без основ нельзя построить что-то большое. С другой стороны я хочу попробовать как пойдет и будет ли смысл писать дальше. Поэтому темой сегодняшней статьи будут простейшие алгоритмы сортировки:

• Сортировка вставками
• Сортировка слиянием
• Пузырьковая сортировка

Стоит сразу же упомянуть тот факт, что простейшие алгоритмы сортировки занимают квадратичное время, а значит крайне неэффективны на больших объемах данных. Однако, они просты в изучении и быстры в реализации.

Для генерации массива будем использовать следующий код:

std::vector< int > arr;
const int N = 10;
for ( int i = 0; i < N; ++i )
    arr.push_back( rand( ) % 10 );

для вывода результатов на экран

for ( int i = 0; i < N; ++i )
    std::cout << arr[ i ] << " ";
std::cout << std::endl;

Сортировка вставками

С сортировкой вставками вы наверняка встречались даже в реальном мире, например, если хоть раз играли в карты, например, в дурака. Когда вы берете со стола карты, предназначенные вам - они находятся в случайном порядке, но вы можете выстроить их по старшинству, вытягивая карту которая находится не на своем месте и вставляя ее туда, где она должна бы находится.

Вот сам алгоритм

// insertion sort
for ( int j = 1; j < arr.size( ); ++j )
{
    int key = arr[ j ];
    int i = j - 1;
    while ( i >= 0 && arr[ i ] > key )
    {
        arr[ i + 1 ] = arr[ i ];
        i--;
    }
    arr[ i + 1 ] = key;
}

На каждом этапе мы выбираем следующий элемент и ставим его на положенное ему место - точь в точь как с картами. Следует отметить, что в приведенном алгоритме присутствует два вложенных цикла, что говорит о квадратичности алгоритма. Кроме того, алгоритм не гарантирует стабильность сортировки, т.е. элементы с равными ключами могут быть переставлены.

Сортировка слияниями

Следующий вариант простейщей сортировки - сортировка слияниями. В этой сортировке мы используем алгоритм “разделяй и властвуй”. Мы делим массив на две одинаковые части, сортируем их отдельно - а потом сливаем вместе. Подобные алгоритм повторяется для каждой из частей. Дробление происходит до тех пор - пока не останется один элемент, понятно что один элемент отсортирован сам собой.

Алгоритм состоит из двух частей: функции слияния и функции сортировки. Функция слияние обеспечивает слияние двух частей массива (предполагается что они уже отсортированы). Техника следующая: мы делаем два массива, затем идем по указанному промежутку и выбираем из двух массивов минимальный элемент - его и вставляем. В качестве признака конца частей используем очень большое число.

Функция слияния:

void merge( std::vector< int >& arr, int p, int q, int r )
{
    int n1 = q - p;
    int n2 = r - q;
    
    std::vector< int > left;
    left.resize( n1 + 1 );
    
    std::vector< int > right;
    right.resize( n2 + 1 );
    
    for ( int i = 0; i < n1; ++i )
        left[ i ] = arr[ p + i ];
    for ( int j = 0; j < n2; ++j )
        right[ j ] = arr[ q + j ];
    
    left[ n1 ] = 0x7fffffff; // +singularity
    right[ n2 ] = 0x7fffffff; // +singularity
    
    int i = 0, j = 0;
    for ( int k = p; k < r; ++k )
    {
        if ( left[ i ] <= right[ j ] )
        {
            arr[ k ] = left[ i ];
            i++;
        }
        else
        {
            arr[ k ] = right[ j ];
            j++;
        }
    }
}

Функция сортировки слиянием:

void merge_sort( std::vector< int >& arr, int p, int r )
{
    if ( p < ( r - 1 ) )
    {
        int q = ( p + r ) / 2;
        merge_sort( arr, p, q );
        merge_sort( arr, q, r );
        merge( arr, p, q, r );
    }
}

Ну и соответственно вызов нашей замечательной сортировки:

merge_sort( arr, 0,  arr.size( ) );

Пузырьковая сортировка

Последней и самой простой в реализации является пузырьковая сортировка. Суть ее заключается в том, что на каждой итерации нужный элемент как бы “выплывает” на свое нужное место. Пузырьковая сортировка выполняется путем переставления соседних элементов, которые стоят в неправильном порядке. Простота ее реализации снискала ей огромную популярность в рядах начинающих программистов. Но, несомненно, следует помнить, что это очень неэффективная сортировка.

Вот ее код:

for ( int i = 0; i < arr.size( ) - 1; ++i )
{
    for ( int j = i; j < arr.size( ); ++j )
    {
        if ( arr[ i ] > arr[ j ] )
            std::swap( arr[ i ], arr[ j ] );
    }
}