Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/35: Рейтинг темы: голосов - 35, средняя оценка - 4.86
voral
882 / 590 / 129
Регистрация: 16.03.2008
Сообщений: 2,780
1

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

08.06.2011, 02:10. Просмотров 6527. Ответов 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--;
    }
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2011, 02:10
Ответы с готовыми решениями:

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

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

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

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

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

4
grizlik78
Эксперт С++
2016 / 1497 / 206
Регистрация: 29.05.2011
Сообщений: 3,117
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
882 / 590 / 129
Регистрация: 16.03.2008
Сообщений: 2,780
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
882 / 590 / 129
Регистрация: 16.03.2008
Сообщений: 2,780
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; ...


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

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

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