Data Structures and Algorithms: BRIDGES

Let’s revisit the task of sorting a stack of phone bills for the past year. Another intuitive approach would be to go through the pile and find the bill for January, setting it aside. Then continue searching for the bill for February and place it after January. Repeat this process with the remaining bills, selecting and arranging them in order until you reach the end. This approach serves as the basis for our last Θ(n^2) sorting algorithm, known as Selection Sort.

During each pass of Selection Sort, we "select" the i-th largest key in the array and place it at the end. In simpler terms, we start by finding the largest key in the unsorted portion of the list, then the next largest, and so on. Selection Sort stands out with its minimal number of swaps. While searching for the next largest key value requires scanning through the entire unsorted section, only one swap is needed to position the record correctly. Consequently, the total number of swaps required will be n-1. It’s worth noting that any algorithm can be implemented in various ways. For instance, we could have designed Selection Sort to find the smallest record, followed by the next smallest, and so forth. However, in our version, we aimed to closely resemble the behavior of our Bubble Sort implementation. This highlights that Selection Sort is essentially a modified version of Bubble Sort, where we keep track of the position of the record to be selected and perform a single swap at the end.

Here is a link to the OpenDSA textbook that has examples for selection sort: Read Me¹