VPF::Шаблоны функций, сортировка массивов

Михаил345

Дата 27.10.2014, 18:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 27.10.2014

Репутация: нет
Всего: нет

День добрый, у меня такая задача:

Создайте шаблон функции, выполняющей процедуру слияния
для двух отсортированных по возрастанию входных массивов.
Результатом этой операции должен стать отсортированный по
возрастанию массив, содержащий элементы обоих входных массивов.

имеется в виду алгоритм merge для сортировки, как создать сам шаблон затрудняюсь. Буду признателен за помощь.
Что имеется:

Код


template<class T> void Merge(T const *const A, int const nA,
                             T const *const B, int const nB,
                             T *const C)
{ //Выполнить слияние массива A, содержащего nA элементов,
  //  и массива B, содержащего nB элементов.
  //  Результат записать в массив C.

    int a(0), b(0); //Номера текущих элементов в массивах A и B

    while( a+b < nA+nB ) //Пока остались элементы в массивах
    {
        if( (b>=nB) || ( (a<nA) && (A[a]<=B[b]) ) )
        { //Копирую элемент из массива A
            C[a+b] = A[a];
            ++a;
        } else { //Копирую элемент из массива B
            C[a+b] = B[b];
            ++b;
        }
    }
}

Код


template<class T> void MergeSort(T *const A, int const n)
{ //Отсортировать массив A, содержащий n элементов

    if( n < 2 ) return; //Сортировка не нужна

    if( n == 2 ) //Два элемента проще поменять местами,
    {            //  если нужно, чем делать слияние
        if( A[0] > A[1] ) { T const t(A[0]); A[0]=A[1]; A[1]=t; }
        return;
    }
    
    MergeSort(A    , n/2  ); //Сортируем первую половину
    MergeSort(A+n/2, n-n/2); //Сортируем вторую половину

    T *const B( new T[n] ); //Сюда запишем результат слияния

    Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин

    //Копирование результата слияния в исходный массив:
    for(int i(0); i<n; ++i) A[i]=B[i];

    delete[n] B; //Удаляем временный буфер
}

Cheloveck

Дата 27.10.2014, 19:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1578
Регистрация: 26.7.2008
Где: Тула

Репутация: 5
Всего: 32

http://brainstream-dev.blogspot.ru/2011/01/c-linux.html -- в конце

--------------------

baldina

Дата 27.10.2014, 19:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

Михаил345, у вас условие окончания цикла неправильное и не копируется хвост:
user posted image

Код


int a=0,
     b=0; 
while (a != nA && b != nB) {
  if (A[a] < B[b]) {
     С[a+b]=A[a];
     ++a;
  }
  else {
     С[a+b]=B[b];
     ++b;
  }
}
// остаток
while (a != nA) {
   C[nB+a] = A[a];
   ++a;
}
while (b != nB) {
   C[nA+b] = B[b];
   ++b;
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »