80.8k views
1 vote
Why do Selection Sort and Insertion Sort’s outer loops run 11 iterations if there are 12 elements in the array?

1 Answer

3 votes

Answer:

The final case in selection sort is trivially sorted.

The final iteration in insertion sort is not needed.

Step-by-step explanation:

For selection sort, you make sub arrays and find the smallest element placing it in the front and repeat until sorted. This guarantees the final element will already be the greatest element, thus it is trivially sorted.

For Insertion sort, you use the initial element and compare it to the previous element and swap if the current is larger than the previous. Using this sort, you will always perform n-1 comparisons where n is the total amount of elements in the array. Thus, there are only 11 iterations for a 12 element array.

Cheers.

User Nevenka
by
5.3k points