Quick sort is also known as partition exchange sort. Let x be an array and there are n number of elements in the array to be sorted. Choose an element a from a specific position within the array - a may be the first element of the array and place a in its appropriate position (suppose the location is j) of the array such that the following conditions are true:-All the elements of the array within 0 through j-1 is less than or equal to a and all the elements of the array within j+1 through n-1 is greater than a.
So the array is divided into two partitions. The left part contains values less than or equal to a while the right part contains values greater than a. suppose we have a list of 12 numbers like
44 33 11 55 77 90 40 60 99 22 88 66
Let's start with the first number 44. 44 will be placed in its actual location within the array.
Begin with the last number 66 and scan the list from right to left comparing each number with 44.When a number less than 44 is found stop the scan and interchange the positions between the numbers. Here in the list when 22 are reached the scan will stop and 44 and 22 will interchange their positions. So the list will be as follows:-
22 33 11 55 77 90 40 60 99 44 88 66
Note that all the values at the right of 44 are greater than it.
Next start scan from left to right beginning with 22 and stop when a number greater than 44 is found. Interchange their positions. Here in the left to right scan 55 is such a value when the scan will be stoped.So the list at present will be:-
22 33 11 44 77 90 40 60 99 55 88 66
Here also all the values at the left of 44 is less than it.
Next scan again from right to left beginning at 55 and stop when a value less than 44 is found before 44 and then interchange their positions. So after this scan the list will be like:-
22 33 11 40 77 90 44 60 99 55 88 66
Next left to right scan beginning with 40 up to 44 will yield the list as:-
22 33 11 40 44 90 77 60 99 55 88 66
Next scan starts with 77 - from right to left without producing any result.44 is now placed in it actual position and two sub lists are generated. Left sublist is at the left side of 44 and right sub list is at the right of 44.Any sub list containing at least two values will be subjected to the above steps to produce the final result.
Start with 22 33 11 40
11 33 22 40
next scan from left to right upto 11 if any number greater that 22 is found , 33 is found - interchange them
11 22 33 40
scan from right to left to search less value than 22 - not found so the sublist is in sorted order
Next start with the second sublist
90 77 60 99 55 88 66
right scan
66 77 60 99 55 88 90
left scan from 66
66 77 60 90 55 88 99
left scan from 88
66 77 60 88 55 90 99
right scan from 55
66 77 60 55 88 90 99
So 90 is in proper position , right sublist contains only one element so the left sublist will be needs sorting.
66 77 60 55 88
R->L starting from 88
55 77 60 66 88
L->R upto 66
55 66 60 77 88
R->L 60 to 66
55 60 66 77 88
So the final list is completed
Algorithm of Quick sort
Procedure will be called recursively until the array is completely sorted.
QS(Arr,N,Start,End,Loc)
Here Arr is the array with N number of elements. Start and End contains the lower and upper index value of the array or sub list on which the procedure will work. Loc keeps track of the position of the first value of the array sub list during execution. Two local variables Left and Right will contain the boundary values of the sub list that have not been scanned.
Set Left=Start
Set Right=End
Set Loc=Start
[Scan from right to left]
Repeat while Arr [Loc] <=Arr [Right] and Loc! =Right
Right=Right-1
[End of loop]
If Loc=Right
Return
If Arr [Loc]>Arr [Right]
Interchange Arr [Loc] and Arr [Right]
Set Loc=Right
Go to left scan
[End of If block]
[Scan from left to right]
Repeat while Arr [Left] <=Arr [Loc] and Loc! =Left
Left=Left+1
[End of loop]
If Loc=Left
Return
If Arr [Left]>Arr [Loc]
Interchange Arr [Loc] and Arr [Left]
Set Loc=Left
Go to Right scan
[End of If block]
This procedure will set the first value of the array or sub list in its proper position.
Complexity of Quick sort algorithm: - First consider the worst case. It occurs when the list is already sorted. Suppose there is n number of elements in the array, so the list needs n number comparisons to recognize that it remains at the proper location. Now the left sub list will be empty and there will be (n-1) number of elements in the right sublist.So (n-1) comparisons needed for this sub list again and so on. So the total number of comparisons will be
n+ (n-1) + (n-2) +….2+1
=n ((n+1)/2
=n2/2+n/2
O (n2)
Program on Quick Sort
#include
#include
void qS(int array[], int first, int last)
{
int temp, low, high,i,x;
x=array[first];
/*position of this element will be fixed now */
low = first;
high = last;
do
{
while (array[high] > x)
high--;
// right to left
while (array[low] < x)
low++;
// left to right
if (low <= high)
{
temp = array[low];
array[low++] = array[high];
array[high--] = temp;
}
} while (low <= high);
printf("\n**\n");
for(i=0;i<6;i++)
printf("%d ",array[i]);
if (first < high)
qS(array, first, high);
if (low < last)
qS(array, low, last);
}
void main()
{
int values[]={3,2,6,5,4,8}, i;
clrscr();
printf("\n Unsorted list is as follows \n");
for(i=0;i<6;i++)
printf("%d ",values[i]);
qS(values,0,5);
/*passing the lower bound and upper bound as arguments.*/
printf("\n Sorted list as follows\n");
for (i = 0; i < 6; i++)
printf("%d ", values[i]);
getch();
}
Given a list of elements: - 2 51 82 12 31 14 78
Show the steps how the list can be sorted using quick sort algorithm :-
2 (51 82 12 31 14 78 ) right to left upto 2
2 (51 82 12 31 14 78 ) left to right upto 2
2 (14 82 12 31 51 78 ) right to left upto 51
2 14 51 12 31 82 78 left to right upto 51
2 14 31 12 51 82 78 right to left upto 51
2 14 31 12 51 82 78 left to right upto 51
So 51 is now placed in proper position
Start with the left sub list
14 31 12 left to right
12 31 14 right to left
12 is in proper position
31 14 right to left
14 31 left to right
14 31
So from left up to 51 the list is as follows
2 12 14 31 51
Now start with the right sub list
81 78 right to left
78 81 left to right
2 12 14 31 51 78 82
No comments:
Post a Comment