Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
bgm313
12 / 12 / 3
Регистрация: 27.07.2012
Сообщений: 208
#1

Алгорим быстрой сортировки - C++

11.08.2012, 20:30. Просмотров 836. Ответов 5
Метки нет (Все метки)

В одной из тем выложен алгоритм быстрой сортировки. Возник вопрос: если индексы i и j указывают на один элемент зачем нужен обмен?

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
void quick(char *items, int count)
{
  qs(items, 0, count-1);
}
 
void qs(char *items, int left, int right)
{
  register int i, j;
  char x, y;
 
  i = left; j = right;
  x = items[(left+right)/2];
 
  do {
    while((items[i] < x) && (i < right)) i++;
    while((x < items[j]) && (j > left)) j--;
 
    if(i <= j) {
      y = items[i];
      items[i] = items[j];
      items[j] = y;
      i++; j--;
    }
  } while(i <= j);
 
  if(left < j) qs(items, left, j);
  if(i < right) qs(items, i, right);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2012, 20:30
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгорим быстрой сортировки (C++):

Пример быстрой сортировки массива строк и сортировки методом выбора
Добрый вечер. Скиньте пожалуйста пример быстрой сортировки массива строк и...

Тонкости быстрой сортировки
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку...

Визуализатор быстрой сортировки
Добрый день! Нужно написать программу, которая иллюстрирует работу быстрой...

Алгоритм Быстрой Сортировки на C++
Можно ли этот алгоритм использовать для последовательности чисел? Просто в...

Не алгоритм быстрой сортировки
Просто как подключить эту функцию Не работаеееет #include&lt;iostream&gt;...

Метод быстрой сортировки
Доброго времени суток, форумчане. Вчера проходили метод быстрой сортировки....

5
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 20:32 #2
Чтобы отработала строка 23 и цикл do–while закончился.
0
bgm313
12 / 12 / 3
Регистрация: 27.07.2012
Сообщений: 208
11.08.2012, 20:37  [ТС] #3
Что понимается под устойчивостью метода?

Добавлено через 1 минуту
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Чтобы отработала строка 23 и цикл do–while закончился.
Почему бы не сделать условное выражение в while, такое : i < j
0
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 20:48 #4
Цитата Сообщение от bgm313 Посмотреть сообщение
Что понимается под устойчивостью метода?
Устойчивые методы сортировки сохраняют относительный порядок равных элементов. К примеру, при сортировке массива
[b, D, L, a, U, S, y, r, A, s]
по алфавиту, но не по регистру (то есть A == a), устойчивый метод всегда вернёт
[a, A, b, D, L, r, S, s, U, y]
«Равные» буквы a, A, s, S следуют в точно таком же порядке, как в исходом массиве. При использовании неустойчивого алгоритма эти буквы могут идти в другом порядке, например, так:
[a, A, b, D, L, r, s, S, U, y]

Цитата Сообщение от bgm313 Посмотреть сообщение
Почему бы не сделать условное выражение в while, такое : i < j
Потому что надо, чтобы после выхода из него i > j, а не !(i < j) == (i >= j) [для того, чтобы рекурсивные вызовы не подрались за общий центральный элемент].
А такой хитрохак позволяет сэкономить пару строк кода и кидать понты «мой квиксорт укладывается в 20 строк».
0
bgm313
12 / 12 / 3
Регистрация: 27.07.2012
Сообщений: 208
11.08.2012, 20:54  [ТС] #5
Цитата Сообщение от
Потому что [I
надо[/I], чтобы после выхода из него i > j, а не !(i < j) == (i >= j). А такой хитрохак позволяет сэкономить пару строк кода и кидать понты «мой квиксорт укладывается в 20 строк».
Ну тогда смотрите можно рассмотреть 2 ситуации:
1)Действовать так, как в описанном выше алгоритме
2)Не тратить время в пустую и не обменивать элементы, сделать условие i < j и сразу после выхода сделать инкремент и декремент этих величин.
Как лучше действовать?

Добавлено через 1 минуту
Количество строк увеличится на 1
0
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 21:15 #6
Суть в том, что может случиться так, что i > j ещё до входа в if (в результате тех двух while выше). В этом случае инкременты делать не надо.

Дело в том, что этот лишний обмен выполняется один раз. А проверка на i == j, чтобы избежать обмена, выполняется на каждой итерации. В итоге для больших массивов может быть выгоднее сделать один лишний обмен, но не делать много лишних проверок.

Добавлено через 6 минут
И если волноваться об эффективности, то тут надо 1) избавиться от половины рекурсий, 2) выбирать вот этот индекс (left+right)/2 тщательнее, 3) маленькие массивы сортировать вставками.

Иначе достаточно уже того, что оно значительно быстрее всяких сортировок обменом выбором.
1
11.08.2012, 21:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2012, 21:15
Привет! Вот еще темы с решениями:

Алгоритм быстрой сортировки
Написать программу, реализующую алгоритм быстрой сортировки(рекурсивный) для...

Визуализация быстрой сортировки
Ребят,может кто помочь с визуальной сортировкой массива.. Нужна быстрая...

Иллюстрация быстрой сортировки
Ребят,необходимо написать программу похожую на ту,которая тут...

Поиск самой быстрой сортировки
Ищу быструю реализацию быстрого алгоритма сортировки массива для среднего...


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

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

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