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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
bloodflood
0 / 0 / 0
Регистрация: 07.02.2013
Сообщений: 11
#1

Как найти кол-во сравнений в методе Шелла - C++

08.02.2013, 20:59. Просмотров 307. Ответов 2
Метки нет (Все метки)

Здравствуйте, у меня есть двумерный массив, отсортированный методом Шелла, нужно найти кол-во сравнений и перестановок в нем. Кол-во перестановок я нашел. А вот найти кол-во сравнений не удается. Буду благодарен помощи. shift_shell считает кол-во перестановок.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    int step=n/2;
    for (int i=0; i<m; i++) 
    {
        while (step>0)
        {
            for (int j=0; j<(n-step); j++)
            {
                int k=j;
                while (k>=0 && abs(arr[i][k])>abs(arr[i][k+step]))
                {
                    noun=arr[i][k];
                    arr[i][k]=arr[i][k+step];
                    arr[i][k+step]=noun;
                    k--;
                    shift_shell++;
                }
            }
            step=step/2;
        }
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.02.2013, 20:59     Как найти кол-во сравнений в методе Шелла
Посмотрите здесь:

C++ Как возвратить указатель на объект, созданный в методе?
C++ Ошибка в методе, как исправить?
Можите найти ошибку в методе простых итераций он не расчитывает кубический корень C++
C++ Как определить количество перестановок и сравнений
Нужно чтобы введённый студент в методе in вывелся на экран как в методе out C++
C++ Как теоретически (не программно) посчитать количество сравнений и обменов в пузырьковой сортировке?
Найти количество сравнений после сортировки массива C++
Как найти в этой сортировке количество перестановок и сравнений? C++
Как найти в данной сортировке количество перестановок и сравнений? C++
Как в методе класса осуществить вывод переменной C++
Как определить количество перестановок и сравнений в выборочной сортировке C++
Как определить количество сравнений и перестановок в быстрой сортировке массива C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
08.02.2013, 21:25     Как найти кол-во сравнений в методе Шелла #2
попробуй так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    int step=n/2;
    for (int i=0; i<m; i++) 
    {
        while (step>0)
        {
            for (int j=0; j<(n-step); j++)
            {
                int k=j;
                while (k>=0 && abs(arr[i][k])>abs(arr[i][k+step]))
                {
                    noun=arr[i][k];
                    arr[i][k]=arr[i][k+step];
                    arr[i][k+step]=noun;
                    k--;
                    shift_shell++;
                    compare_shell++;
                }
                if (k>=0) compare_shell++;
            }
            step=step/2;
        }
    }
или так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    int step=n/2;
    for (int i=0; i<m; i++) 
    {
        while (step>0)
        {
            for (int j=0; j<(n-step); j++)
            {
                int k=j;
                while (k>=0 && (++compare_shell && abs(arr[i][k])>abs(arr[i][k+step])))
                {
                    noun=arr[i][k];
                    arr[i][k]=arr[i][k+step];
                    arr[i][k+step]=noun;
                    k--;
                    shift_shell++;
                }
            }
            step=step/2;
        }
    }
второй вариант подразумевает, что изначально compare_shell >= 0, иначе сортировка будет работать неправильно
bloodflood
0 / 0 / 0
Регистрация: 07.02.2013
Сообщений: 11
08.02.2013, 22:02  [ТС]     Как найти кол-во сравнений в методе Шелла #3
Цитата Сообщение от ya_noob Посмотреть сообщение
попробуй так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    int step=n/2;
    for (int i=0; i<m; i++) 
    {
        while (step>0)
        {
            for (int j=0; j<(n-step); j++)
            {
                int k=j;
                while (k>=0 && abs(arr[i][k])>abs(arr[i][k+step]))
                {
                    noun=arr[i][k];
                    arr[i][k]=arr[i][k+step];
                    arr[i][k+step]=noun;
                    k--;
                    shift_shell++;
                    compare_shell++;
                }
                if (k>=0) compare_shell++;
            }
            step=step/2;
        }
    }
или так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    int step=n/2;
    for (int i=0; i<m; i++) 
    {
        while (step>0)
        {
            for (int j=0; j<(n-step); j++)
            {
                int k=j;
                while (k>=0 && (++compare_shell && abs(arr[i][k])>abs(arr[i][k+step])))
                {
                    noun=arr[i][k];
                    arr[i][k]=arr[i][k+step];
                    arr[i][k+step]=noun;
                    k--;
                    shift_shell++;
                }
            }
            step=step/2;
        }
    }
второй вариант подразумевает, что изначально compare_shell >= 0, иначе сортировка будет работать неправильно
Спасибо. Теперь считается, вроде верно).
Yandex
Объявления
08.02.2013, 22:02     Как найти кол-во сравнений в методе Шелла
Ответ Создать тему
Опции темы

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