Печать строки после обмена

Алгоритмы сортировки и их эффективность

Сортировка – это процесс упорядочивания набора элементов в возрастающем или убывающем порядке.

Алгоритмы сортировки делятся на:

· Внутренние, когда все данные находятся в оперативной памяти и

· Внешние, - данные могут храниться на вспомогательных устройствах, например, на жёстком диске.

Результат сортировки набора чисел или символов понятен, но можно упорядочивать и объекты, в этом случае выбирается ключ сортировки (ФИО, возраст, адрес).

Анализ алгоритмов – это способы сравнения эффективности разных методов решения задач. Сравнение алгоритмов должно быть сосредоточено на их существенных различиях (время выполнения и занимаемая память). Основной способ оценки эффективности алгоритма - подсчёт его операций. Будем рассматривать фактор времени.

Время выполнения алгоритма выражается функцией, зависящей от размера задачи.

Время выполнения алгоритма А прямо пропорционально функции f(n), говорят, что алгоритм А имеет порядок f(n) и этот факт обозначается как O(f(n)).

Функция f(n) называется сложностью алгоритма.

Методы сортировки на том же месте можно разбить на три категории:

· С помощью прямого выбора,

· С помощью прямого включения,

· С помощью прямого обмена

П Р О Г Р А М М Ы С О Р Т И Р О В О К

Подготовительная часть

const int n(10);

int A[n], B[n+1], C[n], i, j, x, c;

Использование датчика случайных чисел

srand( (unsigned)time( NULL ) );

for (i=0; i<n; i++)

{

A[i] = rand() % 100;

cout << A[i] << " " ;

C[i] = B[i+1] = A[i];

}

cout << "\n\n";

//****************************************************

С О Р Т И Р О В К А В Ы Б О Р О М

Этот приём основан на следующих принципах:

· Выбирается элемент с наименьшим ключом,

· Он меняется местами с первым элементом,

· Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до последнего.

//****************************************************

cout << "S E L E C T I O N S O R T \n\n";

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

{

int min = i;

for (j=i+1; j<n; j++)

if (A[j] < A[min]) min = j;

Обмен значениями

c=A[i];

A[i]=A[min];

A[min]=c;

печать строки после обмена

for (int i1=0; i1<n; i1++)

{

cout << A[i1] << " " ;

}

cout << "\n";

}

}

cout << "\n\n";

АНАЛИЗ: Внешний цикл выполняется n-1 раз, внутренний цикл работает от 1 до n-1, => общее количество итераций внешнего цикла = (n-1)+(n-2)+…+1 = n*(n-1)/2.

Поскольку при каждой итерации выполняется одно сравнение,

Их общее количество = n*(n-1)/2. При обмене производится 3 присваивания, => всего присваиваний будет 3*(n-1).

В сумме выполняется n*(n-1)/2+3*(n-1)=n²/2+5*n/2-3 основных операций. => Сложность алгоритма сортировки методом выбора равна O(n²).

//****************************************************