3.6.2.1 Quicksort Algorithm for Table Searching
Internally, this demo computes the temperature at each of the NTCs by using an array (table) of presorted values. Each value in the array is the expected value of the ADC indexed by temperature. By using precomputed values, we can save CPU time and avoid approximating the non-linear response curve.
To determine the temperature, first start in the middle of a table with 2N + 1 elements. The extra element is to ensure the table is odd. The value at this index is compared to the search value. If they are equal, then the search is complete. If they are not equal, then go either up or down ½ of the remaining table, depending on whether the term was bigger or smaller. When the table has no remaining elements, return the value at the last index. This algorithm does not have any rounding, so accuracy is limited to ±1°C, depending on the value. Additionally, the elements at the ends of the table are not accessible to the search algorithm, although these can be checked prior to the search, if desired. A simple example is shown below. With this algorithm, the time complexity is improved from to time.
