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

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

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

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

рекурсивная сортировка слиянием
проблема с рекурсивной сортировкой слиянием, ума не приложу в чем дело...

Код:
template <class T> void vector<T>::Start_Merge_Sort()
{
   T* arraytemp;                 //вспомогательный массив
   arraytemp = new T[size];
   Merge_Sort(0, size-1, arraytemp);
   delete[] arraytemp;
  
}
//рекурсивная сортировка слиянием
template <class T> void vector<T>::Merge_Sort(int l, int r, T *arraytemp)
{
  if(r <= l) return;

  int m = (l + r)/2;
  Merge_Sort(l, m, arraytemp);
  Merge_Sort(m+1, r, arraytemp);
  Merge(l, r, m, arraytemp);
}
//вспомогательная функция Merge
template <class T> void vector<T>::Merge(int l, int r, int m, T *arraytemp)
{
int i, j;

   for(i = m + 1; i >= l + 1; i--)
   {
	   arraytemp[i-1] = array[i-1];
   }
   for(j = m; j < r - 1; j++)
   {
	   arraytemp[r+m-j] = array[j+1];
   }
   for(int k = l; k < r; k++)
   {
	   if(arraytemp[j] <= arraytemp[i])
	   {
		   array[k] = arraytemp[j];
		   j = j - 1;
	   }else
	   {
		   array[k] = arraytemp[i];
		   i = i + 1;
	   }

   }
}
  #2  
Старый 06.01.2011, 13:01
Пользователь

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

псевдокод брал отсюда
  #3  
Старый 06.01.2011, 13:13
гocть

 
Сообщений: n/a

телепатов здесь нет

какая проблема?
  #4  
Старый 06.01.2011, 13:37
Пользователь

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

Сообщение от гocть Посмотреть сообщение
телепатов здесь нет

какая проблема?
пардон, забыл написать проблему...
вообщем сортирует как то не правильно..
допустим три раза подряд генерирую случайные числа и пишу в массив, а потом сортирую и вот что выдает:

1-й раз:
до сортировки: 95 3 3 54 13 72
после сортировки: 3 54 54 3 95 72(здесь 13 куда то пропала)

2-й раз:
до сортировки: 51 54 16 62 53 10
после сортировки: 51 54 16 62 62 10(здесь 53 куда то пропала)

3-й раз:
до сортировки: 74 0 1 86 95 95
после сортировки: 0 74 1 86 95 95

он вроде как сортирует парно, но потом отсортированные пары не сортирует или что, ниче понять не могу...
  #5  
Старый 06.01.2011, 17:40
MBo MBo вне форума
Местный

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

При слиянии нужно учитывать то, что один из подмассивов может закончиться раньше.
  #6  
Старый 06.01.2011, 21:00
Пользователь

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

MBo,а можешь указать в коде ошибку?
  #7  
Старый 06.01.2011, 21:07
гocть

 
Сообщений: n/a

здесь:
Цитата:
Код:
   for(int k = l; k < r; k++)
   {
	   if(arraytemp[j] <= arraytemp[i])
	   {
		   array[k] = arraytemp[j];
		   j = j - 1;
	   }else
	   {
		   array[k] = arraytemp[i];
		   i = i + 1;
	   }

   }
  #8  
Старый 06.01.2011, 23:23
Пользователь

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

Сообщение от MBo Посмотреть сообщение
При слиянии нужно учитывать то, что один из подмассивов может закончиться раньше.
можете подробнее пояснить? что значит может закончиться раньше?
  #9  
Старый 06.01.2011, 23:39
гocть

 
Сообщений: n/a

j у тебя может стать меньше m, или i больше m
отсюда проблемы особенно когда размер массива 1-2 элемента
  #10  
Старый 07.01.2011, 19:43
Пользователь

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

Сообщение от гocть Посмотреть сообщение
j у тебя может стать меньше m, или i больше m
отсюда проблемы особенно когда размер массива 1-2 элемента
т.е. надо надо написать:
Код:
   if(j < m || i > m) return;
   for(int k = l; k < r; k++)
   {
	   if(arraytemp[j] <= arraytemp[i])
	   {
		   array[k] = arraytemp[j];
		   j = j - 1;
	   }else
	   {
		   array[k] = arraytemp[i];
		   i = i + 1;
	   }

   }
но от этого ничего не меняется...
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
рекурсивная сортировка разделением blackbanny Сортировка и поиск 2 06.01.2011 12:32
Ошибка в коде к статье по сортировке слиянием. Семён[гость] Замечания о работе сайта 0 23.05.2010 18:55
Сортировка слиянием гость Сортировка и поиск 7 29.01.2010 04:29
Внешняя сортировка прямым слиянием OKSI55 Сортировка и поиск 0 22.03.2009 13:31
Помогите реализовать сортировку естественным двухпутевым слиянием на С++ Witcher Сортировка и поиск 9 19.06.2008 14:38