ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Быстрая сортировка. Число перестановок
5 сообщений из 5, страница 1 из 1
Быстрая сортировка. Число перестановок
    #38003427
kab18
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kab18
Гость
Пытаюсь реализовать подсчет колличества перестановок в методе быстрой сортировки. Переманная-счетчик kolvo, начальное значение которой 0 присвоено в основном блоке программы. Очень смущает малое значение возвращаемое функцией(1-2 перестановки на 3-5 строк). Прошу проверить правильность реализации подсчета.
Код: plaintext
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.
int quickSortR(int* i3,int i1,char*** string2,int kolvo) {
// На входе - массив i3[], i1 - его последний элемент.
  int number = 0, j = i1, temp, p;// поставить указатели на исходные места
  char*** string3;
  string3=new char**[i1];
  for (number=0; number<=i1; number++)
  {
  string3[number]=new char*[256];
  }
  number=0;
  p = i3[ i1>>1 ];// центральный элемент

  // процедура разделения
  do {
    while ( i3[number] < p ) number++;
    while ( i3[j] > p ) j--;

    if (number <= j) {
      temp = i3[number]; string3[number]=string2[number];
      i3[number] = i3[j]; string2[number]=string2[j]; kolvo++;
      i3[j] = temp; string2[j]=string3[number];
      number++; j--;
    }
  } while ( number<=j );

  // рекурсивные вызовы, если есть, что сортировать
  if ( j > 0 ) quickSortR(i3,j,string2,kolvo);
  if ( i1 > number ) quickSortR(i3+number,i1-number,string2+number,kolvo);
  delete[]string3;
  return(kolvo);
}
...
Рейтинг: 0 / 0
18.10.2012, 00:41
| Ответить | Цитировать | Написать  
Быстрая сортировка. Число перестановок
    #38003446
kab18
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kab18
Гость
...
Рейтинг: 0 / 0
18.10.2012, 01:07
| Ответить | Цитировать | Написать  
Быстрая сортировка. Число перестановок
    #38003448
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
kab18,

Подсчет - неверный, причем дважды.
1) Кол-во перестановок подсчитанное и возвращаемое внутренними рекурсивными вызовами игнорируется и не учитывается в вызвающем коде
2) Зачем-то текущий счетчик передается во внутренние вызовы в качестве начального.

Если исправить п.1 то п.2 приведет к дублированию.

Правильно - перенести kolvo из агрументов в локальные переменные с начальным значением 0.
Подсчитать кол-во на текущем уровне вложенности.
А при вызове вложенных веток рекурсии прибавлять их результат к счетчику.
И потом все вернуть.


Второй вариант - аргумент kolvo сделать ссылкой (или указателем) и каждый вызов в нем будет подсчитывать свои перестановки.
При этом естественно уже ничего складывать и возвращать не надо.


ЗЫ. Сам алгоритм сортировки не смотрел, но сразу скажу - в quicksort нигде выделение памяти не требуется, он работает с тем массивом что ему передают на вход.
Так что все эти new, да еще и в цикле, и указатели *** выглядят страшновато :)
...
Рейтинг: 0 / 0
18.10.2012, 01:09
| Ответить | Цитировать | Написать  
Быстрая сортировка. Число перестановок
    #38003457
kab18
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kab18
Гость
Я не совсем понял то, что вы написали на счет уровней вложенностей и веток рекурсии но попытался исправить:
Код: plaintext
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.
int quickSortR(int* i3,int i1,char*** string2) {
// На входе - массив i3[], i1 - его последний элемент.
  int number,j=i1,temp,p,kolvo;// поставить указатели на исходные места
  kolvo=0;
  char*** string3;
  string3=new char**[i1];
  for (number=0; number<=i1; number++)
  {
  string3[number]=new char*[256];
  }
  number=0;
  p = i3[ i1>>1 ];// центральный элемент

  // процедура разделения
  do {
    while ( i3[number] < p ) number++;
    while ( i3[j] > p ) j--;

    if (number <= j) {
      temp = i3[number]; string3[number]=string2[number];
      i3[number] = i3[j]; string2[number]=string2[j]; kolvo++;
      i3[j] = temp; string2[j]=string3[number];
      number++; j--;
    }
  } while ( number<=j );

  // рекурсивные вызовы, если есть, что сортировать
  if ( j > 0 )
  {
  quickSortR(i3,j,string2);
  kolvo++;
  }
  if ( i1 > number )
  {
  quickSortR(i3+number,i1-number,string2+number);
  kolvo++;
  }
  delete[]string3;
  return(kolvo);
}
...
Рейтинг: 0 / 0
18.10.2012, 01:35
| Ответить | Цитировать | Написать  
Быстрая сортировка. Число перестановок
    #38003473
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
kab18,

Вместо
Код: plaintext
1.
2.
  quickSortR(...);
  kolvo++;


должно быть
Код: plaintext
1.
  kolvo += quickSortR(...);
...
Рейтинг: 0 / 0
18.10.2012, 02:02
| Ответить | Цитировать | Написать  
5 сообщений из 5, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Быстрая сортировка. Число перестановок
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]