The Gateway to Computer Science Excellence
0 votes
443 views
A list of elements are given A - <3,1,4,1,5,9,2,6,5,3,5,8,9 >

Show Howw the "Pivot" and quick sort algorithm work.

finally show the Best Case analysis for quick sort .
in Algorithms by Active (3.7k points) | 443 views

2 Answers

+1 vote
Best answer
3,1,4,1,5,9,2,6,5,3,5,8,9

We'll choose arr[0] as pivot.
Now take two variables, say i and j.

j will point to the next < element than arr[0] from right.
i will point to the next >= element than arr[0] from left

so.. j will point to '2'
i will point to '4'.
SWAP

[3] 1,2,1,5,9,4,6,5,3,5,8,9
      ^       ^   
      i       j
continue till j-i > 0.
so j will be at '1' when i moves to '1' j-i = 0 and loop breaks.

SWAP arr[j] with arr[0]

1,1,2 (3) 5,9,4,6,5,3,5,8,9
       ^
       j

So, we see we have two sub-array partitions. 0 to j-1 and j+1 to n-1
Repeat and see what you get. :)

Best case for quick sort can be performed with a check that after a single pass if any swap is happening.
If not, then it is sorted, no need to go further.

Ex: 1,2,3,4,5,6

j starts from '6' and crosses i that is in '2'.
No swaps performed. So, sorted.
Quick Sort can be modified like this to give best case as O(n).

However in the traditional algorithm you have to go on partitioning to find it at O(nlog(n))
by (351 points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,708 users