Interview Preparation Quick Sort
From Embedded Systems Learning Academy
Revision as of 12:38, 25 November 2016 by Proj user18 (talk | contribs) (Created page with "Algorithm for implementation of quick sort is as follows a. Any element can be marked as a pivot but in this algorithm, I am using the starting index as a pivot. b. Divide...")
Algorithm for implementation of quick sort is as follows
a. Any element can be marked as a pivot but in this algorithm, I am using the starting index as a pivot.
b. Divide the array such that, All the element that are less than pivot are kept in one part and other are kept in another part.
c. Now pivot can be placed at its position between two parts.
d. consider only left part and repeat the step b and c until only one element is left.
e. consider right part and repeat step b,c,d and e until all the elements are sorted.
For an array with n number of elements,
Best case complexity = Average case complexity = O(n log n).
Worst case complexity = O(n^2).
