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
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput