Illustrate the execution of QuickSort on the array A64985101

Illustrate the execution of QuickSort on the array A=6,4,9,8,5,10,1,3. descriptive as possible.

Solution

Quicksort is like the merge sort and it is based on the divide-and-conquer paradigm. The Steps involved in quick sort are

1) Choose a Pivot element, we take the middle of the array as the pivot element.

2) Partition Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array.

3) Sort Both Parts applying the quick sort recursively on both left and right parts.

Inorder to explain it on the given array

A= 6,4,9,8,5,10,1,3           // Let 5 be the pivot element

3,4,9,8,5,10,1,6                 // 6 > 5 > 3.. So we swaped 6 with 3..

3,4,1,8,5,10,9,6                //9 > 5 > 1. So we swappaed 9 with 1

This is the First step. We need to run it recursively until elements less than 5 are on left side and greater then 5 on right side. Then we need to follow same steps on both left and right side until we get the sorted array as

1,3,4,6,8,9,10