1. Selection sort is a popular sorting algorithm. The algorithm works as follows

Question

1. Selection sort is a popular sorting algorithm. The algorithm works as follows: 1).Find the minimum value in the list. 2). Swap it with the value in the first position. 3). Repeat the steps above for the remainder of the list. Below is is a pseudo code fo the algorithm.

input : An Array A of numbers

output: Array A sorted

1.1 //A.length is the length of the array A;

1.2 for i <-- 0 to A.length do

1.3 int indexOfMin = i;

1.4 int min = A[i];

1.5 for j <-- i + 1 to A.length do

1.6 if A[j] < min then

1.7 indexOfMin = j;

1.8 min = A[j];

1.9 end

1.10 end

1.11 //swap A[indexOfMin] and A[i];

1.12 A[indexOfMin] = A[i];

1.13 A[i] = min;

1.14 end

1.15 return A

(a) Use a small example, (e.g.,"3 1 4 5 2") to show how the algorithm works. Specifically, write down the contents of array A each time after line 1.13 is executed.

(b) Which line of the program will be executed the most number of times?

(c) For an input array of size n, how many times the line you choosein (b) will be executed in the best case? How about in the worst
case?

Explanation / Answer

a) 1 3 4 5 2

1 2 4 5 3

1 2 3 5 4

1 2 3 4 5

b) 1.5

c) Best case, Worst case : n times. Same for both.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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