С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

08.02.2013, 20:59. Просмотров 345. Ответов 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;
        }
    }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.02.2013, 20:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как найти кол-во сравнений в методе Шелла (C++):

Нужно чтобы введённый студент в методе 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 InsertSort(int *mas, int N) //сортировка вставками { int...

Как найти в данной сортировке количество перестановок и сравнений? - 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++
Элементы в массиве идут по возростанию.

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

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

2
ya_noob
_
203 / 147 / 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, иначе сортировка будет работать неправильно
1
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, иначе сортировка будет работать неправильно
Спасибо. Теперь считается, вроде верно).
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2013, 22:02
Привет! Вот еще темы с ответами:

Как вывести числа от 1 до 1000 без сравнений в Си++? - C++
Привет всем. Получил на собеседовании по Си++ такой странный вопрос, подумал, ещё подумал. Ничего путного в голову не пришло....

Найти ошибку в методе упорядочения Шелла - PascalABC.NET
народ мне сбросили задачу которая маё упорядочивать элементы методом шелла но она почемута не работает посмотрите где здесь ошибка есть ...

Сортировка Шелла. Количество сравнений. - C (СИ)
Здравствуйте! Может кто-нибудь помочь? Требовалось отсортировать массивы разного размера при помощи сортировки Шелла, и оценить...

Подсчет количества сравнений в методе быстрой сортировки массива - JavaScript
Есть скрипт выполняющий сортировку массива методом быстрой сортировки. Не могу разобраться, как реализовать подсчет и вывод количества...


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

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

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