5. Сортиране на масиви

-- Общи положения
 Сортиране - пренареждане на дадено множество в определен ред.
 Сортиране на масиви и сортиране на последователни файлове.

struct Item {
    int key;
    <други полета на структурата>
};
 Полето ключ съхранява функцията на пренареждане.
 Един метод за сортиране се нарича устойчив, ако относителният ред 
на елементите с равни ключове остава непроменен в процеса на
сортирането.
 Ще се разглеждат методи, при които пермутирането на елементите,
водещо до подходящото им нареждане, се извършва на място (без да
се използва втори масив).
 Мярка за ефективността на методите - броят C на сравненията и
броят M на присвояванията (движенията на елементите), като фунции
на броя n на елементите, които се сортират.
 Преки методи изискват от порякъка на n^2 сравнения и присвоявания, 
добрите методи - n.log(n).
 Класификация:
 1. сортиране чрез вмъкване
 2. сортиране чрез селекция
 3. сортиране чрез размяна.
 
const int n=<число>;
Item a[n+1]; 
Заб. Ще сортираме масива a[1]..a[n], а a[0] ще използваме за 
"ограничител" - известен метод за завършване на цикъл с 2 условия
и/или за работна променлива.

-- Сортиране чрез пряко вмъкване
for (i=2; i<=n; i++) 
{ 
 x=a[i]; 
 <вмъкване на x на подходящо място в редицата a[0]..a[i]>
}
 Вмъкването става чрез последователно сравняване и изместване,
докато x попадне на мястото си в сортираната вече редица a[1]..a[i].

void StraightInsertion(Item a[n+1])
{ 
 int i, j;
 for (i=2; i<=n; i++) 
 { 
  a[0]=a[i]; j=i-1;
  while (a[0].key < a[j].key)
  { 
   a[j+1]=a[j]; j--;
  }
  a[j+1]=a[0];
 }
}
 Броят на сравненията и движенията е:
C(min) = n-1                 M(min) = 2(n-1)
C(ave) = (n^2+n-2)/4         M(ave) = (n^2+9n-10)/4
C(max) = (n^2+n)/2-1         M(max) = (n^2+3n- 4)/2

 min се реализира, когато елементите в масива a са предварително 
сортирани по ключ
 естествено поведение + устойчив алгоритъм
 max се реализира, когато в началото елементите са подредени в
обратен ред

-- Сортиране чрез пряка селекция
for (i=1; i<=n-1; i++) 
{ 
 k=<индекса на най-малкия елемент от редицата a[i]..a[n]>; 
 <размяна на a[i] с a[k]>
}

void StraightSelection(Item a[n+1])
{ 
 int i, j, k;
 Item x;
 for (i=1; i<=n-1; i++) 
 { 
  k=i; x=a[i]; 
  for (j=i+1; j<=n; j++)
   if (a[j].key<x.key)
  {
   k=j; x=a[j];
  }
  a[k]=a[i]; a[i]=x;
 }
}
 Броят на сравненията не зависи от началния ред на ключовете и е
C = (n^2-n)/2.
 Броят на движенията е:
M(min) = 3(n-1), M(max)=[n^2/4]+3(n-1),
където [] е вземане на цяла част на число.
min (max) се реализира когато ключовете са предварително подредени
(са в обратен ред).

-- Сортиране чрез пряка размяна (методи на мехурчето)
void BubbleSort(Item a[n+1])
{
 int i, j;
 Item x;
 for (i=2; i<=n; i++) 
 { 
  for (j=n; j>=i; j--)
   if (a[j-1].key > a[j].key)
  {
   x=a[j-1]; a[j-1]=a[j]; a[j]=x;
  }
 }
}
 Броят на сравненията C = (n^2-n)/2, а на присвояванията --
M(min) = 0
M(ave) = 3(n^2-n)/4
M(max) = 3(n^2-n)/2