автоматная программа сортировки слиянием

[FrauAja]

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

Код: Выделить всё

void merge(int *A, int l, int s, int r)
{
//слияние упорядоченных частей массива
int pos1=l;
int pos2=s+1;
int pos3=0;
int *B;
B=(int*)calloc((r-l+1), sizeof(int));
 
//идет слияние, пока есть хоть один элемент в каждой последовательности
while(pos1<=s && pos2<=r)
{
 if(A[pos1]<A[pos2]) B[pos3++]=A[pos1++];
 else B[pos3++]=A[pos2++];
}
 
//одна последовательность закончилась
while(pos2<=r)
B[pos3++]=A[pos2++];
while(pos1<=s)
B[pos3++]=A[pos1++];
 
//скопировать B в A
for(pos3=0; pos3<r-l+1; pos3++)
A[l+pos3]=B[pos3];
free(B);
}
 
void mergeSort(int *A,int l, int r)
{
int s;//индекс, по которому делим массив
if(l<r)//если больше одного элемента
{
  s=(l+r)/2;
  mergeSort(A, l, s); //сортировать левую половину
  mergeSort(A, s+1, r); //сортировать правую половину
  merge(A, l, s, r); //слить результаты в общий массив
}
}

[PeksuxSa]

Собственно спор пойдет об этом Чаще всего человек склонен думать неожиданно? А как Вы хотели? выходят под маркой
А как они хотели? Влить немного воды и накрыть казан крышкой
Вот еще где бывает интересно Я очень простой парень невероятная мудрость При использовании ПЧВ можно
пора доставать платья и бикини Собственно речь будет об этом На свадьбе мужу вручался ключ в знак того неожиданно? А как Вы хотели? Йорка использовали его для

[Lapsha]

[quote="FrauAja"]Добрый день! нужно реализовать автоматную программу сортировки слиянием.
у меня реализован на данный момент только рекурсивный метод, не подскажите как его можно переделать в автомат


Вот нерекурсивный вариант сортировки слиянием. Может подойдет... Расчет автомата незнаю..
void MergeSort(vector<int>& p_varrInt);
void Swap(vector<int>& p_varrInt, int p_iA, int p_iB);
void Print(vector<int>& p_varrInt);

void MergeVarrs(
vector<int>& p_varrA,
vector<int>& p_varrB,
vector<int>& p_varrC) ;



int _tmain(int argc, _TCHAR* argv[])
{
vector<int> varrInt;




varrInt.push_back(9);
varrInt.push_back(1);
varrInt.push_back(8);
varrInt.push_back(2);
varrInt.push_back(5);
varrInt.push_back(4);
varrInt.push_back(2);
varrInt.push_back(12);
varrInt.push_back(3);
varrInt.push_back(4);
//for(int i=9; i >=0; i--)
//varrInt.push_back(i);

MergeSort(varrInt);

Print(varrInt);

return 0;
}


void MergeSort(vector<int>& p_varrInt)
{
vector<int> varrA, varrB, varrC;



//Упорядочиваем сначала соседние пары
for(int i=1; i < p_varrInt.size(); i+= 2)
{
if( p_varrInt[i-1] > p_varrInt )
Swap(p_varrInt, i-1, i);
}

/*Далее будем сливать 2 массива varrA, varrB в 1 (varrC) с упорядочиванием.
Готовим 1-ый массив*/
for(int i=0; i < 2; i++)
varrA.push_back(p_varrInt);


for(int i=2; i < p_varrInt.size(); i+= 2)
{
varrB.clear();

//Подготовили varrB
for(int j=i; j < i+2 && j < p_varrInt.size(); j++)
varrB.push_back(p_varrInt[j]);

//Теперь слив varrA и varrB в varrC с упорядочиванием
MergeVarrs(varrA, varrB, varrC);

//Теперь упорядоченная слив в varrC. Скопируем в varrA для дальнейших шагов
varrA.resize(varrC.size());
std::copy(varrC.begin(), varrC.end(), varrA.begin());
}

//Теперь готовый результат в varrC, копируем в исходный
std::copy(varrC.begin(), varrC.end(), p_varrInt.begin());
}


void MergeVarrs(
vector<int>& p_varrA,
vector<int>& p_varrB,
vector<int>& p_varrC)
{
int i=0, j=0;


p_varrC.clear();


while( i < p_varrA.size() && j < p_varrB.size() )
{
if( p_varrA < p_varrB[j] )
p_varrC.push_back(p_varrA[i++]);
else
p_varrC.push_back( p_varrB[j++] );
}


if( i < p_varrA.size() )
{
//Перельем остатки p_varrA
for( ; i < p_varrA.size(); i++)
p_varrC.push_back(p_varrA);
}else
{
//Остатки p_varrB
for( ; j < p_varrB.size(); j++ )
p_varrC.push_back( p_varrB[j] );
}
}


void Swap(vector<int>& p_varrInt, int p_iA, int p_iB)
{
int v_temp = p_varrInt[p_iB];
p_varrInt[p_iB] = p_varrInt[p_iA];
p_varrInt[p_iA] = v_temp;
}

void Print(vector<int>& p_varrInt)
{
for(int i=0; i < p_varrInt.size(); i++)
cout << p_varrInt << endl;
}