рекурсивная сортировка разделением

[blackbanny]

ниже привел код рекурсивной сортировки разделением, но она сортирует нормально, если в массиве представлены только уникальные элементы, а если появляются одинаковые, то зацикливается...
не могу понять в чем дело...
вызов в main Qsort(0, a.size-1); где a - объект класса vector

template <class T> void vector<T>::Qsort(int l, int r)
{
   if(l < r)
   {
	   int k = Partition(l, r);
	   Qsort(l, k);
	   Qsort(k+1, r);
   }
}

template <class T> int vector<T>::Partition(int l, int r)
{
	T x = array[(l+r)/2];  
	int i = l;
	int j = r;
	while(1)
	{
	   while(array[j] > x)
	   {
		   j--;
	   }
	   while(array[i] < x)
	   {
		   i++;
	   }
	   if(i < j)
	   {
		   T t = array[i];
			 array[i] = array[j];
			 array[j] = t;
	   } else return j;
	}
}

[Gongled]

Полагаю, стоит в одном из циклов while выставить нестрогое условие.

В алгоритм не вникал.

[blackbanny]

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

Полагаю, стоит в одном из циклов while выставить нестрогое условие.

В алгоритм не вникал.

нет, дело не в этом...
если выставить нестрогие, то прога вообще падает...

[xPAL]

Долго искал...
Думаю, что после этого

 array[j] = t;

напрашивается

i++;
j--;

. У меня (в упрощенном варианте) работает с этой строчкой.

[Flyasd1]

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

Полагаю, стоит в одном из циклов while выставить нестрогое условие.

В алгоритм не вникал.

Он прав так как если у вас в переменной х окажется элемент которому найдется равный в массиве то у вас в определенный момент ни одна из переменных i и j не будут изменятся и получается зацикливание