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

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

Восстановить пароль Регистрация
 
bloodflood
0 / 0 / 0
Регистрация: 07.02.2013
Сообщений: 11
08.02.2013, 20:59     Как найти кол-во сравнений в методе Шелла #1
Здравствуйте, у меня есть двумерный массив, отсортированный методом Шелла, нужно найти кол-во сравнений и перестановок в нем. Кол-во перестановок я нашел. А вот найти кол-во сравнений не удается. Буду благодарен помощи. 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++ как найти кол-во локальных минимумов в двумерном массиве
найти кол во пятниц с 2001 с 1 января по 2010 с 31 декабря. И найти кол во пятниц 13 числа C++
C++ Для чисел от -50 до 50 найти кол-во четных отрицательных и кол-во положительных нечетных чисел
C++ Как определить количество перестановок и сравнений
Нужно чтобы введённый студент в методе in вывелся на экран как в методе out C++
Найти количество сравнений после сортировки массива C++
Как найти в этой сортировке количество перестановок и сравнений? C++
Как найти в данной сортировке количество перестановок и сравнений? C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 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     Как найти кол-во сравнений в методе Шелла
Ответ Создать тему
Опции темы

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