Printable View
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?
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.
The above is a simple selection sort, showing how i and j are commonly used as sentinelsCode: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;
}
}
}
in a sort.
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