Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 21.03.2013, 21:41   #1
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию Алгоритм сортировки, быстрый, да бесконечный

Добрый вечер, уважаемые Коллеги!

И всё бы ничего, да вот покоя не даёт такое слово, как "курсовая работа".

Собственно, дело всё в быстрой сортировке.

Кусок кода, который верно работает (т.е., сортирует):



Код:
	void q_sorta(int *m, int left, int right)
{
int i=left, j=right, mid=m[(a+b)/2];
	//(!!!)
        while (i<=j)
	{
		while (m[i]<mid)
			i++;
		while (m[j]>mid)
			j--;
	//(!!!)
	if (i<=j)
		{
			int s;
			s=m[i];
			m[i]=m[j];
			m[j]=s;			
			i++;
			j--;
		}
	}

	if (left<j)
	q_sorta(m,left,j);
	if (i<right)
q_sorta(m,i,right);
}
Внимание, вопрос: почему, когда в двух строчках, отмеченные в начале (!!!), если убрать знак "=", то сортировка уходит куда-то в бесконечность? Как сие дело можно исправить?

Буду очень благодарна, если вы мне сможете помочь!

Последний раз редактировалось Fanyuus; 22.03.2013 в 08:53. Причина: ошибка в коде - имена переменных
Fanyuus вне форума Ответить с цитированием
Старый 21.03.2013, 21:48   #2
Bugrimov
C/C++, Java
Участник клуба
 
Аватар для Bugrimov
 
Регистрация: 28.03.2012
Сообщений: 1,680
По умолчанию

Вы имеете в виду
Код:
(i<=j)
?
Попробуйте в ручную на листе бумаги произвести эту сортировку, думаю некоторые моменты станут понятней.
"Keep it simple" - придерживайтесь простоты!
Уильям Оккам - "Не следует множить сущее без необходимости"
Сложность - враг простоты и удобства!
Bugrimov вне форума Ответить с цитированием
Старый 21.03.2013, 21:52   #3
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию

Bugrimov,

Код:
while (i<=j)
{
//нахождение индексов, для перестановки+ перестановка
....
}
и, внутри него есть

Код:
if (i<=j) //перестановка элементов массива
{
...
}
забавно, что даже если с if убрать "=", то уже некорректное отображение сортировки.

Воооот... есть идеи "почему так логично"?)
Fanyuus вне форума Ответить с цитированием
Старый 22.03.2013, 00:01   #4
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Цитата:
void q_sorta(int *m, int lleft, int rright)
{
int i=left, j=right, mid=m[(a+b)/2];
А это чё у Вас за хрень? left, откуда берётся? Это глабальная переменная? Тогда нахрена int lleft нужен?
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 22.03.2013, 08:51   #5
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию

Ойй, простите - старая опечатка
*дублированные буквы убрать нужно
Fanyuus вне форума Ответить с цитированием
Старый 22.03.2013, 09:12   #6
Bugrimov
C/C++, Java
Участник клуба
 
Аватар для Bugrimov
 
Регистрация: 28.03.2012
Сообщений: 1,680
По умолчанию

Цитата:
Сообщение от Fanyuus Посмотреть сообщение
Воооот... есть идеи "почему так логично"?)
В чем вопрос??? Почему так, а не иначе.
Когда я изучал эти сортировки, сначала все проделывал на бумаге, что бы иметь представление что делает программа... И Вам рекомендую.
"Keep it simple" - придерживайтесь простоты!
Уильям Оккам - "Не следует множить сущее без необходимости"
Сложность - враг простоты и удобства!
Bugrimov вне форума Ответить с цитированием
Старый 22.03.2013, 09:19   #7
Sciv
Старожил
 
Аватар для Sciv
 
Регистрация: 16.05.2012
Сообщений: 3,211
По умолчанию

Цитата:
сортировка уходит куда-то в бесконечность
Непонятно. Можете проиллюстрировать? Бесконечный цикл - это понятно. А бесконечная сортировка - что это?

Хотя... Я Вам сам проиллюстрирую:

Массив делится пополам (mid), счетчики идут слева (i) и справа (j). Если убрать "=" из условия цикла, то по достижении середины массива i перейдет в правую половину, а j - в левую - и только тогда цикл прекратится, так как условие i<j не выполнится.

А следующее условие if i<=j в таком случае вообще не выполняется. И наоборот - в момент остановки цикла i=j, а вы из условие это самое "=" убираете - верно ли в таком случае if i<j?
Начал решать проблему с помощью регулярных выражений. Теперь решаю две проблемы...

Последний раз редактировалось Sciv; 22.03.2013 в 09:24.
Sciv вне форума Ответить с цитированием
Старый 22.03.2013, 09:39   #8
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию

Sciv, выходит, от этого равно не избавиться просто так?

Так, что.то не совсем поняла: последнее - если там i=j, то ИФ -> нет -> нет перестановки.
Или я не правильно говорю?
Хм, нет, всё равно не могу понять, где в условии ошибка.
*попытка номер два - ошибка возникает, когда i и j будут равными, из-за двух ваилов внутри?
Fanyuus вне форума Ответить с цитированием
Старый 22.03.2013, 09:55   #9
Sciv
Старожил
 
Аватар для Sciv
 
Регистрация: 16.05.2012
Сообщений: 3,211
По умолчанию

Цитата:
Sciv, выходит, от этого равно не избавиться просто так?
Именно. Последствия, знаете ли...

Цитата:
Так, что.то не совсем поняла:
Кратко все сводится к следующему: когда убираете равно в while или в if (или в обоих сразу) - не срабатывает условие if. Вот тогда как раз и нет перестановки.

Цитата:
попытка номер два - ошибка возникает, когда i и j будут равными, из-за двух ваилов внутри?
Два while внутри всего лишь смещают счетчики к середине массива, не более. Ошибка возникает, когда i=j (это равенство - так и должно быть), но это условие отсутствует в while и в if (а вот так быть не должно).

Вспомните свой вопрос - почему все глючит, когда убираем равно? Следовательно, как раз при условиях <= все работает правильно.

Встречный вопрос - а чего Вам так приспичило от этого "равно" избавляться?
Начал решать проблему с помощью регулярных выражений. Теперь решаю две проблемы...
Sciv вне форума Ответить с цитированием
Старый 22.03.2013, 10:20   #10
Bugrimov
C/C++, Java
Участник клуба
 
Аватар для Bugrimov
 
Регистрация: 28.03.2012
Сообщений: 1,680
По умолчанию

Цитата:
Сообщение от Sciv Посмотреть сообщение
Вспомните свой вопрос - почему все глючит, когда убираем равно? Следовательно, как раз при условиях <= все работает правильно.

Встречный вопрос - а чего Вам так приспичило от этого "равно" избавляться?
Золотые слова.... Отзыв обязательно напишу..
"Keep it simple" - придерживайтесь простоты!
Уильям Оккам - "Не следует множить сущее без необходимости"
Сложность - враг простоты и удобства!
Bugrimov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм сортировки BarsRus Помощь студентам 3 03.06.2010 16:11
Самый быстрый вид сортировки массива Warnes Свободное общение 42 06.12.2009 16:02
самый быстрый метод сортировки, который расположит в порядке возврастания 50.000 чисел типа real Rusl92 Помощь студентам 8 21.11.2009 20:50
Быстрый алгоритм для вычисления синуса RIO Помощь студентам 10 17.12.2007 14:33
Предложите самый быстрый алгоритм! Gambler Общие вопросы Delphi 6 26.12.2006 22:44