Question

6) Assume that we are using quick sort algorithm to sort the following elements in the array 26, 15,30,11,8,17 22, 40, 4, 10. Use the first element in the array as pivot. (20 pts.) 1- How total iterations it would take to complete the sorting process? 2- Simulate the entire sorting process. (If you need additional space, complete it at the other side of the paper) public static void quick_sort(intl] a, int left, int right) if (left < right) ( int j = partition( a, left, right); quick_sort (a, left, j 1); quick_sort (a, j 1, right); Total iterations:

Answer 1

In quick sort we move the smaller element to the left of pivot and larger element to the right of pivot. Below we have taken i=0 and j=9(both are index position from left and right end of array).

We keep incrementing “i” till we find and element greater than pivot element(i.e 26) and keep decrementing “j” till we find an element smaller than pivot(26). The point where “i>j” then that value of “j” is the position index of pivot element. So we will be having all smaller number than pivot on left and larger on right.

26

15

30

11

8

17

22

40

4

10

i=0                                                                                                                                                    j=9

Now,i=2(i.e.30) is greater than 26 and j=9(i.e.10) is smaller than 26. So swap them.

26

15

10

11

8

17

22

40

4

30

   i=2 j=9

Now,i=7(i.e.40) is greater than 26 and j=8(i.e.4) is smaller than 26. So swap them.

26

15

10

11

8

17

22

4

40

30

                                                                                                                    i=7             j=8

Now,further increasing “I” and decreasing “j” will make “i>j” so the position of pivot = position of j and so swap the element.

4

15

10

11

8

17

22

26

40

30

Now position of pivot is sorted and the element left of it are all smaller and right of it are largerer than pivot(i.e. 26). Now we will divided the array in 2 sub parts.

4

15

10

11

8

17

22

And

40

30

Now using the same logic as above we need to sort these 2 sub array.

Considering the 1^st array and 1^st element as pivot(i,e .4). In below array it is not possible to swap the pivot as pivot is already sorted .So we will consider 15 as pivot.

4

15

10

11

8

17

22

i=0                                                                                                                                                          j=6

So we will consider 15 as pivot.

4

15

10

11

8

17

22

                              I=0                                                                                                                     j=5

Next Swap:

4

8

10

11

15

17

22

Now above sub array is sorted. Similarly the other sub array will be sorted in 1 run so final array after

5 iteration will be:

4

8

10

11

15

17

22

26

30

40

Total 11 times partition method is called.