The idea behind the selection sort is very similar to bubble sort. The selection

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, 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 don’t 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.

Here’s 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)How would you write step 4 in MATLAB?

a.for (n+1):length(A)

b.for m = (n+1):length(A)

c.for m = n+1:A

d.for m = (n+1):size(A)

2)How would you write step 7 in MATLAB?

a.A(n) = A(smallest_element_position)

b.A(n) = A(smallest_element_position)
A(smallest_element_position) = A(n)

c.temp = A(n)
A(n) = smallest_element_position
smallest_element_position = A(n)

d.temp = A(n)
A(n) = A(smallest_element_position)
A(smallest_element_position) = temp

Explanation / Answer

1. (b) for m = (n+1):length(A) is the correct syntax for a for loop that runs from n+1 to the length of matrix a.

2. (d) temp = A(n)
A(n) = A(smallest_element_position)
A(smallest_element_position) = temp

This is the correct syntax for line 7.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.