Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

11.08.2012, 20:30. Просмотров 812. Ответов 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++
Добрый вечер. Скиньте пожалуйста пример быстрой сортировки массива строк и сортировки массива строк методом выбора. Очень срочно надо,...

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

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

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

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

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

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

Добавлено через 1 минуту
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Чтобы отработала строка 23 и цикл do–while закончился.
Почему бы не сделать условное выражение в while, такое : i < j
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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 строк».
0
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
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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) маленькие массивы сортировать вставками.

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

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

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

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

Алгоритм быстрой сортировки по убыванию - C++
Я нашёл алгоритм быстрой сортировки по возрастанию: int n, a; //n - количество элементов void qs(int* s_arr, int first, int last) ...


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

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

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