tag

#sentinel

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 1. Linear and Sequential Search ›

Sentinel Linear Search

Sentinel Linear Search Sentinel linear search removes the explicit boundary check inside the loop by placing the target value at the end of the array as a sentinel. This reduces one comparison per iteration and improves constant factors while preserving correctness. You use it when you want a tight inner loop and can safely modify the array temporarily. Problem Given an array $A$ of length $n$ and a value $x$,...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Insertion Sort with Sentinel

Insertion Sort with Sentinel Insertion sort with sentinel is a small optimization of insertion sort. It first places the minimum element at the beginning of the array. That element acts as a sentinel, so the inner loop can stop without checking whether it has reached the start of the array. You use it when implementing insertion sort as a low-level routine, especially inside hybrid sorts. Problem Given an array (...