Thread: Sentinel in sorting algorithms

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    27

    Sentinel in sorting algorithms

    Maybe this doesn't have to do strictly with C programming syntax wise, however I thought maybe someone would be able to help me.

    My question was, what exactly does it mean to use a sentinel when performing a sorting algorithm and how do you implement one?

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Sentinels are just placeholders - like you use a bookmark when you're reading a book. When the left and right sentinels cross in Quicksort, for example, you know that the entire sub array has been covered, since they start at opposite sides of the numbers being sorted then.

    They're usually integers or pointers, and provide indexes into the array or sub array being sorted.

    In an array with 10 elements, Array[0] would be left, Array[9] would be right. When they needed to be swapped, you wouldn't want to hard code numbers for the indexes, so you just use Array[left] and Array[right], etc. I and j are other common names for index placeholders in loop code.

    Code:
    for(i = 0; i < MaxArraySize - 1; i++)  {
       for(j = i + 1; j < MaxArraySize; j++)  {
          if(Array[i] > Array[j]  {
             temp = Array[i];
             Array[i] = Array[j];
             Array[j] = temp;
          }    
       }
    }
    The above is a simple selection sort, showing how i and j are commonly used as sentinels
    in a sort.

  3. #3
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    In a wider sense a sentinel is a general value that tells you when you can stop doing something.
    Take strlen for example. Since you don't know the actual length of the string, you have to traverse each char until you hit a '\0'. That NULL terminator is your sentinel, it tells you that you can stop traversing the string and that you've found the length.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. Sorting Algorithms
    By ashir30000 in forum C++ Programming
    Replies: 9
    Last Post: 05-21-2009, 09:27 AM
  4. Sorting Algorithms with Time
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2005, 11:27 AM
  5. recommendations on sorting algorithms
    By btq in forum C++ Programming
    Replies: 4
    Last Post: 10-14-2002, 11:36 AM