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

  • Автор темы Sermak
  • Дата начала
Статус
Закрыто для дальнейших ответов.
S

Sermak

#1
Помогите пожалста с проблемкой. Нижеследующая прога выполняет рекурсивную сортировку разделением. А проблема в том, что она правильно сортирует только массивы с уникальными элементами (ключами). Если в массиве случаются одинаковые элементы, программа зацикливается. Как исправить? Заранее спасибо.


Код:
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();
}
 

grigsoft

Well-known member
15.11.2005
735
0
#2
Все не изучал, но конструкции типа
Код:
for (j = r; a[j] > x; j--)
с одинаковым успехом могут и падать и циклить. Где проверка на выход за границы массива?
 
S

Sermak

#3
Для: grigsoft
Нет, за границы массива не выходит. Я бы заметил, а циклит она потому, что при двух одинаковых элементах в массиве программа при каждом проходе переставляет местами эти элементы в цикле
Код:
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;			//если элементы равны фактически возвращаем середину
};
и так бесконечно. А как выйти из этого я чегой то не дойду.
 

grigsoft

Well-known member
15.11.2005
735
0
#4
Ты же меняешь только элементы которые больше и меньше среднего, они не могут быть равны, причина в другом. Отлаживай повнимательней.
 
Статус
Закрыто для дальнейших ответов.