Friday, 1 December 2017

Explain the algorithm for Quick Sort Algorithm.

Quick sort is based on partition. It is also known as partition exchange sorting. The basic concept of quick sort process is pick one element from an array and rearranges the remaining elements around it. This element divides the main list into two sub lists. This chosen element is called pivot. Once pivot is chosen, then it shifts all the elements less than pivot to left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element. 

Algorithm for Quick Sort:
It is also known as partition exchange sort. It was invented by CAR Hoare. It is based on partition. The basic concept of quick sort process is pick one element from an array and rearranges the remaining elements around it. This element divides the main list into two sub lists. This chosen element is called pivot. Once pivot is chosen, then it shifts all the elements less than pivot to left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element.
quicksort(q)
varlist less, pivotList, greater
if length(q) ≤ 1
return q
select a pivot value pivot from q
for each x in q except the pivot element
if x < pivot then add x to less
if x ≥ pivot then add x to greater 
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))

Time Complexity of Quick Sort:
Best case : O(nlogn)
Average case : O(nlogn)
Worst case : O(n2)

Advantages of Quick Sort:
1. This is faster sorting method among all.
2. Its efficiency is also relatively good.
3. It requires relatively small amount of memory.

Disadvantages of Quick Sort:
1. It is complex method of sorting so, it is little hard to implement than other sorting methods.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput