В этой статье не будет идти речь о синтаксисе языка С++. Люди не знакомые
с основами языка могут найти книгу на
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 :"<
| // сортируем их... |
|
|
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]| // если число справа меньше числа |
|
|
{
|
|
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. Отвечу.
До встречи...
Перейти к рубрике --> C & C++ |
