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

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.78
voral
345 / 325 / 46
Регистрация: 16.03.2008
Сообщений: 1,694
08.06.2011, 02:10     C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) #1
Вопрос, скорее академический, по мотивам реализации.
Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий фрагмент:
C++
1
2
3
4
5
6
7
8
9
do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );
Т.е. у нас бывает ситуация когда i=j ( я так понимаю - как раз центральный элемент). При этом мы так же прогоняем через temp.
Т.е. три лишних операции присвоения. Ускорится ли выполнение (понимаю что разница мала, но все же если немного изменить)
C++
1
2
3
4
5
if (i <= j)
    {
      if (i < j) {temp = a[i]; a[i] = a[j]; a[j] = temp;};
      i++; j--;
    }
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2011, 02:10     C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Посмотрите здесь:

Быстрая сортировка Хоара C++
Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
C++ Быстрая сортировка Хоара без рекурсивных функций
C++ Сортировка Хоара
C++ сортировка хоара
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
08.06.2011, 02:54     C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вряд ли. Тут ещё вопрос, что будет дешевле — пустой обмен один раз или проверка условия много раз. Как бы медленнее не получилось
Тогда уж логичнее вообще вынести эту проверку из цикла.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i < j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i < j );
 
  if (i == j) {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i == j) {
      i++; j--;
    }
  }
Вроде я нигде не погорячился, но всё-равно надо тщательно проверять.
А в сколь-нибудь заметном выигрыше я опять же сомневаюсь. Если не лень — проведи эксперимент
voral
345 / 325 / 46
Регистрация: 16.03.2008
Сообщений: 1,694
08.06.2011, 02:58  [ТС]     C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) #3
Цитата Сообщение от grizlik78 Посмотреть сообщение
Вряд ли. Тут ещё вопрос, что будет дешевле — пустой обмен один раз или проверка условия много раз. Как бы медленнее не получилось
А. да. точно. что-то я тормознул...
AlvinMax
 Аватар для AlvinMax
0 / 0 / 0
Регистрация: 05.01.2013
Сообщений: 16
06.01.2013, 23:06     C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) #4
Можно и встроенной функцией sort отсортировать!
voral
345 / 325 / 46
Регистрация: 16.03.2008
Сообщений: 1,694
08.01.2013, 13:54  [ТС]     C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) #5
Конечно можно.....
Только не во всех случаях это возможно и не во всех эффективно.

В данном конкретном топике вопрос был по алгоритму, а не о том "как отсортировать"
Yandex
Объявления
08.01.2013, 13:54     C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Ответ Создать тему
Опции темы

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