About myself,
I am K.Mohana Devi.
I was completed my undergraduation at Lady Doak College, Madurai.
Now doing my post graduation M.C.A at Thiagarajar College of Engineering, Madurai.
This is my first blog creation..
This blog is about the quick sort technique..
Through this blog contents we can understand all about the quick sort technique..
QUICK SORT
The quick sort algorithm was developed in 1960 by Tony Hoare
while in the Soviet Union,
as a visiting student at Moscow State University. At that time, Hoare worked in a
project on machine translation for the National Physical Laboratory. He developed the algorithm in
order to sort the words to be translated, to make them more easily matched to
an already-sorted Russian-to-English dictionary that was stored on magnetic
tape.
Quick sort gained widespread adoption, appearing, for example, in Unix
as the default library sort function, hence it lent its name to the C standard library function q sort
and in the reference implementation of Java. It was analyzed extensively by Robert Sedge wick, who wrote his Ph.D. thesis about
the algorithm and suggested several improvements.
QUICK SORT ALGORITHM WITH AN EXAMPLE:
Full example of quick sort on a random set of numbers. The shaded element is
the pivot. It is always chosen as the last element of the partition. However,
always choosing the last element in the partition as the pivot in this way
results in poor performance (O(n²)) on already sorted
arrays, or arrays of identical elements. Since sub-arrays of sorted / identical
elements crop up a lot towards the end of a sorting procedure on a large set,
versions of the quick sort algorithm which choose the pivot as the middle
element run much more quickly than the algorithm described in this diagram on
large sets of numbers.
Quick sort is a divide and conquer algorithm. Quick sort first divides a large
array into two smaller sub-arrays: the low elements and the high elements.
Quick sort can then recursively sort the sub-arrays.
The
steps are:
- Pick an element, called a pivot,
from the array.
- Reorder the array so that all
elements with values less than the pivot come before the pivot, while all
elements with values greater than the pivot come after it (equal values
can go either way). After this partitioning, the pivot is in its final
position. This is called the partition operation.
- Recursively apply the above steps to the
sub-array of elements with smaller values and separately to the sub-array
of elements with greater values.
The base case of the recursion is arrays of size zero or one, which never
need to be sorted. In pseudo code,
a quick sort that sorts elements i through k (inclusive) of an array A can be
expressed compactly as
ALGORITHM:
Partition (A, left, right)
Pivot = choose first element (A, left, right)
For l = left to right
If pivot < a[l] break
For r = right to left
If pivot > a[r] break
If l < r
Swap A[l] & A[r]
Else
Swap A[r] & pivot
Return
QUICK
SORT (ANOTHER TYPE):
- 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)
Note: that
to sort entire array, the initial call Quick Sort (A, 1, length[A])
As a first step, Quick Sort chooses as pivot one of the items in the array to
be sorted. Then array is then partitioned on either side of the pivot. Elements
that are less than or equal to pivot will move toward the left and elements
that are greater than or equal to pivot will move toward the right.
PARTITIONING
THE ARRAY:
Partitioning procedure rearranges the subarrays in-place.
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
Partition selects the first key, A[p] as a pivot
key about which the array will partitioned:
Keys
≤ A[p] will be moved towards the left .
Keys ≥ A[p] will be moved towards the right.
Keys ≥ A[p] will be moved towards the right.
The running time of the partition procedure is (n) where n = r - p +1 which
is the number of keys in the array.
Another
argument that running time of PARTITION on a subarray of size (n) is
as follows: Pointer i and pointer j start at
each end and move towards each other, conveying somewhere in the middle. The
total number of times that i can be incremented and j can
be decremented is therefore O(n). Associated with each increment or
decrement there are O(1) comparisons and swaps. Hence, the total time
is O(n).
ARRAY
OF SAME ELEMENTS:
Since all the elements are equal, the “less than or equal” teat in lines 6 and
8 in the PARTITION (A, p, r) will always be
true. this simply means that repeat loop all stop at once.
Intuitively, the first repeat loop moves j to the left; the
second repeat loop moves i to the right. In this case, when
all elements are equal, each repeat loop moves i and j towards
the middle one space. They meet in the middle, so q= Floor(p+r/2).
Therefore, when all elements in the array A[p . . r] have
the same value equal to Floor(p+r/2.
C Program for Quick Sort :
void
quicksort(int [10],int,int);
int
main(){
int x[20],size,i;
printf("Enter size of the array: ");
scanf("%d",&size);
printf("Enter %d elements: ",size);
for(i=0;i<size;i++)
scanf("%d",&x[i]);
quicksort(x,0,size-1);
printf("Sorted elements: ");
for(i=0;i<size;i++)
printf(" %d",x[i]);
return 0;
}
void quicksort(int x[10],int first,int last){
int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
{
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j)
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
The running time of quick sort depends on whether partition
is balanced or unbalanced, which in turn depends on which elements of
an array to be sorted are used for partitioning.
A very good partition splits an array up into two equal sized arrays. A bad
partition, on other hand, splits an array up into two arrays of very different
sizes. The worst partition puts only one element in one array and all other
elements in the other array. If the partitioning is balanced, the Quick sort
runs asymptotically as fast as merge sort. On the other hand, if partitioning
is unbalanced, the Quick sort runs asymptotically as slow as insertion sort.
ADVANTAGES OF QUICK SORT:
- It is in-place since it uses
only a small auxiliary stack.
- It requires only n log(n) time
to sort n items.
- It has an extremely short inner
loop
- This algorithm has been
subjected to a thorough mathematical analysis, a very precise statement
can be made about performance issues.
DISADVANTAGES OF QUICK SORT:
- It is recursive. Especially if
recursion is not available, the implementation is extremely complicated.
- It requires quadratic (i.e., n2)
time in the worst-case.
- It is fragile i.e., a simple
mistake in the implementation can go unnoticed and cause it to perform
badly.
Finally, Quick sort is an in place sorting algorithm whose worst-case running
time is (n2)and expected running time is (n lg n) where
constants hidden in (n lg n) are small.
