---// Алгоритмы в С++. Часть 1. Сортировки.
---// Автор: \/\/oz3qK


   Данный блок статей предназначен для новичков. Но может пригодится
и для профессионалов. 

В этой статье не будет идти речь о синтаксисе языка С++. Люди не знакомые
с основами языка могут найти книгу на 
http://www.anriintern.com/computer/c++/spisok.html
http://yura-k.kiev.ua/straus/
http://www.helter10.narod.ru

Все программы протестированы на Borland C++ Builder 6, но должны
идти и на других. Написаны они как консольные приложения, но кодер без
труда применит их и в прогах с интерфейсом. Приступим...

Пожалуй, самой первой программой в этом цикле статей должна быть сортировка.
Суть сортировки состоит в том, чтоб отсортировать данные в файле, отсортировать
массив чисел в порядке их возрастания или убывания. Сортировки необходимая вещь
в современном мире. Программы, работающие с базами данных, различные программы 
применяют сортировки. Наверное, вам приходилось сортировать какие-то данные.

Самая простая сортировка (так называемый "пузырек"). 
Отсортируем с ее помощью массив:  17 9 6 14 19 5
Проходим от первого элемента до последнего и сравниваем соседние элементы.
Если слева больше, то меняем их местами (таким образом, справа всегда будет
больший). После такого преобразования будет такое :
9 6 14 17 5 | 19  - 19 уже отсортировано, теперь можно проходить не до конца,
                    а на один элемент меньше. После второй операции :
6 9 14 5 | 17 19  - Потом :
6 9 5 | 14 17 19
6 5 | 9 14 17 19
5 | 6 9 14 17 19
Вот и все. Текст сортировки приведен ниже. 

<##############################################################################>

#include <iostream>
using namespace std;
//========================================================
int array[100];                               // наш массив
//========================================================
void Sort(int col)			          // сортировка
{
    int trash=0;                              // временная переменная для
				                      // хранения промежуточного
					                // результата

    for (int i=1;  i<=col  ;  i++)	          // пока не равно количеству
					                // елементов	
      {
         for (int j=1;  j<=col-i;  j++)	    // пока не равно col-i
            {
               if (array [j]>array [j+1])     // если левый элемент больше
                 {
                    trash=array[j];           // правого, то меняем
                    array [j]=array [j+1];    // их местами
                    array [j+1]=trash;
                 }
            }
      }
}
//========================================================
void Out(int col)			                 // вывод на экран нашего
{
   for (int i=1;  i<=col;  i++)		     // массива после сортировки
     cout << array [i] <<" ";
   cout << endl;  
}
//========================================================
int main()
{
   int col_el;
   
   cout << "  Enter length of array"<< endl;
   cin >> col_el;			                  // считываем количество элементов
       for (int n=1; n<=col_el ; n++)	      // считываем элементы массива
         cin >> array[n];
   Sort(col_el);	
   cout << "Result is :"<<endl;		      // сортируем их...	
   Out(col_el);				            // и выводим	
   cin >> col_el;			                  // ждем нажатия клавиши	
   return 0;
}


<##############################################################################>


Данная программа не доделана окончательно, в частности нет проверки на выход за пределы массива и прочее...
Мы заводим массив на 100 элементов, затем считываем количество элементов
 вызываем процедуру
сортировки. Вроде все понятно...


Это можно упростить до следующего вида :

<##############################################################################>

#include <iostream>
using namespace std;
//========================================================
int array[100];
//========================================================
void Sort(int col)
{
    int trash=0;
    bool f=true;
    for (int i=1;  (i<=col) && (f=true)  ;  i++)
      {
         f=false;
         for (int j=1;  j<=col-i;  j++)
            {
               if (array [j]>array [j+1])
                 {
                    trash=array[j];
                    array [j]=array [j+1];
                    array [j+1]=trash;
                    f=true;
                 }
            }
      }
}
//========================================================
void Out(int col)
{
   for (int i=1;  i<=col;  i++)
     cout << array [i] <<" ";
   cout << endl;
}
//========================================================
int main()
{
   int col_el;
   
   cout << "  Enter length of array"<< endl;
   cin >> col_el;			      
       for (int n=1; n<=col_el ; n++)	      
   cin >> array[n];
   Sort(col_el);	
   cout << "Result is :"<<endl;		      	
   Out(col_el);				      	
   cin >> col_el;			      	
   return 0;
}
<##############################################################################>

Суть упрощения заключается в том, что используется дополнительная булевская переменная F.
При каждом заходе в первый цикл ей присваивается значение false и если в процессе выполнения
один из элементов будет не отсортирован, то значение этой переменной меняется на true
и первый цикл продолжается дальше. Если значение не поменялось, то это значит, что уже нечего
сортировать.

Данная сортировка выполняет n*(n-1)*(n-2)*...*(2)*(1) операций в худшем случае.



Следующая сортировка носит название "сортировка Шейкера".
Она похожа на первую, но более оптимизирована. Суть оптимизации в том, что данные сортируются
"волнообразно", программа проходит массив с лева на право, а потом с права на лево. Когда идем 
с лева, то собираем справа большие числа, а когда справа, то собираем слева меньшие.

<##############################################################################> 
 
#include <iostream>
using namespace std;
//========================================================
int array[100];
//========================================================
void Sort(int col)
{
    int trash=0;
    bool f=true;
    for (int i=1;  (i<=col) && (f=true)  ;  i++)
      {
         f=false;
         for (int j=i;  j<=col-i;  j++)	        // проходим с лева на право 
            {
               if (array [j]>array [j+1])  	  // если число слева больше числа
                 {
                    trash=array[j];		        // справа, то меняем местами
                    array [j]=array [j+1];	  // справа собираются большие числа
                    array [j+1]=trash;
                    f=true;
                 }
            }
	 for (int j=col-i-1;  j>i  ;  j--)	        // проходим с права на лево
	    {
   	       if (array [j]<array[j-1])	        // если число справа меньше числа
	         {
		    trash=array[j];		        // слева, то меняем местами
		    array [j]=array [j-1];	        // слева собираются меньшие числа
		    array [j-1]=trash;	
		    f=true;		
		 }
   		    	
	    }	
      }
}
//========================================================
void Out(int col)
{
   for (int i=1;  i<=col;  i++)
     cout << array [i] <<" ";
   cout << endl;
}
//========================================================
int main()
{
   int col_el;
   
   cout << "  Enter length of array"<< endl;
   cin >> col_el;			      
   cout << "  Enter array elements"<<endl;   
    for (int n=1; n<=col_el ; n++)	
       {
   cout <<n<<"  :" << "\t";      
   cin >> array[n];
   
       }
   Sort(col_el);	
   cout << "Result is :"<<endl;		      	
   Out(col_el);				      	
   cin >> col_el;			      	
   return 0;
}

<##############################################################################> 

По сравнению с сортировкой методом "пузырька", эта сортировка быстрее.
И выполняются n*(n-1+n-2)*(n-2+n-3)*...*(2+1)=n*(2n-3)*(2n-5)*...*3.
В следующих статьях, я расскажу про более быстрые сортировки и о самой быстрой 
известной сортировки. Что не ясно, пишите на woz3qk@mail.ru. Отвечу.
До встречи...

---// 21.05.2004 | RusH security team | http://rst.void.ru