Question
The idea behind the selection sort is very similar to bubble sort. The selection sort works by first finding the smallest item in the list,
The idea behind the selection sort is very similar to bubble sort. The selection sort works by first finding the smallest item in the list, then placing it at the beginning of the array. Next time, it will find the next smallest item and place it at position two. The main difference is that instead of swapping as soon as it finds an element that is smaller, it just remembers where the smallest item is, and when it reaches the end, it places that item at the appropriate position (1st or 2nd, etc).
Since you dont initially know what the smallest element is, we always just start by picking the first item. Once we find the smallest item location, we just swap it with that first item. Next time, we would start by picking the second item in the list (since the first one is already in the correct place). We repeat this until we reach the end of the list.
Heres an illustration:
Array: [5, 1, 10, 3]
1: Smallest position = 1
2: Compare with element 2
3: Smallest position = 2
4: Compare with the rest; no changes
5: Swap element at position 1 with element at position 2
Repeat 1 - 5, starting at position 2
Tips: Think about how many times you will need to move the smallest element in the list to the front (or to the proper position) before it is in order. If it helps, do an example with a small list of just 4 5 numbers.
Algorithm: (I am using indentation to indicate blocks or units that belong together)
1: function selection_sort (array A: unsorted array of integers); returns an array sorted in ascending order
2:
3:
4: for m from n+1 to size of A
5: if A(m) < A(smallest_element_position)
6:
7: swap A(n) with A(smallest_element_position)
8: return sorted A
1)What should the second step of this algorithm be?
a.smallest_element_position = 1
b.for n from 1 to size of A
c.for n from 1 to size of A 1
d.for n from 2 to size of A
2)What should step 3 of this algorithm be?
a.smallest_element_position = n
b.for n from 1 to size of A
c.for n from 1 to size of A 1
d.for n from 2 to size of A
3)What should step 6 of this algorithm be?
a.smallest_element_position = m
b.A(m) = A(smallest_element_position)
c.smallest_element_position = n
d.A(m) = A(n)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started