Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
_Edith
0 / 0 / 1
Регистрация: 02.04.2011
Сообщений: 99
#1

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется - C++

25.12.2014, 12:54. Просмотров 593. Ответов 3
Метки нет (Все метки)

Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком или сортировка Шелла. Вот она то и не работает, помогите кто знает.
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <locale>
#include <time.h>
#include <cstdlib>
#include <deque>
#include <stdlib.h>
 
using namespace std;
 
void bubble_sort(int *mass, int N)
{
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < N - i - 1; j++)
        {
            if (mass[j] > mass[j + 1])
            {
                swap(mass[j], mass[j + 1]);
            }
        }
    }
}
 
int increment(long inc[], long size)
{
    int p1, p2, p3, s;
    p1 = p2 = p3 = 1;
    s = -1;
    do
    {
        if (++s % 2)
        {
            inc[s] = 8 * p1 - 6 * p2 + 1;
        }
        else
        {
            inc[s] = 9 * p1 - 9 * p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
        p1 *= 2;
    } while (3 * inc[s] < size);
 
    return s > 0 ? --s : 0;
}
 
template< class T >
void shell_Sort(T a[], long size)
{
    long inc, i, j, seq[40];
    int s;
 
    s = increment(seq, size); // вычисление последовательности приращений
    while (s >= 0)  // сортировка вставками с инкрементами inc[] 
    {
        inc = seq[s--];
        for (i = inc; i < size; ++i)
        {
            T temp = a[i];
            for (j = i - inc; (j >= 0) && (a[j] > temp); j -= inc)
                a[j + inc] = a[j];
            a[j] = temp;
        }
    }
}
 
int main()
{
    locale::global(locale(""));
    srand((unsigned)time(NULL));
 
    int N, i;
    double A, B, X;
    int temp = 0;
    int from, to;
    char *type = new char[6];
 
    cout << "Введите размерность массива: ";
    cin >> N;
 
    cout << endl << "Введите диапазон случайных чисел: ";
    cin >> from >> to;
 
    int *mass = new int[N];
 
    cout << endl << "Полученный массив:" << endl;
 
    for (i = 0; i < N; i++)
    {
        mass[i] = rand() % (to - from + 1) + from;;
        cout << mass[i] << " ";
 
        temp = temp + mass[i];
    }
 
    cout << endl<< "bubble или shell?" << endl;
    cin >> type;
 
    while (strcmp(type, "Bubble") != 0 && strcmp(type, "bubble") != 0 && strcmp(type, "Shell") != 0 && strcmp(type, "shell") != 0)
    {
        cout << "Попробуте еще раз.";
        cin >> type;
    }
 
    if (strcmp(type, "Bubble") == 0 || strcmp(type, "bubble") == 0)
        bubble_sort(mass, N);
    else
        shell_Sort(mass, N);
 
    system("pause");
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2014, 12:54
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется (C++):

Написал программку с рекурсией. Не могу понять, почему не изменяется аргумент.
Еще раз здравствуйте. Днем будучи в очереди которая затянулась на 2 часа, решил...

Написал программу, не могу понять правильно или нет
Написать функцию sum с переменным числом параметров, которая находит сумму...

Написал программу, но она что-то не совсем то, выдает, не могу понять в чем проблема
При х=3, y= -6 после выполнения фрагмента алгоритма 1. если y&lt;x, то y=y+x...

Сортировка Шелла и пирамидальная сортировка для символов
Здраствуйте, можете пожалуйста привести пример сортировок шелла и ...

Не могу понять где ошибка. Сортировка пузырьком
Суть такова. заполняю массив и он должен сортировать. но после компиляции...

Сортировка Шелла и сортировка вставками
Напишите программу для: 1)Сортировка вставкой 2)сортировка Шелла

3
Sonance
6 / 6 / 5
Регистрация: 15.02.2013
Сообщений: 56
25.12.2014, 14:14 #2
Эти алгоритмы в готовом виде есть в википедии. Простите конечно, но ваш код - неосмысленный бред. Непонятные названия переменных, непонятное объявление шаблона класса(зачем тут вообще шаблоны? странно что вообще компилится). Для решения достаточно знать основы Си, Или хотя бы правильно скопировать код из википедии.
0
_Edith
0 / 0 / 1
Регистрация: 02.04.2011
Сообщений: 99
26.12.2014, 11:13  [ТС] #3
Sonance, хорошо, я понял, но вот как это описывается в википедии:
C++
1
2
3
4
5
6
7
8
template< typename RandomAccessIterator, typename Compare >
void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp )
{
    for( typename std::iterator_traits< RandomAccessIterator >::difference_type d = ( last - first ) / 2; d != 0; d /= 2 )
        for( RandomAccessIterator i = first + d; i != last; ++i )
            for( RandomAccessIterator j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d )
                std::swap( *j, *( j - d ) );
}
и вопрос в том, как к ней потом обратиться в самой программе?
0
alptp
5 / 5 / 6
Регистрация: 15.10.2014
Сообщений: 18
26.12.2014, 21:26 #4
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <time.h>
using namespace std;
 
// Ввод параметров
void input_params(int&, int&, int&);
// Создание массива
int* create_array(const int, const int, const int);
// Вывод массива
void print_array(int*, const int);
// Выбор метода сортировки
int menu_sort();
// Сортировка
void bubble_sort(int*, const int);
void shell_sort(int*, const int);
 
// Массив из указателей на функцию
void (*sort [2]) (int*, const int) = {bubble_sort, shell_sort};
 
 
int main()
{
    int size, low, high;
    input_params(size, low, high);
    
    int *arr = create_array(size, low, high); 
    
    print_array(arr, size);
    
    // Выбор метода сортировки массива
    (*sort[menu_sort()])(arr, size);
 
    print_array(arr, size);
    
    // Удаление динамического массива
    delete [] arr;
    
    return 0;
}
 
void input_params(int &size, int &low, int &high)
{
    cout << "Size of array: ";  cin >> size;    
    cout << "Low border: ";     cin >> low;     
    cout << "High border: ";    cin >> high;    
}
 
 
int* create_array(const int size, const int low, const int high)
{
    srand(time(NULL));                          // для истинной рандомизации
    int *arr = new int[size];
    for(int i = 0; i < size; ++i)
        arr[i] = low + rand() % (high - low + 1);  // рандомизация в пределах   
    return arr;
}
 
void print_array(int *arr, const int size)
{
    cout << "ARRAY:";
    for(int i = 0; i < size; ++i)
    {
        if (i % 10 == 0)  cout << '\n'; // в строке печатать не более 10 значений
        cout << arr[i] << '\t';         // значения разделять табуляцией
    }
    cout << '\n';
}
 
int menu_sort()
{
    char ch;
    do 
    {
        cout << "1. Bubble sort\n";
        cout << "2. Shell sort\n";
        cout << "Select a number: ";
 
        cin >> ch;
 
    } 
    while(!strchr("12", ch));
    return ch-49;               // преобразование к целочисленному эквиваленту
}
 
void bubble_sort(int *arr, const int size)
{
    for (int i = size - 1; i >= 0; i--)
        for (int j = 0; j < i; j++)
            if (arr[j] > arr[j+1]) swap(arr[j], arr[j + 1]);
}
 
// Идея метода заключается в сравнение разделенных на группы элементов
// находящихся друг от друга на некотором расстоянии d
// Изначально это расстояние равно d = size div 2 (тоже самое d = d >> 1)
// На первом шаге из каждой группы сравниваются два элемента расположенных друг от друга на расстоянии d;
// В случае необходимости, меняются местами.
// На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на 2.
void shell_sort(int *arr, const int size)
{
    int d = size >> 1;
    while (d > 0)
    {
        for (int i = 0; i < (size - d); i++)
        {
            int j = i;
            while (j >= 0 && arr[j] > arr[j + d])
            {
                swap(arr[j], arr[j + d]);
                j--;
            }
        }
        d = d >> 1;
    } 
};
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.12.2014, 21:26
Привет! Вот еще темы с решениями:

Пирамидальная сортировка и сортировка Шелла
Ребята помогите пожалуйста, я NEWBIE и не могу решить такая задача : Выполнить...

Сортировка Шелла
Здравствуйте. Решил сравнить скорость действия сортировки Шелла с различными...

C++ Сортировка Шелла?
Здравствуйте. Нужно написать сортировку Шелла, но они все так похожи, что не...

Сортировка Шелла
Ребят помогите. есть матрица нужно отсортировать каждую строчку матрицы по...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru