Сортировка двухфазным слиянием

  • Автор темы Witcher
  • Дата начала
W

Witcher

#1
[codebox]#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;

template <class Q>
void slian(Q a[], int lb, int centr, int ub) {

// позиция чтения из первой последовательности a[lb]...a[centr]
int p1=lb;


// позиция чтения из второй последовательности a[centr+1]...a[ub]
int p2=centr+1;

// текущая позиция записи в slian
int p3=0;

Q *slian = new Q[ub-lb+1];

while (p1 <= centr && p2 <= ub) {
if (a[p1] < a[p2])
slian[p3++] = a[p1++];
else
slian[p3++] = a[p2++];
}

// одна последовательность закончилась -
// копировать остаток другой в конец буфера
while (p2 <= ub) // пока вторая последовательность непуста
slian[p3++] = a[p2++];
while (p1 <= centr) // пока первая последовательность непуста
slian[p3++] = a[p1++];

// скопировать буфер slian в a[lb]...a[ub]
for (p3 = 0; p3 < ub-lb+1; p3++)
a[lb+p3] = slian[p3];


}

template <class Q>
void sort(Q a[], int lb, int ub){
int* s= new int [ub+1];
int c=1;
int l=lb;
int r=ub;
int t;// где остановилась запись в массиве s в начале
int y;// где остановилась запись в массиве s в конце
int w=2;
//int kriterii=1;
if (w>1){
for (int i=l, j=r; i<j; i++, --j){// цикл ищет упорядоченные участки в массиве
if(a<a[i+1]){
c+=1;
l=i;
}
else{
//kriterii+=1;
break;
}
if(a[j]<a[j-1]){
c+=1;
r=j;
}
else{
//kriterii+=1;
break;
}
}
int* ps= new int [c];

for (int i=0; i<16; i++){
if(i<=l)
ps=a;
else
break;
}
for (int i=(l+1), j=r; i<16; i++, j++){
if (i<c)
ps=a[j];
else
break;
}

slian (ps, 0, l, c-1);
w+=1;
if((w%2)!=0){
for (int i=0; i<c; i++){
s=ps;
t=i;
}
}
if((w%2)==0){
for (int j=(ub+1), i=0; i<c; i++, --j){
s[j]=ps;
y=i;
}
}

}
else {
for (int i=0; i<16; i++){
c=s;
}
}
}

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};



return 0;
}
[/codebox]

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