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

Тема в разделе "Общие вопросы по С и С++", создана пользователем Sermak, 18 июн 2006.

Статус темы:
Закрыта.
  1. Sermak

    Sermak Гость

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


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

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    Все не изучал, но конструкции типа
    Код (Text):
    for (j = r; a[j] > x; j--)
    с одинаковым успехом могут и падать и циклить. Где проверка на выход за границы массива?
     
  3. Sermak

    Sermak Гость

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

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    Ты же меняешь только элементы которые больше и меньше среднего, они не могут быть равны, причина в другом. Отлаживай повнимательней.
     
Загрузка...
Похожие Темы - Рекурсивная сортировка разделением
  1. Seriy1994
    Ответов:
    1
    Просмотров:
    1.147
  2. Seriy1994
    Ответов:
    1
    Просмотров:
    1.223
  3. Seriy1994
    Ответов:
    0
    Просмотров:
    1.037
  4. Seriy1994
    Ответов:
    0
    Просмотров:
    1.123
  5. Seriy1994
    Ответов:
    1
    Просмотров:
    1.018
Статус темы:
Закрыта.

Поделиться этой страницей