#include "Sort.h"

void Partition(list &l, list &l1, list &l2, list &l3)
{
	node* p = l.PopFront();
	l2.PushFront(p);
	while (l.head)
	{
		p = l.PopFront();
		if (p->key < l2.head->key) l1.PushFront(p);
		if (p->key == l2.head->key) l2.PushFront(p);
		if (p->key > l2.head->key) l3.PushFront(p);
	}
}

list QuickSort(list l)
{
	if (l.head == l.tail) return l;

	list l1, l2, l3;
	Partition(l, l1, l2, l3);
	l1 = QuickSort(l1);
	l3 = QuickSort(l3);
	if (l2.tail) l2.tail->next = l3.head;
	else l2.head = l2.tail = l3.head;
	if(l1.tail) l1.tail->next = l2.head;
	else l1.head = l1.tail = l2.head;
	l.head = l1.head;
	if(l3.tail) l.tail = l3.tail;
	else l.tail = l2.tail;

	return l;
}

void PartitionEvenOdd(list &l, list &l1, list &l2)
{
	while (l.head)
	{
		node* p = l.PopFront();
		if (p->key % 2 == 0) l1.PushFront(p);
		else l2.PushFront(p);
	}
}

list QuickSortEvenOdd(list l)
{
	list l1, l2;
	PartitionEvenOdd(l, l1, l2);
	l1 = QuickSort(l1);
	l2 = QuickSort(l2);
//	cout << l1  << endl << l2 << endl;
	if (l1.tail) l1.tail->next = l2.head;
	else l1.tail = l1.head = l2.head;
	if (l2.tail) l.tail = l2.tail;
	else l.tail = l1.tail;
	l.head = l1.head;

	return l;
}