Методы вставки и выбора оказываются в среднем приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена («пузырька).

Исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.

Сортировка обменом («пузырьковая» сортировка)

Это один из простейших методов сортировки. Метод хорошо работает на простых структурах данных или данных, в некоторой степени отсортированных. В алгоритме выполняются последовательные перемещения соседних элементов. Во время каждого перемещения элементы сравниваются и меняются местами, если они расположены не в желаемом порядке. В результате после каждого перемещения максимальный элемент будет стоять на последней позиции («всплыл» первый «пузырек»). Отсортированные элементы не нуждаются в сравнении при последующих перемещениях, поэтому второй проход перемещений выполняется до предпоследнего элемента и т.д. Всего для массива размерности n требуется (n-1) проход.

1-й проход	5	11	3	7	1	4	2	9
		3	11
			7	11
				1	11
					4	11
						2	11
							9	11

2-й проход	5	3	7	1	4	2	9	11
	3	5	1	7
				4	7
					2	7
3-й проход	3	5	1	4	2	7	9	11
		1	5
			4	5
				2	5
4-й проход	3	1	4	2	5	7	9	11
Программирование – лекция 12 (лекции Стрикелевой Л.В.)								21

	1	3	2		4
5-й проход	1	3	2	4		5	7	9	11
		2	3
6-й проход	1	2	3	4		5	7	9	11
7-й проход	1	2	3	4		5	7	9	11

Алгоритм: последовательно сравниваем каждую пару соседних чисел и в зависимости от результата сравнения их переставляем или оставляем на месте. За один просмотр наибольшее число переместится в конец, но результата не достигнем, поэтому повторяем процесс. Алгоритм реализуется с помощью двух вложенных циклов.

В первом, плохом, варианте и внутренний, и внешний циклы можно повторить (n -1) раз, где n – размерность массива.

for (int i=1; i<n; i++) for (int j=0; j<n-1; j++)

if (x[j] > x[j+1]) {r=x[j]; x[j]=x[j+1]; x[j+1]=r;

}

Улучшаем внутренний цикл.

Так как наибольшее число находится уже в конце, то цикл можно завершать ранее: на каждом последующем шаге количество сравнений уменьшать на 1:

for (int j=0; j<n- i; j++) …..

Тогда имеем:

int main()
{	//прототип функции сортировки
void bsort(int*, int);

const int N = 10;

static int arr[N] = { 37, 84, 62, 91, 11, 65, 57, 28, 19, 49 };

bsort (arr, N);	//вызов функции сортировки
for(int j=0; j<N; j++)	//вывод массива
cout << arr[j] << " ";
cout << endl;
_getch();
return 0;
}
//--------------------------------------------------------------	//функция сортировки «пузырек»
void bsort (int* x, int n)
{int i, j;
Программирование – лекция 12 (лекции Стрикелевой Л.В.)	22

for ( i=1; i<n; i++) {for ( j=0; j<n-i; j++)

if (x[j] > x[j+1]) {int r=x[j];

x[j]=x[j+1];

x[j+1]=r;

}

for(j=0; j<n; j++) //для отладки вывод массива после одного прохода cout << x[j] << " ";

cout << endl;

}

}

37 62 84 11 65 57 28 19 49 91

37 62 11 65 57 28 19 49 84 91

37 11 62 57 28 19 49 65 84 91

11 37 57 28 19 49 62 65 84 91

11 37 28 19 49 57 62 65 84 91

11 28 19 37 49 57 62 65 84 91

11 19 28 37 49 57 62 65 84 91

11 19 28 37 49 57 62 65 84 91

11 19 28 37 49 57 62 65 84 91

Оптимизация внешнего цикла при сортировке:

Не для всех массивов необходимо (n-i) просмотров.

«Хороший» массив может быть отсортирован за меньшее количество просмотров.

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

Это реализуется с помощью переменной flag. Сначала она равна 0. Если перестановка была, то переменная flag изменит свое значение с 0 на 1. Тогда имеем

int main()

{

void bsort(int*, int); //prototype const int N = 10;

static int arr[N] = { 37, 84, 62, 91, 11, 65, 57, 28, 19, 49 };

bsort (arr, N);	//вызов функции сортировки
for(int j=0; j<N; j++) //вывод отсортированного массива
cout << arr[j] << " ";
cout << endl;
_getch();
return 0;
}
//--------------------------------------------------------------		//функция сортировки «пузырек»
void bsort (int* x, int n)
{ int flag = 1, k=n;
while (flag)
{ k--;
Программирование – лекция 12 (лекции Стрикелевой Л.В.)		23

flag=0;

for (int j=0; j<k; j++) if (x[j] > x[j+1])

{int r=x[j]; x[j]=x[j+1]; x[j+1]=r; flag=1;

} //end if }//end while

}//end bsort

Сортировка одномерного массива по некоторому признаку

Рассмотрим сортировку одномерного целочисленного массива по возрастанию последней цифры значения элемента.

1.Вначале строим массив параметров (массив D[n] последних цифр).

2.Сравниваем не сами элементы, а эти параметры. И если они равны, только тогда сравниваем сами числа.

3.Переставляем не только сами числа, но и параметры, чтобы они соответствовали тем же числам, что и до сортировки.

#include < stdlib.h> int main()

{

const int n = 10;

int x[n], D[n], i, j;

cout	<< "x[i]" << endl;				//заполнение массива х
for (i = 0; i<n; i++)		x[i]= rand();		";
for (i = 0; i<n; i++) cout << x[i] << "					//вывод массива х
cout	<< endl;
for ( i=0; i<n; i++)			//заполнение массива D последних цифр
cout	D[i] =x[i] %10;
	<< "D[i]" << endl;			";	//вывод массива D
for (i = 0; i<n; i++) cout << D[i] << "
cout	<< endl;
int flag = 1, k=n;		//сортировка массива «пузырьком»
while (flag)
{	k--;
	flag=0;

for ( j=0; j<k; j++)

if ( (D[j] > D[j+1]) || (D[j] == D[j+1] && x[j] > x[j+1]) ) {int r=x[j];

int r1=D[j];

x[j]=x[j+1]; D[j]=D[j+1];

x[j+1]=r; D[j+1] = r1; flag=1;

}//end if

}//end while

cout << endl;	";//вывод отсортированного массива х
for (i = 0; i<n; i++) cout << x[i] << "
cout << endl;	"; // для отладки вывод массива D
for (i = 0; i<n; i++) cout << D[i] << "
cout << endl;
_getch();
return 0;
}
Программирование – лекция 12 (лекции Стрикелевой Л.В.)	24