Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.78
voral
849 / 558 / 113
Регистрация: 16.03.2008
Сообщений: 2,572
#1

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

08.06.2011, 02:10. Просмотров 6338. Ответов 4
Метки нет (Все метки)

Вопрос, скорее академический, по мотивам реализации.
Вот в 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--;
    }

http://www.cyberforum.ru/cpp-beginners/thread1212199.html
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2011, 02:10
Я подобрал для вас темы с готовыми решениями и ответами на вопрос C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) (C++):

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и...

Быстрая сортировка (сортировка методом Хоара)
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные...

Сортировка Хоара / Быстрая сортировка
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void...

Быстрая сортировка Хоара
Быстрая сортировка Хоара (QSort) разбивает массив в ходе сортировки до ...

Быстрая сортировка Хоара без рекурсивных функций
Здравствуйте мне нужно написать быстрою сортировку Хоара но без рекурсивных...

4
grizlik78
Эксперт С++
1982 / 1475 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
08.06.2011, 02:54 #2
Лучший ответ Сообщение было отмечено mik-a-el как решение

Решение

Вряд ли. Тут ещё вопрос, что будет дешевле — пустой обмен один раз или проверка условия много раз. Как бы медленнее не получилось
Тогда уж логичнее вообще вынести эту проверку из цикла.
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--;
    }
  }
Вроде я нигде не погорячился, но всё-равно надо тщательно проверять.
А в сколь-нибудь заметном выигрыше я опять же сомневаюсь. Если не лень — проведи эксперимент
0
voral
849 / 558 / 113
Регистрация: 16.03.2008
Сообщений: 2,572
08.06.2011, 02:58  [ТС] #3
Цитата Сообщение от grizlik78 Посмотреть сообщение
Вряд ли. Тут ещё вопрос, что будет дешевле — пустой обмен один раз или проверка условия много раз. Как бы медленнее не получилось
А. да. точно. что-то я тормознул...
0
AlvinMax
0 / 0 / 0
Регистрация: 05.01.2013
Сообщений: 16
06.01.2013, 23:06 #4
Можно и встроенной функцией sort отсортировать!
0
voral
849 / 558 / 113
Регистрация: 16.03.2008
Сообщений: 2,572
08.01.2013, 13:54  [ТС] #5
Конечно можно.....
Только не во всех случаях это возможно и не во всех эффективно.

В данном конкретном топике вопрос был по алгоритму, а не о том "как отсортировать"
0
08.01.2013, 13:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2013, 13:54
Привет! Вот еще темы с решениями:

Сортировка расчёской и быстрая сортировка
В файле in.txt записана последовательность целых чисел. Заданными методами...

сортировка хоара
void QuickSort(int* const a, int low, int N) { int i = low, j = N; ...

Сортировка Хоара
помогите правильно вставить счетчик шагов. Насколько я понял, функция сама себя...

Сортировка методом Хоара
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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