This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Quick Sort On Linked List Submitted by

Ive been making a number of standard classes for my own future developments and one of them was a linked list class. I wanted a method to sort the list but not using the slow bubble sort. I wanted the speed of quick sort, but there wasnt a qsort run time function for linked lists. So I hunted down the quick sort algorithm and applied it to my linked list class.
Anyway, I wanted to give something useful to COTD, so I quickly wrote the code below to show you how its done. I havent compared the function to a quick sort function using an array, so I dont know how fast it is.

Download Associated File: qsort.cpp (3,656 bytes)

    // 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();
    }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.