Оригинальный DVD-ROM: eXeL@B DVD !
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 2 сентября!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

ПРОГРАММИРОВАНИЕ НА C и С++



Слушай, дружище, зачем так мучиться с этим языком С++, ты ведь не Билл Гейтс. Возьми тот же Python и программируй, он кроссплатформенный, под Windows тоже работает. Я сам давно заметил: то что на Си пишешь в страницу кода, на питоне решается в одну-две строки. При том, питон намного проще, я его сам недавно изучил по видеокурсу вот этому. Кстати, автор отлично там объясняет. Буквально день-два и уже будешь писать на нём, чего не скажешь про сложный С++.
 
 ---// Алгоритмы в С++. Часть 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
 
 
 
 


<< ВЕРНУТЬСЯ В ПОДРАЗДЕЛ

<< ВЕРНУТЬСЯ В ОГЛАВЛЕНИЕ




Материалы находятся на сайте https://exelab.ru/pro/



Оригинальный DVD-ROM: eXeL@B DVD !


Вы находитесь на EXELAB.rU
Проект ReactOS