Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
06.01.2011, 11:51     Рекурсивная сортировка разделением #1
ниже привел код рекурсивной сортировки разделением, но она сортирует нормально, если в массиве представлены только уникальные элементы, а если появляются одинаковые, то зацикливается...
не могу понять в чем дело...
вызов в main Qsort(0, a.size-1); где a - объект класса vector

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
    }
}
Добавлено через 21 час 50 минут
нашел в чем ошибка, нужно добавить в тело if i++; j--;

C++
1
2
3
4
5
6
7
8
if(i < j)
           {
                   T t = array[i];
                         array[i] = array[j];
                         array[j] = t;
                         i++;
                         j--;
           } else return j;
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2011, 11:51     Рекурсивная сортировка разделением
Посмотрите здесь:

Сортировка разделением C++
C++ трабл с разделением программы на файлы или неймспейсы!
C++ Быстрая сортировка с разделением
C++ int to string с разделением на разряды
C++ Рекурсивная сортировка массива.
Осуществить сортировку текстового файла по длине строк циклическим слиянием/разделением C++
Сортировка разделением C++
Умножение матриц с разделением на потоки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 17:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru