Форум программистов, компьютерный форум CyberForum.ru

Шейкер Сортировка! Непонятны некоторые моменты - C++

Восстановить пароль Регистрация
 
_Mars_
0 / 0 / 0
Регистрация: 13.10.2013
Сообщений: 37
14.10.2013, 17:34     Шейкер Сортировка! Непонятны некоторые моменты #1
Столкнулся с задачей реализации Шейкер сортировки .Почитал теорию и понял , что она очень похожа на пузырьковую. Но столкнулся с примером кода и стало кое-что не понятно .
Вот пример:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}
Я понял с прочитанного, что суть алгоритма в том, что данные сортируются "волнообразно", при этом программа сначала проходит массив слева направо, а потом справа налево. Когда идем слева, то собираем справа большие числа, а когда справа, то собираем слева меньшие.Я всё прорешал вручную и понял суть , но вот с кодом не разобрался.
У меня появились вопросы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trash=0;   //для чего это?
bool f=true;         //..и это?
 
.....
for (int i=1; (i<=col) && (f=true) ; i++)   - что выполняется в этом цикле?
запутался с этим флагом :изначально он true, но когда входим в цикл , он стает false , а затем опять true- я не пойму - почему ? 
 
 
for (int i=1; (i<=col) && (f=true) ; i++)
-как понять , что справа на лево? не могу разобраться, что за условие границы
 
(i<=col) && (f=true)
-пока i меньше количества элементов и флаг=тру? что это значит? 
 
и вот здесь ещё цикл:
 
for (int j=i; j<=col-i; j++) // почему именно слева направо?
 
for (int j=col-i-1; j>i ; j--)  //почему именно справа налево?что за такие условия в цикле
Извините за такое количество вопросов , но я уже и нарисовал , и понял как оно сортируется , но вот с этими циклами и условиями совсем запутался , а так хочется разобраться нормально..
Помогите , пожалуйста , новичку . Расскажите подробненько) Надеюсь на Вашу помощь .
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.10.2013, 17:34     Шейкер Сортировка! Непонятны некоторые моменты
Посмотрите здесь:

C++ Циклы в Си++, хотелось бы уточнить некоторые моменты
Шейкер Сортировка C++
Задача по наследованию. Не понимаю некоторые моменты в формулировке задания C++
Объясните некоторые моменты в задаче C++
C++ Quick sort, не понятно некоторые моменты.
Непонятны некоторые операторы C++
Непонятны некоторые функции C++
Не работает swap и непонятны некоторые строки в программе C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nalasco
0 / 0 / 0
Регистрация: 11.10.2013
Сообщений: 3
15.10.2013, 00:42     Шейкер Сортировка! Непонятны некоторые моменты #2
int trash=0; //для чего это?
это дополнительная переменная для того, чтобы можно было поменять местами значения переменных

к примеру

int a = 5, b = 6;
cout << a << b ; // 5 6
int tmp = a;
a = b;
b = tmp;
cout << a << b ; // 6 5


bool f=true; //..и это? - когда идет проход по внутреннему циклу - например справа налево, мы сравниваем поочередно соседние элементы, выталкивая самый легкий(наименьший) вперед. То есть если есть неупорядоченные элементы - мы заходим в if (array [j]>array [j+1]) и значение флага меняется на true, что и есть одним из условий работы внешнего цикла for (int i=1; (i<=col) && (f=true) ; i++). Если же входной массив упорядочен, тогда значение флага остается false и программа не проходит лишний раз по этим элементам снова.
Алгоритм Шейкера - это и есть тот самый пузырьковый метод, только усовершенствованный


Алгоритм шейкера уменьшает количество перемещений по циклу, действуя по следующей схеме:
1. За первый проход из всех элементов выбирается минимальный и максимальный.
2. Минимальный элемент помещается в начало массива, а максимальный, соответственно в конец.
3. Далее алгоритм выполняется для остальных данных.
Yandex
Объявления
15.10.2013, 00:42     Шейкер Сортировка! Непонятны некоторые моменты
Ответ Создать тему
Опции темы

Текущее время: 08:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru