Question

Given the unsorted list \([6,5,4,3,7,1,2],\) show what the contents of the list would be after each iteration of the loop as it is sorted using the following: a) Selection sort b) Insertion sort

Short answer

The list sorts to [1, 2, 3, 4, 5, 6, 7] in both selection and insertion sorts.

Step-by-step solution

Start Selection Sort

Selection sort operates by selecting the smallest element from the unsorted part and swapping it with the first unsorted element. Given the list: \([6, 5, 4, 3, 7, 1, 2]\)

First Pass of Selection Sort

Identify the smallest element from the entire list, which is \(1\), and swap it with the first element:\([1, 5, 4, 3, 7, 6, 2]\)

Second Pass of Selection Sort

Find the smallest element from the unsorted part \([5, 4, 3, 7, 6, 2]\), which is \(2\), and swap it with the first unsorted element:\([1, 2, 4, 3, 7, 6, 5]\)

Third Pass of Selection Sort

Find the smallest element from \([4, 3, 7, 6, 5]\), which is \(3\), and swap it with \(4\):\([1, 2, 3, 4, 7, 6, 5]\)

Fourth Pass of Selection Sort

Identify the smallest element from \([4, 7, 6, 5]\), which is \(4\). The element is in the correct position, so no swap is necessary:\([1, 2, 3, 4, 7, 6, 5]\)

Fifth Pass of Selection Sort

Select the smallest element from \([7, 6, 5]\), which is \(5\), and swap it with \(7\):\([1, 2, 3, 4, 5, 6, 7]\)

Sixth Pass of Selection Sort

Choose the smallest element from \([6, 7]\), which is \(6\). The element is in the correct position, so no swap is necessary:\([1, 2, 3, 4, 5, 6, 7]\)

Start Insertion Sort

Insertion sort builds the sorted list one element at a time. We begin with the first element in the list as sorted. Given the list: \([6, 5, 4, 3, 7, 1, 2]\)

First Pass of Insertion Sort

Insert \(5\) into the sorted portion \([6]\), resulting in the list:\([5, 6, 4, 3, 7, 1, 2]\)

Second Pass of Insertion Sort

Insert \(4\) into the sorted portion \([5, 6]\), resulting in the list:\([4, 5, 6, 3, 7, 1, 2]\)

Third Pass of Insertion Sort

Insert \(3\) into the sorted portion \([4, 5, 6]\), resulting in the list:\([3, 4, 5, 6, 7, 1, 2]\)

Fourth Pass of Insertion Sort

Insert \(7\) into the sorted portion \([3, 4, 5, 6]\), maintaining its position:\([3, 4, 5, 6, 7, 1, 2]\)

Fifth Pass of Insertion Sort

Insert \(1\) into the sorted portion \([3, 4, 5, 6, 7]\), resulting in:\([1, 3, 4, 5, 6, 7, 2]\)

Sixth Pass of Insertion Sort

Insert \(2\) into the sorted portion \([1, 3, 4, 5, 6, 7]\), resulting in the list:\([1, 2, 3, 4, 5, 6, 7]\)

Key concepts

Selection Sort

Selection sort is a simple yet effective sorting algorithm particularly for smaller lists. It works by selecting the smallest element from the unsorted section of the list and placing it at the beginning. The process is repeated for each element until the list is completely sorted. In our exercise, we start with the list

• [6, 5, 4, 3, 7, 1, 2]

On the first pass, we identify '1' as the smallest and swap it with '6', resulting in

• [1, 5, 4, 3, 7, 6, 2]

On subsequent passes, we continue to identify and swap the smallest element in the unsorted section. The key learning is that selection sort consistently narrows the field and always knows the portion which is sorted. Eventually, it results in

• [1, 2, 3, 4, 5, 6, 7]

where all elements are in the proper order.

Insertion Sort

Insertion sort builds a sorted list one element at a time by inserting each new element into its appropriate position among the previously sorted elements. It begins by considering the first element as sorted. For instance, in the initial list

• [6, 5, 4, 3, 7, 1, 2]

'6' is considered sorted. The algorithm proceeds by comparing and inserting elements like '5' and so on, adjusting backward until they find their correct position among the sorted items. For example, inserting '5' yields

• [5, 6, 4, 3, 7, 1, 2]

This process is repeated, resulting in the fully sorted list

• [1, 2, 3, 4, 5, 6, 7]

Insertion sort is particularly effective for lists that are already partially sorted since it performs minimal adjustments.

Algorithm Analysis

Analyzing sorting algorithms involves two primary concerns: time complexity and space complexity. For selection sort, the time complexity is \(O(n^2)\)due to the nested loops required to compare and swap elements. It does this regardless of whether a list is already sorted, making it less efficient for larger lists. Its space complexity is \(O(1)\)because it operates on the original list without needing extra storage.
On the other hand, insertion sort also has a time complexity of \(O(n^2)\).However, it shines when working with partially sorted data due to fewer required movements, making it more efficient in these circumstances compared to selection sort. Its space complexity, too, is \(O(1)\).
Understanding the nuances of these analyses helps in choosing the right algorithm depending on list characteristics and size.

Loop Iteration

Loop iteration is a fundamental part of most sorting algorithms, including selection and insertion sorts. Each iteration moves through the list, making necessary adjustments to sort it. In selection sort, each iteration selects the smallest element and places it at the start of the unsorted section. For example, when starting with the
list

• [6, 5, 4, 3, 7, 1, 2]

the first iteration results in

• [1, 5, 4, 3, 7, 6, 2]

following the swap of '1' with '6'.
In contrast, insertion sort iterates by taking an element from the unsorted section and inserting it into its proper position in the sorted section. As you see from the list, each element
is gradually moved right until it fits correctly, exemplifying this with our second iteration yielding

• [4, 5, 6, 3, 7, 1, 2]

. Loop iterations are central, driving the sorting process forward.

Unsorted List Manipulation

Unsorted list manipulation refers to the handling and reorganization of elements that are out of order. Both selection and insertion sorts demonstrate effective techniques for this task. With selection sort, each element is selected and relocated through a clearly defined and systematic process. It identifies the smallest element, exchanging its position to move towards sorted order. This direct manipulation gets the list sorted methodically.
In the case of insertion sort, manipulation is handled differently. The algorithm works internally building upon an existing portion that is already sorted, thus shifting elements to create a space for new ones in their correct order. This dynamic shaping allows the unsorted portion to seamlessly transition into the sorted part. Hence, both methods collect their capabilities through different strategies but aim for total list organization with precise manipulation.