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

Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
parkito
 Аватар для parkito
11 / 11 / 2
Регистрация: 22.03.2010
Сообщений: 685
26.03.2014, 23:01     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #1
Помогите пожалуйста в алгоритме быстрой сортировки посчитать количество перестановок и сравнений элементов массивов. Не могу понять куда нужно счетчики встроить.
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
void quick(int *a , int l, int r)
{
    int x = a[l + (r - l) / 2];
    
    int i = l;
    int j = r;
    
    while(i <= j)
    {   //SravQuick++;
        while(a[i] < x) {i++;}
        while(a[j] > x) {j--;}
 
        if(i <= j)
        {   swap(a[i], a[j]);
            
            i++;
            j--;
        }
    }
    if (i<r)
                quick(a,i, r);
 
    if (l<j)
        quick(a,l,j);
 
    
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2014, 23:01     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов
Посмотрите здесь:

C++ График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки
C++ Как определить количество перестановок и сравнений
Счетчик сравнений для быстрой сортировки C++
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? C++
Как подсчитать произведенное количество перестановок при быстрой сортировке? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
uburuntu
 Аватар для uburuntu
94 / 94 / 29
Регистрация: 04.10.2012
Сообщений: 188
26.03.2014, 23:04     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #2
Перестановки - это вызовы swap, а сравнения в вайлах находятся:
C++
1
2
while(a[i] < x) {i++;}
while(a[j] > x) {j--;}
parkito
 Аватар для parkito
11 / 11 / 2
Регистрация: 22.03.2010
Сообщений: 685
26.03.2014, 23:09  [ТС]     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #3
Считается неправильно
C++
1
2
3
4
5
6
7
8
9
10
while(a[i] < x) {SravQuick++;i++;}
        while(a[j] > x) {SravQuick++;j--;}
 
        if(i <= j)
        {   swap(a[i], a[j]);
            NazQuick++;
            i++;
            j--;
        }
    }
uburuntu
 Аватар для uburuntu
94 / 94 / 29
Регистрация: 04.10.2012
Сообщений: 188
26.03.2014, 23:14     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #4
parkito, а где у вас объявлены эти переменные?

Сделайте их глобальными и всё будет ок.
parkito
 Аватар для parkito
11 / 11 / 2
Регистрация: 22.03.2010
Сообщений: 685
26.03.2014, 23:16  [ТС]     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #5
uburuntu, В коде программы они глобальные.
uburuntu
 Аватар для uburuntu
94 / 94 / 29
Регистрация: 04.10.2012
Сообщений: 188
26.03.2014, 23:24     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #6
parkito, вангую, что они объявлены не так:
C++
1
2
static int SravQuick = 0;
static int NazQuick = 0;
parkito
 Аватар для parkito
11 / 11 / 2
Регистрация: 22.03.2010
Сообщений: 685
27.03.2014, 15:47  [ТС]     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #7
uburuntu, Да, не так. Однако когда
C++
1
2
static int SravQuick = 0;
static int NazQuick = 0;
ситуация не меняется.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2014, 22:41     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов
Еще ссылки по теме:

Количество произведенных сравнений в Быстрой Сортировке C++
Как найти в этой сортировке количество перестановок и сравнений? C++
Как найти в данной сортировке количество перестановок и сравнений? C++

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

Или воспользуйтесь поиском по форуму:
uburuntu
 Аватар для uburuntu
94 / 94 / 29
Регистрация: 04.10.2012
Сообщений: 188
27.03.2014, 22:41     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов #8
parkito, очень странно. Скиньте код что ли. А с чего вы взяли, что считается неправильно?
Yandex
Объявления
27.03.2014, 22:41     Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов
Ответ Создать тему
Опции темы

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