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

Solution :

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