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

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

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

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

08.02.2013, 20:59. Просмотров 325. Ответов 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     Как найти кол-во сравнений в методе Шелла
Посмотрите здесь:

Нужно чтобы введённый студент в методе in вывелся на экран как в методе out - C++
#include&lt;conio.h&gt; #include&lt;stdio.h&gt; #include&lt;iostream.h&gt; #include&lt;windows.h&gt; #include&lt;cstring.h&gt; // это просто для русских...

Как найти в данной сортировке количество перестановок и сравнений? - C++
void quicksort(int *mas, int first, int last) { int mid, count, m=0; int f=first, l=last; int count_compare=0, count_swap=0; ...

Как найти в этой сортировке количество перестановок и сравнений? - C++
Как найти в этой сортировке количество перестановок и сравнений? void InsertSort(int *mas, int N) //сортировка вставками { int...

Как найти кол-во различных элементов в массиве? - C++
Элементы в массиве идут по возростанию.

Найти количество сравнений после сортировки массива - C++
Нужно чтобы писала количество сравнений после сортировки массива, но я вроде все прописал #include &quot;stdafx.h&quot; #include...

Как определить количество перестановок и сравнений - C++
У меня есть алгоритм Quicksort как определить количество перестановок и сравнений?? #include &lt;iostream&gt; #include &lt;conio.h&gt; #include...

Как определить количество перестановок и сравнений в выборочной сортировке - C++
void choicesSort(int* Array, int length_array) { for (int repeat_counter(0); repeat_counter &lt; length_array; repeat_counter++) ...

Как определить количество сравнений и перестановок в быстрой сортировке массива - C++
Пробовал сделать счётчики, но они выводили кол-ва для сортировке всех подмассивов, а как вывести кол-во всех перестановок и сравнений за...

Как теоретически (не программно) посчитать количество сравнений и обменов в пузырьковой сортировке? - C++
как теоретически посчитать количество сравнений и обменов в пузырьковой сортировке?не программно

Можите найти ошибку в методе простых итераций он не расчитывает кубический корень - C++
#include&lt;stdlib.h&gt; #include&lt;math.h&gt; #include&lt;iostream&gt; #include&lt;fstream&gt; usingnamespace std; floatfun1(int num,float x,float...

Где правильно ставить счетчики сравнений и перестановок, и как считать сложность этих алгоритмов? - C++
написал код двух сортировок, но не уверен, что правильно проставлены счетчики.#include &lt;iostream&gt; #include &lt;ctime&gt; #include &lt;conio.h&gt; ...

Ошибка в методе, как исправить? - C++
void Point::Read() { int _x,_y; cin&gt;&gt;&quot;(&quot;&gt;&gt;_x&gt;&gt;&quot;,&quot;&gt;&gt;_y&gt;&gt;&quot;)&quot;; SetX(_x); SetX(_y); } Вот метод класса Point, хотел вводить...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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, иначе сортировка будет работать неправильно
Спасибо. Теперь считается, вроде верно).
Ответ Создать тему
Опции темы

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