Quick Sort
Quicksort is a divide and conquer algorithm which relies on a partition
operation: to partition an array, we choose an element, called a pivot, move
all smaller elements before the pivot, and move all greater elements after it.
This can be done efficiently in linear time and in-place. We then recursively
sort the lesser and greater sublists. Efficient implementations of quicksort
(with in-place partitioning) are typically unstable sorts and somewhat complex,
but are among the fastest sorting algorithms in practice. The most complex
issue in quicksort is choosing a good pivot element; consistently poor choices
of pivots can result in drastically slower O(n²) performance, but if at each
step we choose the median as the pivot then it works in O(n log n). Finding the
median, however, is an O(n) operation on unsorted lists, and therefore exacts
its own penalty.
·
Quick Sort
Analysis
§ Base case: Return if number of elements is 0 or 1
§ Pick pivot v in S.
§ Partition into two subgroups. First subgroup is < v
and last subgroup is > v.
§ Recursively quick sort first subgroup and last subgroup
§ Picking the pivot
§ Choose first element
§ Bad for presorted data
§ Choose randomly
§ Random number generation can be expensive
§ Median-of-three
§ Choose median of left, right, and center
§ Good choice!
Workout
Original
: 5 7 3 8 6
Left
=0
Right
=4
Pivot
=a[(Left + Right )/2]
Pivot
= 3
i=Left
j=Right
Pivot
= 3
Pass = 1
a[i]
5 a[j] 3 i 0 j 2
a[i] not Less than Pivot
a[j]>Pivot
j—
a[j]>Pivot
j—
Swap between a[i] ↔
a[j]
a[i] 3 a[j] 5 i 0 j 2
Values
after Pass -1
3 7 5 8 6
Left = 1
Right = 4
Pivot
= 5
Pass = 2
i =1
j = 4
a[i]
<Pivot i++
a]j]>Pivot
j—
a]j]>Pivot
j—
a[i] 7 a[j]
5 i 1
j 2
Swap between a[i] ↔ a[j]
a[i] 5 a[j] 7 i 1 j 2
Values
after Pass -1
3 5 7 8 6
Left
=2
Right
= 4
i=2
J=4
Pivot
= 8
Pass = 3
a[i]
<Pivot i++
a[i]
8 a[j] 6 i 3 j 4
Swap between a[i] ↔
a[j]
a[i] 6 a[j] 8 i 3 j 4
Values
after Pass -1
3 5 7 6
8
Left = 2
Right = 3
Pivot
= 7
Pass = 4
i=2
j=3
a[i]<Pivot && i<j
a[i] 7 a[j] 6 i 2 j 3
Swap between a[i] ↔
a[j]
a[i] 6 a[j] 7 i 2 j 3
Values after Pass -1
3 5 6 7
8
Sorted
Values : 3 5 6 7 8
Complexity
·
Quick sort relation
§ T(N) = T(i) + T(N-i-1) + cN
·
Worst-case – pivot always smallest element
§ T(N) = T(N-1) + cN
§ T(N-1) = T(N-2) + c(N-1)
§ T(N-2) = T(N-3) + c(N-2)
§ T(2) = T(1) + c(2) – add previous equations
§ T(N) = T(1) + csum([2-N] of
i) = O(N2)
·
Best-case – pivot always middle element
§ T(N) = 2T(N/2) + cN
§ Can use same analysis as mergesort
§ O(NlogN)
·
Average-case
§ O(NlogN)
Algorithm
QuickSort(A,
left, right)
- if left >= right return
- else
- middle = Qsort(A, left, right)
- QuickSort(A, left, middle–1 )
- QuickSort(A, middle+1, right)
- end if
Qsort(A,
left, right)
- x = A[left]
- i = left
- for j = left+1 to right
- if A[j] < x then
- i = i + 1
- swap(A[i], A[j])
- end if
- end for j
- swap(A[i], A[left])
- return i
Pseudo code
If p
< r then
q Partition (A, p, r)
Recursive call to Quick Sort (A, p, q)
Recursive call to Quick Sort (A, q + r, r)
PARTITION (A, p, r)
x ← A[p]
i ← p-1
j ← r+1
while TRUE
do
Repeat j ← j-1
until A[j] ≤ x
Repeat i ← i+1
until A[i] ≥ x
if i < j
then exchange A[i] ↔ A[j]
else return j
Source Code
//quick
sort in Java
import
java.io.*;
public class Qsort
{
//Recursive Function
void Sort(int Arr[],int left,int
right)
{
int i,j,temp;
i=left;
j=right;
int N=Arr[(left+right)/2];
do
{
while(Arr[i]<N
&& i<right)
{
++i;
}
while(Arr[j]>N
&& j>left)
{
--j;
}
if (i<=j)
{
temp=Arr[i];
Arr[i]=Arr[j];
Arr[j]=temp;
++i;
--j;
}
} while(i<=j);
if (left<j)
{
Sort(Arr,left,j);
}
if (i<right)
{
Sort(Arr,i,right);
}
}
void Disp(int Arr[])
{
for(int i=0;i<Arr.length;i++)
{
System.out.print(Arr[i]+" ");
}
}
public static void main(String
args[])throws IOException
{
Qsort Qs=new Qsort();
BufferedReader Br=new
BufferedReader(new InputStreamReader(System.in));
int i;
System.out.print("\n\tEnter size of array : ");
int
Size=Integer.parseInt(Br.readLine());
int Arr[]=new int[Size];
for(i=0;i<Size;i++)
{
System.out.print("\tEnter Element at Arr["+i+"] :
");
Arr[i]=Integer.parseInt(Br.readLine());
}
System.out.print("\n\tOriginal ");
Qs.Disp(Arr);
Qs.Sort(Arr,0,Size-1);
System.out.print("\n\tAter
Sort : ");
Qs.Disp(Arr);
}
}
Output
Enter size of array : 5
Enter Element at Arr[0] : 5
Enter Element at Arr[1] : 7
Enter Element at Arr[2] : 3
Enter Element at Arr[3] : 8
Enter Element at Arr[4] : 6
Original 5 7 3 8 6
Ater Sort : 3 5 6 7 8
No comments:
Post a Comment