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!
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
QuickSort
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
Quick Sort using Recursive Function
#include <stdio.h>
#include <conio.h>
//Recursive
Function
void
QSort(int a[],int left,int right)
{
int
i,j;
int
x,temp;
i=left;
j=right;
x=a[(left+right)/2];
do
{
while(a[i]
<x&& i <right)
++i;
while(a[j]
>x && j >left)
--j;
if
(i <=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
++i;
--j;
}
}
while(i <=j);
if
(left <j)
QSort(a,left,j);
if
(i <right)
QSort(a,i,right);
}
//Main Function
void
main()
{
int
i,n,num[20];
clrscr();
printf("\nEnter
N Value below 10 : ");
scanf("%d",&n);
printf("\nEnter
%d values in array : \n",n);
for(i=0;i
<n;i++)
{
scanf("%d",&num[i]);
}
printf("\nOriginal
: ");
for(i=0;i
<n;i++)
{
printf("%d
",num[i]);
}
QSort(num,0,n-1);
printf("\nSorted
Values : ");
for(i=0;i
<n;i++)
{
printf("%d
",num[i]);
}
getch();
}
Quick Sort without Recursive Function[ using
Stack]
#include <stdio.h>
#include <conio.h>
#define MIN 10
int list[20];
struct {
int
a,b;
} STK[20];
int top=-1;
//Function for Swap
void
swap(int *x,int *y)
{
int
temp;
temp=*x;
*x=*y;
*y=temp;
}
void
split(int front,int rear,int *sp)
{
int
x,i,j,s,g;
if
(list[front] <list[(front+rear)/2])
{
s=front;
g=(front+rear)/2;
}
else
{
g=front;
s=(front+rear)/2;
}
if
(list[rear] <=list[s])
{
x=s;
}
else if (list[rear] <=list[g])
{
x=rear;
}
else
{
x=g;
}
swap(&list[x],&list[front]);
x=list[front];
i=front+1;
j=rear+1;
while
(i <j)
{
do
{
j--;
} while (list[j]
>x);
do
{
i++;
}
while (list[i] <x);
swap(&list[i],&list[j]);
}
swap(&list[i],&list[j]);
swap(&list[front],&list[j]);
*sp=j;
}
//Function for Push
void
push(int a,int b)
{
top++;
STK[top].a=a;
STK[top].b=b;
}
//Function for Pop
void
pop(int *a,int *b)
{
*a=STK[top].a;
*b=STK[top].b;
top--;
}
void
Isrt(int front,int rear)
{
int
i,j,c;
for
(i=front;i <=rear;i++)
{
j=list[i];
c=i;
while ((list[c-1] >j)&&(c
>front))
{
list[c]=list[c-1];
c--;
}
list[c]=j;
}
}
void qsrt(int n)
{
int
front,rear,sp;
push(0,n);
while
(top!=-1)
{
pop(&front,&rear);
for (;;)
{
if
(rear-front >MIN)
{
split(front,rear,&sp);
if
(rear-sp <sp-front)
{
push(front,sp-1);
front=sp+1;
}
else
{
push(sp+1,rear);
rear=sp-1;
}
}
else
{
Isrt(front,rear);
break;
}
}
}
}
void
main()
{
int
i,n;
clrscr();
printf("\nEnter
Size of Array [Below 20]: ");
scanf("%d",&n);
for(i=0;i
<n;i++)
{
printf("Enter
Element at [%d]: ",i+1);
scanf("%d",&list[i]);
}
printf("\nOriginal
Input : ");
for
(i=0;i <n;i++)
{
printf("
%d",list[i]);
}
qsrt(n-1);
printf("\nAfter
Sort : ");
for
(i=0;i <n;i++)
{
printf("
%d",list[i]);
}
getch();
}
No comments:
Post a Comment