1 Sort the sequence 2 6 9 5 1 3 4 7 8 using quicksort that s

1. Sort the sequence 2, 6, 9, 5, 1, 3, 4, 7, 8 using quicksort that selects the middle element as pivot (round down in the case of inputs of even size). Show the state of the array after each recursive level of the quicksort execution, marking the chosen pivot and the sorted part at each step.

2.  Show how insertion sort sorts the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5.

Solution

Insertion sort compare elements to the left and right and if any lesser value is found internchange.Keep it repeating until full list is sorted.

a) 3, compare with 1 3>1 hence replace

1,3,4,1,5,9,2,6,5

b) 3, left compare with 1 and right comapre with 4 1<3<4 hence no interchange.

1,3,4,1,5,9,2,6,5

c) 4, compare to left and right 3<4>1 hence replace 4 and 1

1,3,1,4,5,9,2,6,5

d) 5---> 4<5>5, interchange 5 &2

1,3,1,4,2,5,9,6,5

e) 9--> compare 5<9>6 interchange 9 and 6

1,3,1,4,2,5,6,9,5

f) 5---compare 9>g interchange 9 and 5

1,3,1,4,2,5,6,5,9

g) again start from first index

1--1>3 no change

h) 3...1<3>1 interchange 1 and 3

1,1,3,4,2,5,6,5,9

i) 4--> 3<4>2

1,1,3,2,4,5,6,5,9

j) 4-- 4<5<6 no change

k)6 -- 5<6>5 interchange

1,1,3,2,4,5,5,6,9

l) 9--> 6<9 no change.

Again start from first

m) 1--> 1>1 no change

1,1,3,2,4,5,5,6,9

n) 3--> 1<3>2 interchange

1,1,2,3,4,5,5,6,9

o) 4--> 3<4<5 no change

p) 5--> 4<5<=5 no change

q) 5--> 5<=5<6 no change

r) 6--> 5<6<9no change

s) 9--> 6<9 no change

Hence after soring sequence of elemenst is 1,1,2,3,4,5,5,6,9