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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
parkito
11 / 11 / 2
Регистрация: 22.03.2010
Сообщений: 692
#1

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

26.03.2014, 23:01. Просмотров 2356. Ответов 7
Метки нет (Все метки)

Помогите пожалуйста в алгоритме быстрой сортировки посчитать количество перестановок и сравнений элементов массивов. Не могу понять куда нужно счетчики встроить.
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);
 
    
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2014, 23:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов (C++):

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

Посчитать количество сравнений и перестановок в сортировке выбором - C++
Доброго времени суток, столкнулся с проблемой, не знаю куда поставить счетчики на сравнения и перестановки в сортировке выбором, уже всяко...

Нужно вставить счетчик, чтобы посчитать количество сравнений и перестановок - C++
#include &lt;iostream&gt; #include &lt;ctime&gt; using namespace std; int main() { int arr, a, b, i, size; size = 100; //...

Счетчик сравнений для быстрой сортировки - C++
Добрый вечер. Взял сортировку из википедии void qSort(int arr7, int first, int last) { k = first; l =...

Посчитать количество сравнений элементов массива - C++
Имеется код, сортировка вставками, нужно в этот код всунуть счетчик &quot;количество сравнений элементов массива&quot;. Как это сделать? Простым...

График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки - C++
имеются массивы с размерностью от 1 до 20 с данными не отсортированными,частично отсортированными ,отсортированными в обратную сторону...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
uburuntu
94 / 94 / 29
Регистрация: 04.10.2012
Сообщений: 189
26.03.2014, 23:04 #2
Перестановки - это вызовы swap, а сравнения в вайлах находятся:
C++
1
2
while(a[i] < x) {i++;}
while(a[j] > x) {j--;}
0
parkito
11 / 11 / 2
Регистрация: 22.03.2010
Сообщений: 692
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--;
        }
    }
0
uburuntu
94 / 94 / 29
Регистрация: 04.10.2012
Сообщений: 189
26.03.2014, 23:14 #4
parkito, а где у вас объявлены эти переменные?

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

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

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

Количество сравнений/перестановок в сортировке естественным слиянием - C++
Добрый день ! Никак не могу понять как создать счётчик и куда его вставить , лазил по форумах и не нашел всё равно , помогите , если кто-то...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
27.03.2014, 22:41
Ответ Создать тему
Опции темы

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