Помогите пожалста с проблемкой. Нижеследующая прога выполняет рекурсивную сортировку разделением. А проблема в том, что она правильно сортирует только массивы с уникальными элементами (ключами). Если в массиве случаются одинаковые элементы, программа зацикливается. Как исправить? Заранее спасибо.
Код:
int Partition (int a[], int l, int r); // l - левая граница массива r - правая граница
void RekursRasdelSort (int a[], int l, int r) // рекурсивная сортировка разделением
{
if (l >= r) return; // если правая граница равна левой (меньше она быть не может по моему)
int k;
if (l < r) k = Partition (a, l, r); // ищем середину массива a[]
RekursRasdelSort(a, l, k); // рекурсия для левого подмассива
RekursRasdelSort(a, k+1, r); // рекурсия для правого подмассива
}
//-----------------------------------------------------------------------------------
int Partition (int a[], int l, int r) // выбирает середину массива (ПОДМАССИВА)
{
int x = a[(l+r)/2]; //среднее значение ключа (элемента массива
int i = l;
int j = r;
int temp;
while (true)
{
for (j = r; a[j] > x; j--)
{} // ищем в правом подмассиве элемент меньший среднего
for (i = l; a[i] < x; i++)
{} // ищем в левом подмассиве элнмнгт больший среднего
if (i < j) // если эти элементы не равны
{
if (a[j] == a[i]) return j; // эту инструкцию я написал в бешенстве
temp = a[i]; // то меняем их местами
a[i] = a[j]; //
a[j] = temp; //
}
else return j; //если элементы равны фактически возвращаем середину
};
return x; // эта инструкция не нужна (стоит для порядка)
}
///////////////////////////////////////
int main ()
{
const int size = 5;
int mas[size];
for (int i = 0; i < size; i++) mas[i]=rand()%10; // заполняем массив
for (int i = 0; i < size; i++) cout<<mas[i]<<" "; // вывод на экран
RekursRasdelSort (mas, 0, size); // пытаемся сортировать
for (int i = 0; i < size; i++) cout<<mas[i]<<" "; // вывод на экран
getch();
}