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

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

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

Быстрая сортировка, подсчитать количество перестановок элементов массива - C++

29.05.2011, 13:37. Просмотров 955. Ответов 8
Метки нет (Все метки)

Здравствуйте! Никак не могу подсчитать количество перестановок елементов массива в сортировке Хоара
Сделал счетчик value в цикле while, и передаю ето значение в метод. Но когда вызываю метод, независимо от количества елементов массива, это значение равно 0. Может как-нибудь по другому это можна реализовать? Буду очень благодарен.

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
28
29
30
template <class T>
void Kurs <T> :: QuickSort (int from, int to)
{
   value = 0;
   T x, temp;
   int i, j;
 
   if (from >= to) return;
 
   i = from;
   j = to;
 
   x = mas [(from + to) / 2];
   while (i <= j)
   {
      while (mas [i] < x) i++;
      while (mas [j] > x) j--;
 
      if (i <= j)
      {
         temp = mas [i];
         mas [i] = mas [j];
         value++;
         mas[j] = temp;
         i++; j--;
      }
   }
   QuickSort (from, j);
   QuickSort (i, to);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2011, 13:37     Быстрая сортировка, подсчитать количество перестановок элементов массива
Посмотрите здесь:

C++ Поменять местами минимальный и максимальный элемент массива V[25] и подсчитать количество парных элементов массива
Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
Быстрая сортировка: посчитать количество сравнений и обменов C++
C++ Подсчитать Количество перестановок при сортировке массива по возрастанию
C++ Сортировка слиянием: подсчитать количество перестановок
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? C++
Как подсчитать произведенное количество перестановок при быстрой сортировке? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
adico
13 / 13 / 1
Регистрация: 24.02.2011
Сообщений: 64
29.05.2011, 14:30     Быстрая сортировка, подсчитать количество перестановок элементов массива #2
value надо обьявить глобально. Иначе при рекурсивном вызове вы снова обнуляете ее.
Цитата Сообщение от Fiasco Посмотреть сообщение
QuickSort (from, j);
QuickSort (i, to);
Она кстати сортирует?

Добавлено через 2 минуты
я недавно писал, там в зависимости от, какогото параметра выбирается вызов рекурсии.
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
29.05.2011, 14:49  [ТС]     Быстрая сортировка, подсчитать количество перестановок элементов массива #3
Да, сортирует нормально. У меня value обьявляется как private.
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
29.05.2011, 15:18     Быстрая сортировка, подсчитать количество перестановок элементов массива #4
Фокус в том, что при КАЖДОМ рекурсивном входе в самом начале value = 0; Поэтому результат, разный нулю - логично...
Значение value должно сохраняться от вызова к вызову. А это можно сделать с помощью локальной статической переменной.
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
29.05.2011, 19:10  [ТС]     Быстрая сортировка, подсчитать количество перестановок элементов массива #5
Если сделать локальную переменную, и выводить ее значение в блоке сортировки, тогда количество выводов будет равно количеству вызовов рекурсии...
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
29.05.2011, 21:34     Быстрая сортировка, подсчитать количество перестановок элементов массива #6
Fiasco, нет. Ты же в цикле считаешь количество обменов. Вот эту переменную и сделай статической локальной.
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
30.05.2011, 00:22  [ТС]     Быстрая сортировка, подсчитать количество перестановок элементов массива #7
ValeryLaptev, Вы имеете ввиду так:

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
28
29
30
template <class T>
void Kurs <T> :: QuickSort (int from, int to)
{
   static int value = 0;
   T x, temp;
   int i, j;
 
   if (from >= to) return;
 
   i = from;
   j = to;
 
   x = mas [(from + to) / 2];
   while (i <= j)
   {
      while (mas [i] < x) i++;
      while (mas [j] > x) j--;
 
      if (i <= j)
      {
             temp = mas [i];
             mas [i] = mas [j];
             value++;
             mas[j] = temp;
             i++; j--;
      }
   }
   QuickSort (from, j);
   QuickSort (i, to);
}
Если эта переменная локальная, тогда передать в функцию ее уже нельзя а в самом методе сортировки выводить глупо, так как будет выводить столько раз, сколько будет вызываться рекурсия.
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
30.05.2011, 22:14     Быстрая сортировка, подсчитать количество перестановок элементов массива #8
Кто тебе мешает сделать так:
C++
1
2
3
 поле класса += value;    // -- это не количество вызовов, а количество обменов! --
QuickSort (from, j);
   QuickSort (i, to);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2011, 11:04     Быстрая сортировка, подсчитать количество перестановок элементов массива
Еще ссылки по теме:

C++ Быстрая сортировка элементов столбцов двумерного массива, стоящих на четных позициях
C++ Быстрая сортировка массива
Быстрая сортировка, неправильный подсчет количества сравнений и перестановок C++
C++ Быстрая сортировка массива
C++ Быстрая сортировка,количество сравнений

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

Или воспользуйтесь поиском по форуму:
koldun_89
4 / 1 / 0
Регистрация: 09.01.2010
Сообщений: 52
21.06.2011, 11:04     Быстрая сортировка, подсчитать количество перестановок элементов массива #9
помогите пожалуйста сделать счетчик количества перестановок элементов

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
 
#include <stdlib.h>
 
 
 
void quicksort(int *a, int l, int r)
 
{
 
    int i, j, m, t;
 
    i = l;
 
    j = r;
 
    m = (l+r)/2;
 
    do {
 
        while (a[i] < a[m])
 
            i++;
 
        while (a[j] > a[m])
 
            j--;
 
        if (i <= j) {
 
            t = a[i];
 
            a[i] = a[j];
 
            a[j] = t;
 
            i++;
 
            j--;
 
        }
 
    }
 
    while (i < j);
        
 
    if (l < j)
 
        quicksort(a, l, j);
 
    if (i < r)
 
        quicksort(a, i, r);
}
 
 
 
int main()
 
{
 
    int a[10] = {7, 2, 9, 13, 57, 25, 17, 1, 90};
 
    int i;
 
    quicksort (a, 0, 8);
 
    printf ("\nQuicksort:\n");
 
 
    for (i = 0; i <= 8; i++)
 
        printf ("%d\t", a[i]);  
 
 
    return 0;
 
}
очень срочно нужно !!
Yandex
Объявления
21.06.2011, 11:04     Быстрая сортировка, подсчитать количество перестановок элементов массива
Ответ Создать тему
Опции темы

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