CST370 Week 7
This week I learned Counting Sort and how it differs from comparison sorts. The idea is to build a frequency array for the value range, convert it to a cumulative (distribution) array, then scan the input right-to-left to place each element at count[value]-1 in the output and decrement the count. . Next we reviewed Radix Sort the idea is similar to Counting Sort, but you sort the integers by least significant digit (LSD), so no range is needed. We start from the least significant digit and work our way left. After a stable pass on each digit, the list ends up fully sorted. We looked at Dynamic Programming, which is a technique to avoid a lot of recursive calls by using an array to store solutions to subproblems. For example with Fibonacci, instead of making of repeated calls, we just run a simple for-loop to fill an array and reuse results. That turns the Fibonacci algorithm from exponential time complexity to linear time complexity which is really impressive to me. We look ...