Question

Selection Sort List the resulting array after each iteration of the outer loop of the selection sort algorithm. Indicate the number of character-to-character comparisons made for each iteration (line 07 of the Selection Sort algorithm at the end of the assignment). Sort the following array of characters (sort into alphabetical order): CQS A XBT Selection Sort 01 public static void selectionSort (int[] a) { 02 03 int n = a.length; for (int i = 0 ; i 0; j--) { if ( a[j-1] > a[j] ) { exchange(a, j-1, j); } else break; 10 } 12 private static void exchange (int[] a, int i, int j) { 13 // exchange the value at index i with the value at index j int temp = a[i]; a[i] = a[j]; a[j] = temp; 17 }

Answer 1

Initial array =
`$\text{C,Q,S,A,X,B,T}$`

`$n= 7$`(length of the array)

`$\text{1st}$` Iteration:

i = 1

j = 1

`$\text{a[j-1]}$` = C

a[j] = Q

since
`$\text{a[j-1]}$` < a[j] , break from inner loop

Number of comparisons in 1st Iteration = 1

After 1st Iteration:

Array : C,Q,S,A,X,B,T

2nd Iteration:

i = 2

j = 2

a[j-1] = Q

a[j] = S

since a[j-1] < a[j], break from inner loop

Number of comparisons in 2nd Iteration = 1

After 2nd Iteration:

Array : C,Q,S,A,X,B,T

3rd Iteration:

i = 3

j = 3

a[j-1] = S

a[j] = A

since a[j-1] > a[j], exchange a[2] with a[3]

Array : C,Q,A,S,X,B,T

j = 2

a[j-1] = Q

a[j] = A

since a[j-1] > a[j], exchange a[1] with a[2]

Array : C,A,Q,S,X,B,T

j = 1

a[j-1] = C

a[j] = A

since a[j-1] > a[j], exchange a[0] with a[1]

Array : A,C,Q,S,X,B,T

j = 0, break from inner loop

Number of comparisons in 3rd Iteration = 3

After 3rd Iteration:

Array : A,C,Q,S,X,B,T

4th Iteration:

i = 4

j = 4

a[j-1] = S

a[j] = X

since a[j-1] < a[j], break from inner loop

Number of comparisons in 4th Iteration = 1

After 4th Iteration:

Array : A,C,Q,S,X,B,T

5th Iteration:

i = 5

j = 5

a[j-1] = X

a[j] = B

since a[j-1] > a[j], exchange a[4] with a[5]

Array : A,C,Q,S,B,X,T

j = 4

a[j-1] = S

a[j] = B

since a[j-1] > a[j], exchange a[3] with a[4]

Array : A,C,Q,B,S,X,T

j = 3

a[j-1] = Q

a[j] = B

since a[j-1] > a[j], exchange a[2] with a[3]

Array : A,C,B,Q,S,X,T

j = 2

a[j-1] = C

a[j] = B

since a[j-1] > a[j], exchange a[1] with a[2]

Array : A,B,C,Q,S,X,T

j = 1

a[j-1] = A

a[j] = B

since a[j-1] < a[j], break from inner loop

Number of comparisons in 5th Iteration = 5

After 5th Iteration:

Array : A,B,C,Q,S,X,T

6th Iteration:

i = 6

j = 6

a[j-1] = X

a[j] = T

since a[j-1] > a[j], exchange a[5] with a[6]

Array : A,B,C,Q,S,T,X

j = 5

a[j-1] = S

a[j] = T

since a[j-1] < a[j], break from inner loop

Number of comparisons in 6th Iteration = 2

After 6th Iteration:

Array : A,B,C,Q,S,T,X

Sorted Array : A B C Q S T X