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

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

Восстановить пароль Регистрация
 
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
11.08.2012, 20:30     Алгорим быстрой сортировки #1
В одной из тем выложен алгоритм быстрой сортировки. Возник вопрос: если индексы 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);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 20:32     Алгорим быстрой сортировки #2
Чтобы отработала строка 23 и цикл do–while закончился.
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
11.08.2012, 20:37  [ТС]     Алгорим быстрой сортировки #3
Что понимается под устойчивостью метода?

Добавлено через 1 минуту
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Чтобы отработала строка 23 и цикл do–while закончился.
Почему бы не сделать условное выражение в while, такое : i < j
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 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 строк».
bgm313
12 / 12 / 2
Регистрация: 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
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 21:15     Алгорим быстрой сортировки #6
Суть в том, что может случиться так, что i > j ещё до входа в if (в результате тех двух while выше). В этом случае инкременты делать не надо.

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

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

Иначе достаточно уже того, что оно значительно быстрее всяких сортировок обменом выбором.
Yandex
Объявления
11.08.2012, 21:15     Алгорим быстрой сортировки
Ответ Создать тему
Опции темы

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