Click here to Skip to main content
15,867,453 members
Articles / Mobile Apps
Article

Binary Sorting Into a std::list

Rate me:
Please Sign up or sign in to vote.
3.18/5 (22 votes)
9 Dec 2002CPOL3 min read 110.9K   14   13
One technique for performing a binary insertion sort on a std::list

Introduction

There is no spoon. The Oracle will see you now.

The Problem

Recently I had a need to perform an insertion sort on a STL list of filenames in descending file date order. One of the rules was that I could not change to a de-queue or queue - I had to stick with the list. This should be an indication to you that there were no other options available. The other rule (and one that is completely unrelated to this article but that is included for completeness) was that I had to sort the list into two sections - one that contained BMP files, and one that contained all other files (the existence of sub-folders was not a consideration for this particular task).

If you aren't already aware, the C runtime library's findnext function will find files in the order they were written to the disk. In a pristine environment where files are only created by your application, you can almost be guaranteed that when you perform a findnext on your disk drive, the files will be found in ascending date/time order in which they were written. Notice that I said "almost guaranteed".

If you've spent any time as a programmer, you know there's no such thing as a guaranteed outcome, or at least you shouldn't assume that the guarantee is always valid. So I didn't.

In my case, the act of first determining if the file was a BMP, what the file date/time was, and then finding where to insert it into the list was time-consuming. My original thought was to just start at the top of the list and iterate to the end of the list until I found the proper place to insert the filename. the problem was that for 100 BMP files, this process required about 75 seconds.

I guess I should take this opportunity to mention that the program is running on an SH3 processor under a bastardized implementation Windows CE 2.12, and is reading files off a FlashCard. This is not what I would call a speedy system.

The Solution

I decided that it would be faster if I could implement a binary insertion sort instead of the simple sort that I was already performing. The problem with implementing a binary sort on a STL list is that you can't move the iterator by saying something like

iter += 5;

You actually have to move the iterator one position at a time until it's in the correct position in the list. Believe me when I say this is a royal pain in the rear.

I can't post more code than this (proprietary stuff), but it should give you a basis for implementing a binary insertion sort on your own STL list.

// CFileData is a class I wrote to hold the WIN32_FIND_DATA structure 
// that's populated by a call to findnext

typedef std::list < CDiskFile* > FileList;
FileList m_FileList;

void MyListMgr::SortIntoList(CDiskFile* pFile)
{
	// Find a place to start and stop.  In my case, I had to maintain 
	// an iterator that tracked the begining of the section that was 
	// not BMP files (iEnd was NOT guaranteed to be the absolute end 
	// of the list), but for this example, it's not neccesary.
	FileList::iterator iBegin  = m_FileList.begin();
	FileList::iterator iEnd    = m_FileList.end();
	FileList::iterator iSorter = iBegin;
	int                steps   = m_FileList.size();

	// Find a place to put the file. The list is sorted in descending 
	// date order.
	while (iBegin != iEnd)
	{
	  // start with the iterator at the current beginninf of the list
	  iSorter = iBegin;
	  // find the middle
	  steps = (int)(steps / 2);
	  // move the iterator to the middle
	  for (int i = 0; i < steps; i++)
	  {
		 ++iSorter;
	  }
	  // if the date of the file being inserted is earlier or equal 
	  // to the date of the ciurrent iterator position
	  if (pFile->dateIsEarlierOrEqual((*iSorter)))
	  {
		 // change the beginning of the list to the current  
		 // iterator position
		 iBegin = iSorter;
		 // if we didn't move at all, and if we aren't at the  
		 // end of the list,  move the beginning one more step.
		 if (steps == 0 && iBegin != iEnd)
		 {
			++iBegin;
		 }
		 // we need to do it this way because eventually, you just 
		 // run out of "steps" (it's equal to 0), and the routine 
		 // would just sit there on the same iterator forever.  If 
		 // it gets to this point, it's safe to assume that simply 
		 // moving the iterator one more step in the appropriate 
		 // direction will locate the correct insertion point.
	  }
	  else
	  {
		 iEnd = iSorter;
		 if (steps == 0 && iEnd != iBegin)
		 {
			--iEnd;
		 }
	  }
	}
	iSorter = iEnd;
	m_FileList.insert(iSorter, pFile);
}

In Closing

This isn't rocket science, but it is a useful technique if you're stuck with having to use a list and you need a fast insertion sort into that list. Oh yeah, in case you were wondering, the time required to sort the same list of BMP files using this technique was reduced to 2.5 seconds (on the handheld device described earlier). It took less than one second on my P3/450 at work.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior) Paddedwall Software
United States United States
I've been paid as a programmer since 1982 with experience in Pascal, and C++ (both self-taught), and began writing Windows programs in 1991 using Visual C++ and MFC. In the 2nd half of 2007, I started writing C# Windows Forms and ASP.Net applications, and have since done WPF, Silverlight, WCF, web services, and Windows services.

My weakest point is that my moments of clarity are too brief to hold a meaningful conversation that requires more than 30 seconds to complete. Thankfully, grunts of agreement are all that is required to conduct most discussions without committing to any particular belief system.

Comments and Discussions

 
GeneralA bug occurs if the list and m_filelist contains the same items Pin
Tim L4-Aug-08 15:24
Tim L4-Aug-08 15:24 
QuestionProblems with sort in std::list (Correction) Pin
Carlos_Lopez24710-Mar-06 9:45
Carlos_Lopez24710-Mar-06 9:45 
QuestionProblems with sort in std::list Pin
Carlos_Lopez24710-Mar-06 9:35
Carlos_Lopez24710-Mar-06 9:35 
GeneralAdvance Pin
bramp6-Jan-06 14:28
bramp6-Jan-06 14:28 
GeneralGood one John Pin
Anonymous10-Mar-04 22:54
Anonymous10-Mar-04 22:54 
GeneralUse more STL?.. Pin
compiler11-Dec-02 20:31
compiler11-Dec-02 20:31 
GeneralRe: Use more STL?.. Pin
Anonymous18-Mar-04 8:02
Anonymous18-Mar-04 8:02 
GeneralRe: Use more STL?.. Pin
MaierMan26-Aug-05 22:35
MaierMan26-Aug-05 22:35 
GeneralRe: Use more STL?.. Pin
Anonymous3-Jun-04 7:41
Anonymous3-Jun-04 7:41 
GeneralNice Job Pin
Nick Parker10-Dec-02 17:33
protectorNick Parker10-Dec-02 17:33 
GeneralRe: Nice Job Pin
#realJSOP11-Dec-02 0:24
mve#realJSOP11-Dec-02 0:24 
GeneralRe: Nice Job Pin
Nick Parker11-Dec-02 7:32
protectorNick Parker11-Dec-02 7:32 
Generalright... Pin
Daniel Andersson10-Dec-02 6:26
Daniel Andersson10-Dec-02 6:26 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.