#algorithm# quick sort by linked list

linked_list.cpp

#include "linked_list.h"
#include "timer.h"
#include "LazyTest.h"
#include <list>

// standard
#include <ctime>
#include <random>
#include <algorithm>

using namespace std;

template <class T>
void output(const list<T>& ls)
{
	for(list<T>::const_iterator it = ls.begin(); it != ls.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}

template <class T>
void sort(list<T>& ls)
{
	// Do nothing if the list has length 0 or 1.
	if (ls.size() > 2)
	{
		list<T> __carry;
		list<T> __counter[64];
		int __fill = 0;
		while (!ls.empty()) {
			__carry.splice(__carry.begin(), ls, ls.begin());
			int __i = 0;
			while(__i < __fill && !__counter[__i].empty()) {
				__counter[__i].merge(__carry); // _carry is emptied!!!
				__carry.swap(__counter[__i++]);
			}
			__carry.swap(__counter[__i]);         
			if (__i == __fill) ++__fill;

			for (int __i = 0; __i < __fill; ++__i)
				output(__counter[__i]);
		} 

		for (int __i = 1; __i < __fill; ++__i)
			__counter[__i].merge(__counter[__i-1]);
		ls.swap(__counter[__fill-1]);
	}
}




struct Node
{
public:
	Node(int _data):data(_data){}
	int data;
	Node* next;
};

Node*& next(Node* n)
{
	return n->next;
}

bool less1(Node* n1, Node* n2)
{
	return n1->data < n2->data;
}


TESTCASE(linked_list_quick_sort)
{
	std::tr1::mt19937 eng;
	eng.seed(time(NULL));
	std::tr1::uniform_int<int> unif(-10000, 10000);

	int num = 100000;
	int val = unif(eng);


	// initialize data in linked list and vector
	vector<int> vec;
	vec.push_back(val);

	Node* head = new Node(val);

	Node* cur = head;
	while(num--)
	{
		int val = unif(eng);

		cur->next = new Node(val);
		cur = cur->next;
		//int* p = new int[4000];

		vec.push_back(val);
	}
	cur->next = NULL;



	{
		CAutoTimer at;
		cout << "copy and vector: ";
		vector<int> v;
		
		Node* temp = head;
		while(temp)
		{
			v.push_back(temp->data);
			temp = temp->next;
			
		}

		std::sort(vec.begin(), vec.end());
	}


	// sort using different ways
	//
	//
	{
		CAutoTimer at;
		cout << "vector: ";
		std::sort(vec.begin(), vec.end());
	}


	{
		Node* iter = NULL;
		CAutoTimer at;
		cout << "linked list: ";
		iter = quick_sort<Node*>(head, NULL, next, less1);
	}
}

linked_list.h

#pragma once
#include <utility>
// Quick sort for single linked list
// 
// Template arguments:
// T: node's pointer type
// Next: function/functor to get next node
// Compare: functor to compare 2 arguments
// 
// Functions:
// partition: partition the list into 2 parts, with the pivot at the middle
// quick_sort: recurisve sort left and right part
//
template <class T, class Next, class Compare>
std::pair<T, T> partition(T start, T end, Next next, Compare comp)
{
	// use the first element as pivot as it is easier to access
	T pivot = start; 

	// in process of partition, there are 4 part of datas:
	// pivot | less than pivot | larger than pivot | not processed |
	//
	// first, initialize sLast and lLast to the pivot 
	T sLast = start;
	T lLast = start; 

	// start to process each element after pivot
	T iter = next(start); 
	while(iter != end)
	{
		T cur = iter;
		iter = next(iter);

		if(comp(cur, pivot)) 
		{
			// insert current to the next of sLast, only if we already have some elements larger than pivot
			if(lLast != pivot)
			{
				// insert after sLast
				T temp = next(sLast);
				next(sLast) = cur;
				next(cur) = temp;

				// as cur is removed, we need to link the 2 node before and after
				next(lLast) = iter;
			}

			// advance sLast
			sLast = cur;
		}
		else
		{
			// advance lLast
			lLast = cur;
		}
	}

	T head = next(pivot);

	// Insert pivot to the correct position if there is no element less than pivot
	if(sLast != pivot) 
	{
		T temp = next(sLast);
		next(sLast) = pivot;
		next(pivot) = temp;
	}

	return std::make_pair(head ,pivot);
}


template <class T, class Next, class Compare>
T quick_sort(T start, T end, Next next, Compare comp)
{
	// base case - only one element in the list
	if(start == end) return start;
	if(start != NULL && next(start) == end) return start;
	if(end != NULL && next(end) == start) return end; // think about already sorted list

	// divide
	std::pair<T, T> pos = partition(start, end, next, comp);

	// and conquer
	T head1 = quick_sort(pos.first, pos.second, next, comp);
	T head2 = quick_sort(next(pos.second), end, next, comp);

	// link the first part and the second part, or else you may drop some elements
	next(pos.second) = head2;

	return head1;
}