Given an input array [1, 3, 4, 8, 2, 5, 7, 6], sort the array by Quicksort. Pick

Question

Given an input array [1, 3, 4, 8, 2, 5, 7, 6], sort the array by Quicksort. Pick a median value of three elements from the input array as a pivot: data[0], data[n/2], and data[n-1]. When there are only two elements in a subarray, select the first element as a pivot. Show how the sorting algorithm works as it sorts the input array into ascending order.

I dont need code or a copy paste of what quick sort is.

I keep messing up with it, is the median value 2?
data[0] = 1

data[n/2] = data[8/2] = data[4] = 2

data[n-1] = data[8-1] = data[7] = 6

If thats right how do I show how the algorithm works as it sorts?

          [1, 3, 4, 8, 2, 5, 7, 6]

       [1]                   [3,4,8,5,7,6]

????

Explanation / Answer

yes the median is 2 in the first case..

and yes, you have done quick sort correctly in the second step

it should follow as

[smaller value] [ pivot] [larger value]

step 1 : [1] [2] [3 4 8 5 7 6]

step 2 :

since there is only one element in left we wont do any quicksort operation there,

for the right half

pivot = median(data[0], data[6/2], data [5]) = median(3,5,6) = 5

[1] [2] [3 4] [5] [8 7 6]

step 3 : pivot of 3, 4 = median (data[0] , data [2/2] ,data[1]) = median(3,4,4) = 4

pivot of 8,7,6 =median(data[0] , data[3/2] ,data[2]) = median(8,7,6) = 7

[1] [2] [3] [4] [5] [8 7 6]

[1] [2] [3] [4] [5] [6] [7] [8]

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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