12 / 12 / 3
Регистрация: 27.07.2012
Сообщений: 208
1

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

11.08.2012, 20:30. Показов 1078. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.08.2012, 20:30
Ответы с готовыми решениями:

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

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

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

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

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

Добавлено через 1 минуту
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Чтобы отработала строка 23 и цикл do–while закончился.
Почему бы не сделать условное выражение в while, такое : i < j
0
~ Эврика! ~
1254 / 1003 / 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
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
~ Эврика! ~
1254 / 1003 / 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.08.2012, 21:15

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

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

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

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

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

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


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

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

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