Scribd
Upload
6 views15 pages

QuickSort Algorithm with Pivot Partitioning

The document describes a quicksort algorithm that uses a pivot element to partition an array into two sub-arrays, where elements in the left sub-array are less than the pivot and those in the right are greater. It outlines the process of the partitioning function (PA) and the recursive quicksort function (QS). The average case time complexity is O(n log n), while the worst case is O(n^2) when the array is sorted in ascending order.

Uploaded by

vj2713
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
6 views15 pages

QuickSort Algorithm with Pivot Partitioning

The document describes a quicksort algorithm that uses a pivot element to partition an array into two sub-arrays, where elements in the left sub-array are less than the pivot and those in the right are greater. It outlines the process of the partitioning function (PA) and the recursive quicksort function (QS). The average case time complexity is O(n log n), while the worst case is O(n^2) when the array is sorted in ascending order.

Uploaded by

vj2713
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

WE FIND a element called pivot, that partition that Partition the array into two halves in such a way

that the elements in left the sub-array are less than the pivot element and the elements in right sub-array are greater than the pivot element

Begin If (lb < ub) then Call PA(a,lb,ub,loc) Call QS(a,lb,loc-1); Call QS(a,loc+1,ub);

PA(a,beg,end,loc) Begin Set left=beg,right=end,loc=beg Set done=false While(not done) do While(a[loc] <=a[right] and loc!=right) Set right=right-1 EndWhile If(loc=right) then Set done=true Elseif (a[loc] >a[right]) then InterChange a[loc] and a[right] Set loc=right End if

If(not done) then While(a[loc] >=a[left] and loc!=left) Set left=left+1 EndWhile If(loc=left) then Set done=true Else if (a[loc] <a[left]) then Interchange a[loc] and a[left] Set loc=left End if End if End while End

25 10 30 15 20 28
Loc left

RIGHT

25 10 30 15 20 28
Loc left

RIGHT

20 10 30 15 25 28
LOC RIGHT

left

20 10 30 15 25 28
LOC RIGHT

left

20 10 30 15 25 28
LOC RIGHT

left

20 10 25 15 30 28
LOC left

RIGHT

20 10 25 15 30 28
LOC left RIGHT

250 10 15 25 30 28
LOC RIGHT

left

20 10 15 25 30 28
LOC RIGHT
left

20 10 15
LEFT SUB ARRAY

AND

30 28
RIGHT SUB ARRAY

O(n log2n) AVERAGE CASE

O(n2) WORST CASE (ASCENDING ORDER)

You might also like