// Quick Sort on a Linked List
// By Stephen Hassall
// Web: www.logic22.com
// EMail: stephen@logic22.com

#include <stdio.h>

// Define a linked list structure
typedef struct _tagIntegerList
{
	// The integer object
	int nInteger;

	// Pointers
	struct _tagIntegerList *pPrev;
	struct _tagIntegerList *pNext;
} IntegerList;

// Pointers to First and Last items
IntegerList *g_pFirstItem = NULL;
IntegerList *g_pLastItem = NULL;

// Add List Item
void AddListItem(int nInteger)
{
	// Create a new list item
	IntegerList *pItem = new IntegerList;
	
	// Set Integer value
	pItem->nInteger = nInteger;

	// Add to list
	// If this is the first item added
	if (g_pFirstItem == NULL)
	{
		g_pFirstItem = g_pLastItem = pItem;
		pItem->pNext = pItem->pPrev = NULL;
	}
	else
	{
		// Add item to the end of the list
		g_pLastItem->pNext = pItem;
		pItem->pPrev = g_pLastItem;
		g_pLastItem = pItem;
		pItem->pNext = NULL;
	}
}

// Remove all items
void RemoveAllItems()
{
	IntegerList *pDelItem, *pItem = g_pFirstItem;

	// Loop while there are items
	while (pItem != NULL)
	{
		// Set the delete item
		pDelItem = pItem;

		// Move to the next item
		pItem = pItem->pNext;

		// Delete the item
		delete pDelItem;
	}

	// Set global pointers to NULL
	g_pFirstItem = g_pLastItem = NULL;
}

// Print List
void PrintList()
{
	IntegerList *pItem = g_pFirstItem;

	// Loop while there are items
	while (pItem != NULL)
	{
		// Print this item
		printf("%d\n", pItem->nInteger);

		// Move to the next item
		pItem = pItem->pNext;
	}
}

// Quick Sort List
void QuickSortList(IntegerList *pLeft, IntegerList *pRight)
{
	IntegerList *pStart;
	IntegerList *pCurrent; 
	int nCopyInteger;

	// If the left and right pointers are the same, then return
	if (pLeft == pRight) return;

	// Set the Start and the Current item pointers
	pStart = pLeft;
	pCurrent = pStart->pNext;

	// Loop forever (well until we get to the right)
	while (1)
	{
		// If the start item is less then the right
		if (pStart->nInteger < pCurrent->nInteger)
		{
			// Swap the items
			nCopyInteger = pCurrent->nInteger;
			pCurrent->nInteger = pStart->nInteger;
			pStart->nInteger = nCopyInteger;
		}	
		
		// Check if we have reached the right end
		if (pCurrent == pRight) break;

		// Move to the next item in the list
		pCurrent = pCurrent->pNext;
	}

	// Swap the First and Current items
	nCopyInteger = pLeft->nInteger;
	pLeft->nInteger = pCurrent->nInteger;
	pCurrent->nInteger = nCopyInteger;

	// Save this Current item
	IntegerList *pOldCurrent = pCurrent;

	// Check if we need to sort the left hand size of the Current point
	pCurrent = pCurrent->pPrev;
	if (pCurrent != NULL)
	{
		if ((pLeft->pPrev != pCurrent) && (pCurrent->pNext != pLeft))
			QuickSortList(pLeft, pCurrent);
	}

	// Check if we need to sort the right hand size of the Current point
	pCurrent = pOldCurrent;
	pCurrent = pCurrent->pNext;
	if (pCurrent != NULL)
	{
		if ((pCurrent->pPrev != pRight) && (pRight->pNext != pCurrent))
			QuickSortList(pCurrent, pRight);
	}
}

// Main
void main ()
{
	// Add some items
	AddListItem(100);
	AddListItem(12);
	AddListItem(56);
	AddListItem(67);
	AddListItem(4);
	AddListItem(91);
	AddListItem(34);
	AddListItem(59);
	AddListItem(42);
	AddListItem(20);
	AddListItem(83);
	AddListItem(74);
	AddListItem(33);
	AddListItem(79);
	AddListItem(49);
	AddListItem(51);

	// Sort the list
	QuickSortList(g_pFirstItem, g_pLastItem);

	// Print list
	PrintList();

	// Remove items from list
	RemoveAllItems();
}