C++ C++ C# C# ASP.NET Security ASP.NET Security ASM ASM Скачать Скачать Поиск Поиск Хостинг Хостинг  
  Программа для работы с LPT портом...
Язык: .NET — ©Alexey...
  "ASP.NET Atlas" – AJAX в исполнении Micro...
Язык: .NET — ©legigor@mail.ru...
  "Невытесняющая" Многопоточность...
Язык: C/C++ — ©...
  Update World C++: Сборник GPL QT исходников
  Весь сайт целиком можно загрузить по ссылкам из раздела Скачать

 Алгоритмы в С++. Часть 1. Сортировки / Другое. / Алгоритмы

---// Алгоритмы в С++. Часть 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 элементов, затем считываем количество элементов
вызываем процедуру
сортировки. Вроде все понятно...


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

#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