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

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

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

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

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

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

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 ] );
	}
}