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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 24.03.2008, 17:27
Новичок

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

Помогите реализовать сортировку естественным двухпутевым слиянием на С++
Народ.
Помогите реализовать сортировку естественным двухпутевым слиянием на С++.
Срочно надо для сдачи допуска к курсовой.
Если можно то с коментариями, но это не обезательно.
  #2  
Старый 24.03.2008, 17:55
MBo MBo вне форума
Местный

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

Возьми алгоритм прямого слияния, и измени условие слияния подмассивов - для естественного слияния ищется неубывающая серия
  #3  
Старый 24.03.2008, 18:03
гость

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

Сообщение от MBo Посмотреть сообщение
Возьми алгоритм прямого слияния, и измени условие слияния подмассивов - для естественного слияния ищется неубывающая серия
Спасидо большое! Ты случаем не в Иркутске живешь. А то если в Иркутске, то с меня пиво)!
  #4  
Старый 24.03.2008, 18:12
гость

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

Сообщение от MBo Посмотреть сообщение
Возьми алгоритм прямого слияния, и измени условие слияния подмассивов - для естественного слияния ищется неубывающая серия
#include "stdafx.h"
#include <iostream>
#include <ctime>

using namespace std;

template<class T>
void Sort(T a[], long lb, long ub)
{
long splitter;
if (lb < ub) {
splitter = (lb + ub)/2;
Sort(a, lb, splitter);
Sort(a, splitter+1, ub);
//слияние результатов в общий массив
merge(a, lb, splitter, ub);
}
}
template<class T>
void merge(T a[], long lb, long split, long ub)
{
long pos1=lb;
long pos2=split+1;
long pos3=0;
T *temp = new T[ub-lb+1];
while (pos1 <= split && pos2 <= ub)
{
if (a[pos1] < a[pos2])
temp[pos3++] = a[pos1++];
else
temp[pos3++] = a[pos2++];
}
while (pos2 <= ub)
temp[pos3++] = a[pos2++];
while (pos1 <= split)
temp[pos3++] = a[pos1++];
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];
delete[] temp;
}

int _tmain(int argc, _TCHAR* argv[])
{
srand(time(0));
int size;
cout<<"Input size of array"<<endl;
cin>>size;
int *mass = new int[size];
for(int i = 0;i<size;++i)
mass[i] = rand() % 100;
cout<<endl;
cout<<"\tArray"<<endl;
for(int i = 0;i<size;++i)
cout<<mass[i]<<' ';
Sort(mass,0,size-1);
cout<<endl;
cout<<"\tArray after sorting"<<endl;
for(int i = 0;i<size;++i)
cout<<mass[i]<<' ';
cout<<endl;
delete[] mass;
return 0;
}

Смотри вот этот алготитм на С++, и че где менять, я прочитал сам алгоритм и как я понял он всеравно делит массив на две части, а естественное слияние не должно делить, вот тут можешь немного объеснить. И плз помоги)
  #5  
Старый 24.03.2008, 19:41
MBo MBo вне форума
Местный

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

Смысл ест. слияния - идем по массиву, определяем первую неубывающую серию. Как только она закончилась- запомнили начало и конец, ищем конец второй неубыв. серии, выполняем слияние этих двух серий в другой массив, продолжаем со следующей парой серий. Работа алгоритма заканчивается, когда на очередной итерации во всем массиве было две серии, и они слиты в одну.
  #6  
Старый 25.03.2008, 16:13
Новичок

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

Код:
#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;




template <class Q>
void merge_sort(Q a[], int lb, int ub){
poisk(a,lb,ub);


}


template <class Q>
void slian(Q a[], int lb, int l, int ub, int r, int w) {
Q *t = new Q[ub-lb+1];
if(w%2==0){
for (int lt=0, i=lb, j=ub; i<=l || j>=r;lt++){
if(i<=l && j>=r){
if(a[i]<a[j]){
t[lt]=a[i];
i++;
}
else{ 
t[lt]=a[j];
j++;
} 
}


if(i<=l && j<r){
t[lt]=a[i];
i++;
}

if(j>=r && i>l){
t[lt]=a[j];
j++;
}
}
}
}

template <class Q>
void poisk(Q a[], int lb, int ub){
int w=0;
int l=lb;
int r=ub;
for (int c=0;(l+1)!=r;){

for (int i=l; i<r; i++){
if(a[i]<a[i+1]){

l=i;
} 
else
break;
}

for (int j=r; l<j; --j){
if(a[j]<a[j-1]){

r=j;
} 
else
break;
}
slian (a, lb, l, ub, r, w);
w+=1;
lb=l+1;
ub=r-1;
}

}

int _tmain(int argc, _TCHAR* argv[])
{

int c[16]={503, 87, 512, 61, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703};

for (int i=0; i<16; i++)
cout<<c[i]<<",";
cout<<endl;

merge_sort (c, 0, 15);

for (int i=0; i<16; i++)
cout<<c[i]<<",";
cout<<endl;



return 0;
}
Вот код который у меня получился. Он у меня ищет упорядоченные куски и сливает их, и все дальше у меня стопор(

Последний раз редактировалось Witcher, 25.03.2008 в 17:10.
  #7  
Старый 25.03.2008, 17:14
MBo MBo вне форума
Местный

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

Код:
procedure MergeSortNatural(var A: array of Integer);
var
  N, ll, mm, rr, SeriesCnt: Integer;
  B: array of Integer;

  procedure Merge(var c, d: array of Integer; l, m, r: Integer);
  var
    i, j, k: Integer;
  begin
    i := l;
    j := m;
    k := l;
    while (i < m) and (j <= r) do
      if c[i] <= c[j] then begin
        d[k] := c[i];
        Inc(k);
        Inc(i);
      end
      else begin
        d[k] := c[j];
        Inc(k);
        Inc(j);
      end;
    while i < m do begin
      d[k] := c[i];
      Inc(k);
      Inc(i);
    end;
    while k <= r do begin
      d[k] := c[j];
      Inc(k);
      Inc(j);
    end;
  end;

begin
  N := Length(A);
  SetLength(B, N);
  repeat
    SeriesCnt := 0;
    ll := 0;
    repeat
      mm := ll + 1;
      while (mm < N) and (A[mm - 1] <= A[mm]) do
        Inc(mm);
      rr := mm + 1;
      while (rr < N) and (A[rr - 1] <= A[rr]) do
        Inc(rr);
      Inc(SeriesCnt);
      Merge(A, B, ll, mm, rr - 1);
      ll := rr;
    until ll >= N;
    Move(B[0], A[0], N * SizeOf(Integer));
      //лучше менять указатели A<=>B
  until SeriesCnt <= 1;
end;
  #8  
Старый 25.03.2008, 18:18
Новичок

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

Сообщение от MBo Посмотреть сообщение
Код:
procedure MergeSortNatural(var A: array of Integer);
var
  N, ll, mm, rr, SeriesCnt: Integer;
  B: array of Integer;

  procedure Merge(var c, d: array of Integer; l, m, r: Integer);
  var
    i, j, k: Integer;
  begin
    i := l;
    j := m;
    k := l;
    while (i < m) and (j <= r) do
      if c[i] <= c[j] then begin
        d[k] := c[i];
        Inc(k);
        Inc(i);
      end
      else begin
        d[k] := c[j];
        Inc(k);
        Inc(j);
      end;
    while i < m do begin
      d[k] := c[i];
      Inc(k);
      Inc(i);
    end;
    while k <= r do begin
      d[k] := c[j];
      Inc(k);
      Inc(j);
    end;
  end;

begin
  N := Length(A);
  SetLength(B, N);
  repeat
    SeriesCnt := 0;
    ll := 0;
    repeat
      mm := ll + 1;
      while (mm < N) and (A[mm - 1] <= A[mm]) do
        Inc(mm);
      rr := mm + 1;
      while (rr < N) and (A[rr - 1] <= A[rr]) do
        Inc(rr);
      Inc(SeriesCnt);
      Merge(A, B, ll, mm, rr - 1);
      ll := rr;
    until ll >= N;
    Move(B[0], A[0], N * SizeOf(Integer));
      //лучше менять указатели A<=>B
  until SeriesCnt <= 1;
end;
Извени но я не понял, ваще ни чего. Я просто Паскаль как я понял не знаю.
  #9  
Старый 11.06.2008, 20:54
disturbed

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

help
программа сортировки методом естественного слияния (внешняя сортировка) на С++
Реализовать этап предварительной сортировки фрагментов для получения начальных серий.
Использовать 5 файлов – входной и 4 вспомогательных. Исходный набор данных – случайные
числа от 1 до 3 миллионов.

надо срочно сдать курсовик помогите плз
  #10  
Старый 19.06.2008, 14:38
Новичок

Отправить личное сообщение для Lonelind Посмотреть профиль Найти все сообщения от Lonelind
 
Регистрация: 19.06.2008
Адрес: Иркутск, Россия
Сообщений: 2

Witcher, здорово вот всем надо курсовик... блин...
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите реализовать в рефале vilza Реализация, исходники, языки 7 18.11.2009 20:21
Помогите реализовать свертку суммированием tumanovalex Реализация, исходники, языки 3 29.10.2007 14:48