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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
#1

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

11.08.2012, 20:30. Просмотров 798. Ответов 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);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2012, 20:30     Алгорим быстрой сортировки
Посмотрите здесь:

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

Иллюстрация быстрой сортировки - C++
Ребят,необходимо написать программу похожую на ту,которая тут http://www.cyberforum.ru/csharp-beginners/thread874724.html Помогите...

Найти ошибку быстрой сортировки - C++
Пытался написать, помогите найти ошибки. Код должен вставит на первое место самое большое четное число из списка и дальше сортировать...

Прогресс выполнения быстрой сортировки - C++
хочу написать простой консольный прогресс бар, отображающий ход выполнения быстрой сортировки, но не могу найти за что &quot;зацепиться&quot; то есть...

Алгоритмом быстрой сортировки строк - C++
Необходимо отсортировать дату,она же char, по возрастанию. void q_sort(Medicament m, int f, int l){ int i = f, j = l; char...

Вывод результата быстрой сортировки - C++
Доброго времени суток, возникла проблема с быстрой сортировкой, не знаю как реализовать вывод отсортированного массива. Сам код: #include...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 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
~ Эврика! ~
1243 / 992 / 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2012, 21:15     Алгорим быстрой сортировки
Еще ссылки по теме:

Вопросы насчёт быстрой сортировки - C++
Здравствуйте. Объясните, пожалуйста. Есть алгоритм быстрой сортировки: Код: int shag=1; void quickSort(int arr, int left, int...

Поиск самой быстрой сортировки - C++
Ищу быструю реализацию быстрого алгоритма сортировки массива для среднего случая на С/С++ под Win32. Остальные параметры не имеют значения....

Сортировка последовательности методом быстрой сортировки - C++
помогите :Написати програму для сортування послідовності 45 37 2 5 9 12 6 4 52 методом швидкого сортування. На кожному кроці виводити...

Метод быстрой сортировки: нужно исправить! - C++
Помогите исправить ошибку. Само задание описано в комментах в программе, но написанная мной функция неверно отсортировывает массив D. Это...


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

Или воспользуйтесь поиском по форуму:
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 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     Алгорим быстрой сортировки
Ответ Создать тему
Опции темы

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