C++ : Алгоритмы сортировок

Для начала немного теории:

Сортировка – это упорядочение данных по некоторому признаку.

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

Сейчас мы будем говорить про сортировку массивов, то есть про Внутреннюю сортировку данных.

Сортировка массивов

Пусть задан массив с элементами a1, a2, .......an, которые нужно расположить в возрастающем порядке.

Будем сначала классифицировать методы по их экономичности, т.е. по времени их работы. Хорошей мерой эффективности может быть С - число необходимых сравнений ключей и М - число перестановок элементов.

Для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.

Методы сортировки можно разбить в соответствии с определяющими их принципами на три основные категории.

1.              Прямое включение (by insertion).

2.              Прямой выбор (by selection).

3.              Прямой обмен (by exchange) (пузырьковый метод).

Пример алгоритма  Прямое включение с «барьером»

  

void SortInsertionSentinel(int n, int *a)

{

   int i,j,x,k;

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

   {

      x=a[i]; j=i;a[0]=x;

              while (x<a[j-1])

              {

                 a[j]=a[j-1];

                         j--;

              }

              a[j]=x;

              cout<<"\n"<<i-1<<" prochod"<<endl;

              for (k=1; k<=n; k++)

              {

                  cout<<a[k]<<" ";

              }

   }

}

           Пример алгоритма Прямое включение без «барьера»

void SortInsertion(int n, int *a)

{

   int i,j,x,k;

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

   {

      x=a[i]; j=i;

              while ((j>0)&&(x<a[j-1]))

              {

                 a[j]=a[j-1];

                         j--;

              }

              a[j]=x;

              cout<<"\n"<<i<<" prochod"<<endl;

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

              {

                  cout<<a[k]<<" ";

              }

   }

}

 Прямой выбор

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

1)    выбирается элемент с наименьшим ключом;

2)    он меняется местами с первым элементом .

Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один самый большой элемент.

void SortSelection(int n, int *a)

{

   int i,j,x,k,m;

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

   {

      x=a[i]; k=i;

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

               if (a[j]<x) {k=j; x=a[k];}

         a[k]=a[i]; a[i]=x;

         cout<<"\n"<<i+1<<" prochod"<<endl;

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

         {

             cout<<a[m]<<" ";

         }

   }

}

Прямой обмен

Этот алгоритм основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.

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

       Прмой обмен («пузырек»)

void BubbleSort(int n, int *a)

{

   int i,j,x,k;

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

   {

      for (j=n-1; j>=i; j--)

             if (a[j-1]>a[j])

             { x=a[j-1];

               a[j-1]=a[j];    

               a[j]=x;

             }

         cout<<"\n"<<i<<" prochod"<<endl;

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

         {

             cout<<a[k]<<" ";

         }

   }

}

Продолжение следует))