Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 05.01.2011, 23:26
Пользователь

Отправить личное сообщение для blackbanny Посмотреть профиль Найти все сообщения от blackbanny
 
Регистрация: 05.01.2011
Сообщений: 29

рекурсивная сортировка разделением
ниже привел код рекурсивной сортировки разделением, но она сортирует нормально, если в массиве представлены только уникальные элементы, а если появляются одинаковые, то зацикливается...
не могу понять в чем дело...
вызов в 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;
        }
}
  #2  
Старый 06.01.2011, 08:23
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

сравни с циклом do-while здесь:
http://algolist.ru/sort/quick_sort.php
  #3  
Старый 06.01.2011, 12:32
Пользователь

Отправить личное сообщение для blackbanny Посмотреть профиль Найти все сообщения от blackbanny
 
Регистрация: 05.01.2011
Сообщений: 29

нашел ошибку...
нужно здесь:
Код:
if(i < j)
           {
                   T t = array[i];
                         array[i] = array[j];
                         array[j] = t;
           }
добавить i++; j--; вот так:

Код:
if(i < j)
           {
                   T t = array[i];
                         array[i] = array[j];
                         array[j] = t;
                         i++;
                         j--;
           }
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49