Quick Sort

 
Quick sort is the most preferred sorting algorithm which is based on the fact that it is faster and easier to sort two small arrays than to sort one long array.Quick sort is also known as partition exchange sort.The basic strategy of quick sort is divide and conquer.

Complexity : 

Algorithm Worst Case Average Case Best Case
Quick Sort O(n2) O(n log n) O(n log n)

Algorithm :
Step 1 : Choose a pivot element.
Step 2 : Based on pivot element divide the array into smaller sub arrays.One sub array has all values greater than pivot and another sub array with all values less than equal to pivot element.
Step 3 : Keep on repeating step 2 and step 3 to further sub arrays.Eventually you will get the array sorted.

Question : Given an array.Sort the array using Quick Sort technique ?

Solution : The problem is solved in recursive way.

Explanation :

Original array :

 3  5  1  2  7  9  6  8  10  4

pivot element : 3

begin=1

end=9

To dive the array ,two index variables begin and end are chosen such that begin points to 1st element i.e 5 and end refers to (arr.length-1)th elements i.e. 4.

The job of index variable begin is to find an element greater that 0th position element or pivot element 3.So begin is incremented by 1 till the value stored at begin is greater than 0th element.

The job of index variable end is to find an element lower than 0th position element or pivot element 3.So begin is incremented by 1 till the value stored at begin is lower than 0th element.

When these elements are found ,they are interchanged.Again from the current positions begin and end are incremented and decremented respectively and swappings are done whenever condition meets.

The process ends whenever the index pointers meets or crossover.At that point the whole array is divided into 2 parts where the first part is having all elements less than pivot element and the other part is having all elements greater than pivot element.

Algorithm internal Working Output:

3 5 1 2 7 9 6 8 10 4
1 2 3 5 7 9 6 8 10 4
1 2 3 5 7 9 6 8 10 4
1 2 3 4 5 9 6 8 10 7
1 2 3 4 5 7 6 8 9 10
1 2 3 4 5 6 7 8 9 10


Program :

 
 


Leave a comment

Your email address will not be published. Required fields are marked *

eighteen + 3 =