Let’s now turn our attention to the problem of developing a general formula to compute the number of comparisons needed to sort any arbitrary list of N items. The algorithm will blindly scan the “unsorted” list during each pass to find the smallest item, not realizing that in this case the smallest item always appears first.
Surprisingly, this is true even if the original “unsorted” list were already sorted to begin with. If you think about it, you will see that regardless of the actual items to be sorted, or the original order of those items, 36 comparisons will always be required to sort eight items using the selection sort method. In each row, the “smallest item so far” is printed in boldface and the “current item” is underlined.Ī careful examination of this figure reveals that 36 comparisons are required to completely sort the eight items. The rows of the figure represent executions of step 3.1.3.1, which compares the “current item” to “smallest item so far”.
The “passes” shown in the figure correspond to repetitions of step 3.1, which scans the unsorted list for the smallest item. Illustrates the behavior of the selection sort algorithm on a list of eight items. The final result would be a list sorted in descending order, from largest to smallest. In this case the only change to the algorithm would be that instead of selecting the smallest object from the input list in step 3.1, the largest item would be selected. Since the process of “finding the smallest item” involves a number of steps, the algorithm includes a detailed description of that process in step 3.1.Ī descending order selection sort could also be defined. The selection algorithm is presented formally in.
At that point, all of the input items will be arranged in ascending order in the sorted list. This process of finding the smallest input item, removing it from the input list and appending it to the end of the sorted list is repeated over and over until the input list is empty. It will then remove that smallest item from the input list and append it to the end of the sorted list. Ascending order selection sort will scan through the input list to determine the smallest item in that list. The operation of the selection sort algorithm can be visualized by imagining a list of input objects and a second, originally empty, list which will eventually hold all of the input items in sorted order. One of the most straightforward ways of approaching the sorting problem is to use the selection sort method.
0 kommentar(er)
