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

    Определение: сортирането е подреждане на елементите на масив по
определен признак. Обикновенно се подреждат (сортират) числа по
големина в нарастващ или намаляващ ред. Когато масивът е съставен
от низове ( имена) имената се подреждат по азбучен ред.
Съществуват различни начини на сортиране.
    I. За обучение най-често се използва метода на пряката размяна
по популярен с името "Метод на мехурчето" .

   Пример 1: Възможно най-опростен пример за сортиране по
"Метода на мехурчето". Въвеждаме 10 цели числа от клавиатурата
и програмата ги подрежда във възходящ ред.

#include<iostream> // for Code Blocks
using namespace std;
int main()
{
   int i,n=10,a[n],j,buf;
   for(i=0;i< n;i++)
       cin >>a[i];
   for(i=0;n >i;i++)
   for(j=n-1;j >i;j--)
      if(a[j-1] >a[j])
       {
          buf=a[j-1];
          a[j-1]=a[j];
          a[j]=buf;
       }
 for(i=0;i< n;i++)
    cout<< a[i]<< "\n";
 return 0;
 }

    Обяснение: Нарича се "метод на мехурчето" защото се
сравняват стойностите на два съседни елемента if(a[j-1] >a[j])
(като се започне от последния елемент).
Ако стойността на последния елемент е по-малка от стойността
на пред последния елемент си разменят местата.
Чрез кода :
       {
          buf=a[j-1];
          a[j-1]=a[j];
          a[j]=buf;
       }
След това се проверява съответно стойността на пред последния елемент с тази на пред-пред последния елемент, ако по-малката
стойност е в пред последния елемент, пак си разменят стойностите
и т.н. Целта на тези съседни сравнения е най-малката стойност
да се премести в началото на масива (на първа позиция). Това се
получава при първото обхождане на масива. При второто обхождане
пак започваме от последния елемент и по същия начин втората
по големина най-малка стойност трябва да се премести на втора
позиция в масива.
                                    Важно !
   При първото обхождане външния цикъл приема стойност i=0, а
вътрешният се превърта от j=9 до j=1,(но се сравняват стойностите
с a[j-1], фактически с нулевия елемент т.е с първата стойност), по
този начин най-малкия елемент отива на първа позиция. При второто
обхождане i=1 , j се превърта от j=9 до j=2 , подрежда се втория по
големина елемент на втора позиция. При третото обхождане i=3 и т.н.
Основния код за сортира масив:
   for(i=0;i< n;i++)
   for(j=n-1;j >i;j--)
      if(a[j-1] >a[j])
       {
          buf=a[j-1];
          a[j-1]=a[j];
          a[j]=buf;
       }


   Пример 2: "Метода на мехурчето". По-изчистен код за сортиране.
Въжеждаме, от колко елемента ще бъде масива (от 2 до 999).

#include<iostream> // for Code Blocks
using namespace std;
int main()
{
   int a[999], n;
   cout<< " Input how many elements will be array contains ( 2 - 999) ==>";
   cin>>n;
   int i,j,buf;
   for(i=0;i< n;i++)
    {
         cout<< "a=["<< i+1<< "]=>";
         cin >>a[i];
    }
   for(i=1;n>i;i++)
   for(j=n-1;j >=i;j--)
      if(a[j-1] >a[j])
       {
          buf=a[j-1];
          a[j-1]=a[j];
          a[j]=buf;
       }
    cout<< endl;
 for(i=0;i< n;i++)
    {
         cout<< "a=["<< i+1<< "]=>";
          cout<< a[i]<< endl;
    }
 return 0;
 }

    II. Алгоритъм за сортиране "Пряк избор"
Масивът се преглежда N-1 пъти, при първото обхождане елементът
с най-голяма стойност заема последна позиция в масива.
При второто обхождане намираме отново най-големия елемент,
от вече останалите N-1 елемента и го поставяме на пред-последна
позиция. По този начин преглеждаме последователно N-2, N-3 ... 2
елементи, до достигане до най-малкия елемент, който вече е сортиран
и се намира на първа позиция.

   Пример 3: Програмата сама избира 10 случайни числа и след това
ги подрежда във възходящ ред.

#include<iostream> // for Code Blocks
#include<stdlib.h>
#include<time.h>
using namespace std;
   main()
    {
      int N=10, max;
      int i,j,a[N],buf,b;
      srand((time(0)));
        for (i=0;i< N;i++)
         {            a[i]=rand()%101;
           cout<< a[i]<< ";";
         }
      cout<< endl<< endl;
        for (i=N-1;i >0;i--)
         {
          max=0;
          for (j=0;j< i+1;j++)
            if (a[j] >a[max]) max=j;
             buf=a[i];
             a[i]=a[max];
             a[max]=buf;
         }
        for (i=0;i< N;i++)
         {
           cout<< "A["<< i<< "]=>";
           cout<< a[i]<< endl;
         }
      cout<< endl<< endl;
      return 0;
}
Следва обяснение ...


   Пример 3: Quick sort - "бързо" сортиране на масив.
Редактиране и компилиране ( за Linux):
cd ..
cd usr/bin
gedit qsort1.cpp

              Копирате от тук:

#include<stdlib.h> // tested on linux/ Windows
#include<iostream>
using namespace std;
   int n;
int sort (const void * a, const void * b)
{
   int x,y;
   x= *((int*)a);
   y= *((int*)b);
     if(x< y) return -1;
     if(x==y) return 0;
  return 1;
}
int main ()
  {
    cout<<"Enter the number of elements in the array n=";
    cin>>n;
   int i,a[n];
    for(i=0;i< n;i++)
      {
        cout<<"a["<< i<<"]=>";
        cin>>a[i];
      }
qsort (((void *)a),n, sizeof(a[0]), sort);
   for(i=0;i< n;i++)
     cout<< a[i]<< "; ";
   return 0;
}

              До тук:

Компилираме :
g++ qsort1.cpp -o qsort1
Стартиране:
./qsort1

Примерен изход:
Enter the number of elements in the array n=5
      a[0]=>77
      a[1]=>55
      a[2]=>44
      a[3]=>999
      a[4]=>45

       44; 45;  55;  77;  999;


   Пример 4: Сортираме масив от низове,
използвам библиотеката <algorithm> за да мога да пoлзвам функцията qsort - за "бързо" сортиране. Редактиране и компилиране ( на Eclips):

#include <iostream> //for Eclipse/Linux
#include <string.h>
#include <algorithm>
using namespace std;
bool comp(string a,string b)
{
return a< b;
}
int main()
{
int n=5;
string arr[]={"www","apple","banana","orange","pear"};
sort(arr,arr+n,comp);
for(int i=0;i< n;i++)
{
cout<< arr[i]<< " ";
}
}

Следва продължение ...