Let Xij =I { zi is compared to zj in quick sort algorithm} is an indicator variable, and zi is the ith smallest number.
Which of the following sequence of the numbers give the X2,5 = 1?
Note: Assume that there is a divide and conquer quick sort algorithm and in partition algorithm the first element of the lists is taken as pivot-element.
1
40, 50, 10, 20, 30
2
10, 20, 50, 30, 40
3
40, 20, 10, 30, 50
4
30, 20, 10, 40, 50