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

  • Автор темы Charley2
  • Дата начала
Статус
Закрыто для дальнейших ответов.
C

Charley2

Гость
#1
Код:
#pragma hdrstop

#include <tchar.h>
#include <iostream.h>
#include <conio.h>
#include <windows.h>
#include <stdlib.h>
#include <stdio.h>

//---------------------------------------------------------------------------

#pragma argsused

class Element {
public:
int data;
Element *next;
Element *prev;
};

class list {
Element *top;
int MaxCount;
public:
int count;
list()
{
MaxCount=0;
count=0;
top=NULL;
}
int IsEmpty ()
{
if (top==NULL)
{
return true;
}
else
return false;
}
int pop()
{
if(!IsEmpty())
{
int element;
element=top->data;
MaxCount--;
top=top->next;
return element;
} else
return NULL;
}

void push(int i)
{
Element *link = new Element;
link->data=i;
link->next=top;
top=link;
MaxCount++;
}

void show()
{
Element *tmp = top;
while (tmp)
{
cout << tmp->data << " ";
tmp=tmp->next;
}
}

void mergeSort(list part)
{
list right_mas;
list left_mas;
int max=MaxCount;
int element;
if (max>=2)
{
for (int i=max; i>0; i--)
{
if (i>max/2)
{
element=pop();
right_mas.push(element);
} else
{
element=pop();
left_mas.push(element);
}
}
mergeSort(right_mas);
mergeSort(left_mas);
//merge(top, stakan.top);
}
show();
cout << "\n";
}
};

int main()
{	 for (int i=0; i<10; i++)
{
a=rand()%100;
t2.push(a);
}
t2.mergeSort(t2);
getch();
return 0;
}
Метод mergeSort делит связный список на списки до тех пор пока в списках останется только один элемент. Вызов t2.mergeSort(t2) должен показать по идее содержимое всех списков, состоящих из одного элемента, но он ничего не показывает. Почему?
 
C

Charley2

Гость
#7
Сортировка слиянием, если кому интересно.
Долго мучился, но решение мне подсказали
Код:
#pragma hdrstop
#include <tchar.h>
#include <iostream>
#include <fstream>
#include <windows.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>

#pragma argsused
using namespace std;

template <typename T>
class Element {
public:
T data;
Element *next;
Element *prev;
};


template <typename T>
class list {
Element<T> *top;
int MaxCount;
bool metka;
public:
list()
{
MaxCount=0;
top=NULL;
}

bool IsEmpty ()
{
if (top==NULL)
{
return true;
}
else
return false;
}

void push(T i)
{
Element<T> *link = new Element<T>;
link->data=i;
link->next=top;
top=link;
MaxCount++;
}

T pop()
{
if(!IsEmpty())
{
T element;
element=top->data;
MaxCount--;
top=top->next;
return element;
} else
return NULL;
}

void show()
{
Element<T> *tmp = top;
while (tmp)
{
cout	<< tmp->data << " ";
tmp=tmp->next;
}
}

list<T> mergeSort(list<T>& stack)
{
int max=stack.MaxCount;
stack.metka=true;
list<T> central_mas;
for (int i=max/2; i>0; i--)
{
central_mas.push(stack.pop());
}
if (stack.MaxCount>1) stack=stack.mergeSort(stack); //это мне подсказали
if (central_mas.MaxCount>1) central_mas=central_mas.mergeSort(central_mas); //это мне подсказали
list<T> buffer;
T left_element;
T right_element;
while (stack.IsEmpty()==false && central_mas.IsEmpty()==false)
{
left_element=stack.pop();
right_element=central_mas.pop();
if (left_element >= right_element)
{
buffer.push(left_element);
central_mas.push(right_element);
} else
{
stack.push(left_element);
buffer.push(right_element);
}
}
while (stack.IsEmpty()==false)
{
buffer.push(stack.pop());
}
while (central_mas.IsEmpty()==false)
{
buffer.push(central_mas.pop());
}
while (buffer.IsEmpty()==false)
{
stack.push(buffer.pop());
}
return stack;
}

~list()
{
if (metka==false)
{
while (top!=NULL)
{
Element<T> *tmp=top;
top=top->next;
delete tmp;
}
}
}
};
на 50000 элементах сортировка работает за 0,7 с.
 
Статус
Закрыто для дальнейших ответов.