Алгоритм сортировки, быстрый, да бесконечный

[Fanyuus]

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

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

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

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

	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);
}

Внимание, вопрос: почему, когда в двух строчках, отмеченные в начале (!!!), если убрать знак "=", то сортировка уходит куда-то в бесконечность? Как сие дело можно исправить?

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

[Bugrimov]

Вы имеете в виду

(i<=j)

?
Попробуйте в ручную на листе бумаги произвести эту сортировку, думаю некоторые моменты станут понятней.

[Fanyuus]

Bugrimov,

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

и, внутри него есть

if (i<=j) //перестановка элементов массива
{
...
}

забавно, что даже если с if убрать "=", то уже некорректное отображение сортировки.

Воооот... есть идеи "почему так логично"?)

[Smitt&Wesson]

void q_sorta(int *m, int lleft, int rright)
{
int i=left, j=right, mid=m[(a+b)/2];

А это чё у Вас за хрень? left, откуда берётся? Это глабальная переменная? Тогда нахрена int lleft нужен?

[Fanyuus]

Ойй, простите - старая опечатка
*дублированные буквы убрать нужно

[Bugrimov]

Сообщение от Fanyuus

Воооот... есть идеи "почему так логично"?)

В чем вопрос??? Почему так, а не иначе.
Когда я изучал эти сортировки, сначала все проделывал на бумаге, что бы иметь представление что делает программа... И Вам рекомендую.

[Sciv]

сортировка уходит куда-то в бесконечность

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

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

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

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

[Fanyuus]

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

Так, что.то не совсем поняла: последнее - если там i=j, то ИФ -> нет -> нет перестановки.
Или я не правильно говорю?
Хм, нет, всё равно не могу понять, где в условии ошибка.
*попытка номер два - ошибка возникает, когда i и j будут равными, из-за двух ваилов внутри?

[Sciv]

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

Именно. Последствия, знаете ли...

Так, что.то не совсем поняла:

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

попытка номер два - ошибка возникает, когда i и j будут равными, из-за двух ваилов внутри?

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

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

Встречный вопрос - а чего Вам так приспичило от этого "равно" избавляться?

[Bugrimov]

Сообщение от Sciv

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

Встречный вопрос - а чего Вам так приспичило от этого "равно" избавляться?

Золотые слова.... Отзыв обязательно напишу..