Создать шаблон функции, выполняющий сортировку слиянием (Метод Фон Неймана) в массиве

@Юленька · Регистрация: 16.12.2007

Author24 — интернет-сервис помощи студентам

Создать шаблон функции, выполгяющий сортировку слиянием (Метод Фон Неймана) в массиве. Протестировать шаблон для массивов с элементами различных типов: int, float, char.

Заранее спасибо...

@Lord_Voodoo · 16.12.2007, 11:48

а можно озвучить сей метод... а то я про такой даже на слышал...

@Юленька · 16.12.2007, 11:56 **[ТС]**

Метод фон Неймана:
Упорядочить пары соседних элементов массива а (а0 и а1, а2 и а3 и т.д.) и перенести их во вспомогательный массив b. Затем взять по две соседние пары из b и, слив их в упорядоченные четверки, снова записать в а; затем каждые две четверки из b слить в упорядоченные восьмерки и переписать в а и т.д. Упорядоченный массив должен оказаться в массиве а.

В этом алгоритме массивы упорядочиваются по возрастанию.

Помогите пожалуйста...

@Lord_Voodoo · 16.12.2007, 13:33

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

@Юленька · 16.12.2007, 19:26 **[ТС]**

Сообщение от WooDooMan666

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

Если я не сдам эту задачку, то я не получу зачёт
Заранее тебе спасибо.

@Lord_Voodoo · 17.12.2007, 13:43

не уверен, что до конца осилил эту сортировку, но сырцы вроде бы рабочие:

Код

void Sort(int* a, int len){
  int tmp = 0;
  for(int i = 0; i < len; i++)
    for(int j = i + 1; j < len; j++){
      if(a[i] > a[j]){
        tmp = a[j];
        a[j] = a[i];
        a[i] = tmp;
      }
  }
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
    int* arr1 = new int[30];
    int* arr2;
    randomize();
    for(int j = 0; j < 30; j++){
      arr1[j] = random(255);
    }
    for(int i = 0; i < 30; i++) std::cout<<arr1[i]<<" ";
    std::cout<<"\n";
    int n = 0, k = 0, ni = 0, ii = 0, r = 0;
    for(int i = 2; i < 30; i *= 2){
      arr2 = new int[i];
      for(k = 0; k < 30 - i; k += i){
        ii = 0;
        for(int j = k; j < k + i; j++){
          arr2[ii] = arr1[j];
          ii++;
        }
        Sort(arr2, i);
        ii = 0;
        for(int j = k; j < k + i; j++){
          arr1[j] = arr2[ii];
          ii++;
        }
      }
      delete arr2;
      for(int j = k; j < 30; j++){
        arr2[ii] = arr1[j];
        ii++;
      }
      Sort(arr2, i);
      ii = 0;
      for(int j = k; j < 30; j++){
        arr1[j] = arr2[ii];
        ii++;
      }
      for(int i = 1; i < 30; i++) std::cout<<arr1[i]<<" ";
      std::cout<<"\n";
    }
    Sort(arr1, 30);
    for(int i = 1; i < 30; i++) std::cout<<arr1[i]<<" ";
    std::cout<<"\n";
    getch();
    return 0;
}
//---------------------------------------------------------------------------

@Ai · 27.05.2009, 17:53

Это не сортировка слиянием, а обычная сортировка методом пузырька , не вводи людей в заблуждение

Добавлено через 26 минут 20 секунд
Хотя я уже не помогу Юленьке, зато другому кому-то пригодится
Вот исходник на Visual C++

C++

#include <iostream>
#include <conio.h>
using namespace std;
template <class T>
T* merge(T *m1, T* m2, int l1, int l2){
    T* ret = new T[l1+l2];
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (l1 && l2){
        if (*m1 < *m2){
           ret[n] = *m1;
           m1++; l1--;}
        else {
           ret[n] = *m2;
           m2++; l2--;}
       n++;}
    // Если закончился первый массив
    if (l1 == 0){
        for (int i=0; i<l2; i++){
            ret[n++] = *m2++;}}
    // Если закончился второй массив
    else {
        for (int i=0; i<l1; i++){
           ret[n++] = *m1++;}}
    return ret;}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len){
    int n=1, l, ost;
    T * mas1;
    while (n<len){
        l=0;
        while (l<len){
           if (l+n >= len) break;
           ost = (l+n*2>len) ? (len-(l+n)) : n;
           mas1 = merge(mas+l, mas+l+n, n, ost);
           for (int i=0; i<n+ost; i++) mas[l+i] = mas1[i];
           delete [] mas1;
           l+=n*2;}
       n*=2;
}}
 
int main()
{
    float a[128];int dl;
    cout<<"Vvedite coli4estvo 4lenov v massive\n";
    cin>>dl;
    cout<<"Vvedite massiv\n";
    for(int i=0;i<dl;i++)
    {    cin>>a[i];}
    
    mergeSort(a, dl);
    for(int i=0;i<dl;i++)
        cout<<" "<<a[i];
    getch();
}

@Ain · 22.12.2009, 07:31

Ai,Спасибо большое, Вы меня просто выручили сортровкой слиянием!

@Demonhunterus · 10.12.2010, 16:14

C++

template <class T>
void mergeSort(T * mas, int len){
    int n=1, l, ost;
    T * mas1;
    while (n<len){
        l=0;
        while (l<len){
           if (l+n >= len) break;
           ost = (l+n*2>len) ? (len-(l+n)) : n;
           mas1 = merge(mas+l, mas+l+n, n, ost);
           for (int i=0; i<n+ost; i++) mas[l+i] = mas1[i];
           delete [] mas1;
           l+=n*2;}
       n*=2;
}}

Подскажите,пожалуйста,кто-нибудь,что здесь означают и за что отвечают переменные n,l,ost и len.Заранее благодарю.

@Юленька 0 / 0 / 0 Регистрация: 16.12.2007 Сообщений: 4
		1
	Создать шаблон функции, выполняющий сортировку слиянием (Метод Фон Неймана) в массиве 16.12.2007, 11:32. Показов 10918. Ответов 8 Метки нет (Все метки) Создать шаблон функции, выполгяющий сортировку слиянием (Метод Фон Неймана) в массиве. Протестировать шаблон для массивов с элементами различных типов: int, float, char. Заранее спасибо... 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	16.12.2007, 11:48	2
	а можно озвучить сей метод... а то я про такой даже на слышал... 0

@Юленька 0 / 0 / 0 Регистрация: 16.12.2007 Сообщений: 4
	16.12.2007, 11:56 [ТС]	3
	Метод фон Неймана: Упорядочить пары соседних элементов массива а (а0 и а1, а2 и а3 и т.д.) и перенести их во вспомогательный массив b. Затем взять по две соседние пары из b и, слив их в упорядоченные четверки, снова записать в а; затем каждые две четверки из b слить в упорядоченные восьмерки и переписать в а и т.д. Упорядоченный массив должен оказаться в массиве а. В этом алгоритме массивы упорядочиваются по возрастанию. Помогите пожалуйста... 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	16.12.2007, 13:33	4
	я, конечно, ничего не имею против фон неймана, но придумал он лютую жесть... ну попробую... завтра пришлю сырцы.... 0

@Юленька 0 / 0 / 0 Регистрация: 16.12.2007 Сообщений: 4
	16.12.2007, 19:26 [ТС]	5
	Сообщение от WooDooMan666 я, конечно, ничего не имею против фон неймана, но придумал он лютую жесть... ну попробую... завтра пришлю сырцы.... Если я не сдам эту задачку, то я не получу зачёт Заранее тебе спасибо. 0

@Ain 2 / 2 / 1 Регистрация: 20.12.2009 Сообщений: 20
	22.12.2009, 07:31	8
	Ai,Спасибо большое, Вы меня просто выручили сортровкой слиянием! 0

	10.12.2010, 16:14