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

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

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

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

Внешняя многофазная сортировка
У меня такой вопрос. Не является ли вот эта сортировка Внешней многофазной сортировкой?
Код:
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
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;
}}
источник: http://ru.wikibooks.org/wiki/При...лиянием
Если нет, подкажите что-нить или где ее можно взять. Нужно на с/с++.
И что значит внешняя многофазная?
  #2  
Старый 06.12.2010, 17:06
гост

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

нет
  #3  
Старый 06.12.2010, 17:07
MBo MBo вне форума
Местный

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

>Не является ли вот эта сортировка Внешней многофазной сортировкой?
Нет, термин "внешняя" относится к работе с данными, ввиду своего размера находящимися не в памяти, а на внешних устройствах, например, на жестком диске.
  #4  
Старый 18.12.2010, 14:58
Новичок

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

Вобшем написал программу по этому алгоритму http://www.algolib.narod.ru/Sort/PolyPhaseMerge.html . Она вроде более менее работает, хотя косяков в ней хватает. Объясните как лучше память распределять на втором этапе, потому что если в исходном файле оч много данных, то если использовать динамические массивы, в них не хватает места потом на опред этапах и выводятся левые числа. Ну и вообще помогите пожалуйста исправить хоть приблизительно алгоритм, если я что-то совсем неправильно организовал. На первом этапе вроде все правильно работает. Со втором не уверен, сделал, чтобы он выполнялся, пока второй из файлов B или D не будет пустой. Пишу в среде BC31.

Код:
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <fstream.h>

int empty(char *str)
{
	 char *s;
	 ifstream file(str);
	 file>>s;
	 if(s[0]=='\0')
			return 1;
	 return 0;
}

void show(char *str)
{
   int mas[100];
	 ifstream file(str);
	 int i=0;
	 while(!file.eof())
	 {
			file>>mas[i];
			if(!file.eof())
			{
				 cout<<mas[i]<<" ";
				 i++;
			}
	}
	file.close();
  cout<<endl;
}

void write(char *str, int *mas, int &size)
{
	 ofstream file(str,ios::app);
	 int v=0;
	 while(v<size)
	 {
			file<<mas[v]<<"  ";
			v++;
	 }
	 file.close();
}

void sort(int *mas, int &i)
{
	 int j=0, temp, izm=1, hod=0;
	 while((hod<i)&&(izm!=0))
	 {
			izm=0;
			j=0;
			while(j<(i-1))
			{
				 if(mas[j]>mas[j+1])
				 {
						temp=mas[j];
						mas[j]=mas[j+1];
						mas[j+1]=temp;
						izm=1;
				 }
				 j++;
			}
			hod++;
	 }
}

void main(void)
{
	ofstream file2("A.txt");
	file2<<"";
	file2.close();
	ofstream file3("B.txt");
	file3<<"";
	file3.close();
	ofstream file4("C.txt");
	file4<<"";
	file4.close();
	ofstream file5("D.txt");
	file5<<"";
	file5.close();
	clrscr();
	//char *str, *str1, *str2;
	int const S=2;
	int i=0, mas[S], CurrentFile=1, flag=0;
	//cout << " Enter a way and file name: "; cin >> str;
	//cout << " Enter a way and file name for file A: "; cin >> str2;
	//cout << " Enter a way and file name for file B: "; cin >> str3;
	ifstream file("111.txt");
	while(!file.eof())
	{
		 i=0;
		 while((flag!=1) && (i<S))
		 {
				file>>mas[i];
				flag=(!file.eof())?0:1;
				if(flag!=1)
					 i++;
				else
					 break;
		 }

		 if(flag!=1)
		 {
				int j;
				sort(mas,i);
				if(CurrentFile==1)
				{
					 write("A.txt",mas,i);
					 CurrentFile=0;
				}
				else
				{
					 write("B.txt",mas,i);
					 CurrentFile=1;
				}
		 }

		 if((flag==1)&&(i!=0))
		 {
				int j;
				sort(mas,i);
				if(CurrentFile==1)
				{
					 write("A.txt",mas,i);
					 CurrentFile=0;
				}
				else
				{
					 write("B.txt",mas,i);
					 CurrentFile=1;
				}
		 }
	}
	cout<<"File: ";
	show("111.txt");
           cout<<"A: ";
	show("A.txt");
	cout<<"B: ";
	show("B.txt");
	//////////////////////////////////////////////////////////////////////////


	int Size=S;
	int Input=1;//, Input2=2;
	ifstream InputFile1("A.txt");
	ifstream InputFile2("B.txt");
	int CurrentOutput=3;

	int change=1;
	while(change!=0)
	{
		 change=0;
		 int const razm=Size+2;//Size*2;
		 int const r=(Size/2)+2;
		 int *mas1=new int[r], *mas2=new int[r], *masres=new int[razm], fl=0,fl2=0;
		 int ch=0;
		 while((!InputFile1.eof())&&(!InputFile2.eof()))
		 {
				ch++;
				int i,j;
				if(fl!=1)
				{
					 i=0;
					 while(i<(Size/2))
					 {
							InputFile1>>mas1[i];
							fl=(!InputFile1.eof())?0:1;
							if(fl!=1)
								 i++;
							else
							{
								 j=0;
								 while(fl2!=1)
								 {
										InputFile2>>mas2[j];
										fl2=(!InputFile2.eof())?0:1;
										if(fl2!=1)
											 j++;
								 }
								 break;
							}
					 }
				}
				if(fl2!=1)
				{
					 j=0;
					 while(j<(Size/2))
					 {
							InputFile2>>mas2[j];
							fl2=(!InputFile2.eof())?0:1;
							if(fl2!=1)
								 j++;
							else
							{
								 //i=0;
								 while(fl!=1)
								 {
										InputFile1>>mas1[i];
										fl=(!InputFile1.eof())?0:1;
										if(fl!=1)
											 i++;
								 }
								 break;
							}
					 }
				}

				int size=i+j;
				memcpy(masres,mas1,i*sizeof(int));
				memcpy(&masres[i],mas2,j*sizeof(int));
				sort(masres,size);
				if(CurrentOutput==1)				// if A
				{
					 write("A.txt",masres,size);
					 if(ch==2)
					 {
							CurrentOutput=2; 		// then B
							ch=0;
					 }
				}
				else
				{
					 if(CurrentOutput==2)		// if B
					 {
							//change=1;
							write("B.txt",masres,size);
							if(ch==2)
							{
								 CurrentOutput=1; 	// then A
								 //change=1;
								 ch=0;
							}
					 }
					 else
					 {
							if(CurrentOutput==3)		// if C
							{
								 write("C.txt",masres,size);
								 if(ch==2)
								 {
										CurrentOutput=4; // then D
										ch=0;
								 }
							}
							else
							{
								 if(CurrentOutput==4)		// if D
								 {
										//change=1;
										write("D.txt",masres,size);
										if(ch==2)
										{
											 CurrentOutput=3;  // then C
											 //change=1;
											 ch=0;
										}
								 }
							}
					 }
				}
		 }

		 delete []mas1;
		 delete []mas2;
		 delete []masres;
		 InputFile1.close();
		 InputFile2.close();

		 if(CurrentOutput==1)
		 {
				if(empty("B.txt")!=1)
					 change=1;
		 }
		 else
		 {
				if(empty("D.txt")!=1)
					 change=1;
		 }


		 if(change==0)
		 {
				if(CurrentOutput==1)
				{
					//if(empty("B.txt")==1)
					 //{
							cout<<"A: ";
							show("A.txt");
							cout<<"B: ";
							show("B.txt");
					 //}
					 //else change=1;
				}
				else
				{
					 //if(empty("D.txt")==1)
					 //{
							cout<<"C: ";
							show("C.txt");
							cout<<"D: ";
							show("D.txt");
					 //}
					 //else change=1;
				}
		 }


		 Size*=2;
		 if(change!=0)
		 {
				if(Input==1)
				{
					 Input=3;
					 CurrentOutput=1;
					 ofstream file("A.txt");
					 file<<"";
					 file.close();
					 ofstream file2("B.txt");
					 file2<<"";
					 file2.close();
					 fl=0;fl2=0;
					 cout<<"C: ";
					 show("C.txt");
					 cout<<"D: ";
					 show("D.txt");
					 InputFile1.open("C.txt");
					 InputFile2.open("D.txt");
				}
				else
				{
					 Input=1;
					 CurrentOutput=3;
					 ofstream file("C.txt");
					 file<<"";
					 file.close();
					 ofstream file2("D.txt");
					 file2<<"";
					 file2.close();
					 fl=0;fl2=0;
					 cout<<"A: ";
					 show("A.txt");
					 cout<<"B: ";
					 show("B.txt");
					 InputFile1.open("A.txt");
					 InputFile2.open("B.txt");
				}
		 }
	}

	getch();
}
Для данных 4 2 9 0 5 1 6 3 8 7 вроде работает.
Изображения:
Тип файла: jpg 1.jpg (23.0 Кб, 104 просмотров)

Последний раз редактировалось Aндрей, 19.12.2010 в 14:18.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Реализовать метод многопутевого сбалансированного слияния (внешняя сортировка) Delphi Яночка_90 Сортировка и поиск 3 08.06.2010 11:25
Многофазная сортировка файлов Ro. Сортировка и поиск 1 05.05.2009 00:10
Внешняя сортировка прямым слиянием OKSI55 Сортировка и поиск 0 22.03.2009 13:31
Многофазная сортировка в массиве freddy_kruger Сортировка и поиск 0 21.03.2009 19:36
Внешняя сортировка на Visual С++. BitHunter Сортировка и поиск 3 07.05.2008 17:21