What three conditions must be satisfied in order to solve the critical section problem?
1 answer:
You might be interested in
Solution :
Initial array =
(length of the array)
Iteration:
i = 1
j = 1
= C
a[j] = Q
since < 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