Сравнение прямых методов сортировки.

Название метода	C(n)		M(n)			T(n)
	в лучшем случае	в худшем случае	в лучшем случае	в худшем случае	в лучшем случае		в худшем случае
Прямой Выбор	n^2-n 2	n^2-n 2	3(n-1)	3(n-1)+n^2/4	5n^2+ 23n -11 2 2		13n^2+ 23n -11 2 2
Прямой Обмен	n^2-n 2	n^2-n 2	0	3(n^2-n) 2	7n^2+ 5 n -3 2 2		8n^2-2n-3
Прямое Включение	n-1	n^2-n 2	2(n-1)	n^2+3n-4 2	18n — 16		5n^2+8n-11

Выводы:

1. Все прямые методы сортировки порядка О( n²), т.к. Т(n) C n² в худшем случае.

2. В худшем случае Обменная сортировка проигрывает сортировке Выбором и сортировке Включением. Из этих двух последних сортировка Выбором лучше, т.к. в ней меньше перестановок, отсюда рекомендация: при сортировке сложных (громоздких) данных использовать сортировку Выбором.

3. Сортировка выбором никак не реагирует на упорядоченность элементов. Поэтому рекомендуется: в случае почти упорядоченной совокупности использовать сортировку Включением.

4. При небольших n затраты временные во всех трёх методах практически одинаковые. Из-за простоты метода лучше всего запоминается и часто используется именно метод Обменной сортировки.

Cортировка сложных данных

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

Для данных сложных типов не определены операции отношения, поэтому (если они определены в самой задаче) проверки типа if a[j] > a[j+1] { ….} оформляются в процедурах или функциях. Например, функция P(a,b) возвращает true, если a > b. Тогда указанный фрагмент запишется if ( P(a[j] , a[j+1] ) ) { …}

В случае сортировки по значениям упорядочивающей функции f(x) рекомендуется сформировать вектор значений упорядочивающей функции U = {f(a₁ ), f(a ₂) , …,f(a _n )}. Сравнения элементов в описанных алгоритмах заменяются сравнением значений упорядочивающей функции, но переставлять в этом случае необходимо и сами элементы и значения упорядочивающей функции. Например, фрагмент пузырьковой сортировки запишется так

if (u[j] > u[j+1] ) { u[j]  u[j+1] ; а[j]  a[j+1]};

При сортировке сложных данных часто, чтобы не переставлять элементы в совокупности и значения упорядочивающей функции, применяют алгоритмы сортировки с использованием вектора индексов. Для этого заводят специальный вектор, назовём его Ind : помещают в Ind индексы элементов 1, 2, 3, …,n. В алгоритмах сортировки вместо перестановки элементов и значений упорядочивающей функции переставляют их индексы. Однако, необходимо помнить в этом случае, что доступ к элементам совокупности и значениям упорядочивающей функции выполняется через вектор индексов:

a[ Ind[j] ] вместо a[j], u[ Ind [j] ] вместо u[ j ]

if (a[ Ind[j] ] >a[ Ind[j+1] ]) { Ind[j] Ind[j+1] }

if (u[ Ind [j] ]> u[ Ind [j+1] ]) { Ind[j] Ind[j+1] }

Пример для лекции //sortstrmatr.cpp

#include <iostream>

using namespace std;

// В целочисленной матрице отобрать те её строки,

// у всех элементов которых сумма цифр одинакова.

// Отобранные строки отсортировать по возрастанию

// сумм цифр элементов.

const int ni=5,nj=6;

int sumdigit(int a)

{//сумма цифр числа a

int s=0;

while (a>0)

{s=s+a%10; a=a/10;}

return s;}

bool provstr(int k,int a[],int& s)

//проверка, у всех ли элементов строки сумма цифр одинакова.

{bool f;int i;

s=sumdigit(abs(a[0]));

for(i=1,f=true;(i<k)&&(f==true);i++)

f=s==sumdigit(abs(a[i]));

return f;}

void writestr(int k,int a[])

{// вывод строки на зкран

for (int i=0; i<k; i++)

cout <<a[i]<<" ";

cout <<"\n"; }

int main ()

{ int k,l,i,j,u,r;

int a [ni][nj];

int x[ni];

int ind[ni];

// чтение матрицы

cout<<"\n kol-vo ctrok <= "<<ni;

cin>>k;

cout<<"\n kol-vo ctolbcov <="<<nj;

cin>>l;

u=0; //кол-во отобранных строк

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

{cout <<"\n"<<i+1<<" stroka: ";

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

cin>>a[u][j];

if(provstr(l,a[u],x[u])){ind[u]=u;u=u+1;}

}

if (u==0) cout<<"\n NO STROK";

else {r=u-1;

while (r>0)

{int t=0;

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

if(x[ind[i]]>x[ind[i+1]])

{int z=ind[i];ind[i]=ind[i+1];

ind[i+1]=z; t=i;

}

r=t;}

for(i=0;i<u;i++) //вывод строк

{cout<<x[ind[i]]<<": ";

writestr(l,a[ind[i]]);

}

}

return 0;}

Пример:

Выдать на экран строки целочисленной матрицы А (n*m) в порядке возрастания количества взаимно простых пар элементов в строках.

Ind

A

K

K

Ind

Cтроки: