QUICK SORTING: – Quick Sort is an algorithm that also likes to merge sort and uses the idea of divide and conquers. This algorithm finds the element that divides (splits) the array into halves in such a way that the elements in the left sub-array are less than and the elements in the right sub greater than the dividing (splitting) element. Then these two – sub-arrays are sorted separately. This procedure is recursive.
The main task in quick sort is to find the element that divides the array into halves and to place it at its proper location in the array. Usually, the procedure places the first element in the array at its final position. To find the location of the element that splits the array into two sections is an O (N) operation because every element in the array is compared to the dividing element. After the division each section is examined separately if the array is split approximately Vin half (which is not usually), then there will be log2n splits.
Quick sort is sensitive to the order of the input data and it gives the worst-case performance when the elements are already in ascending or descending order Then it divides the array into sections of 1 and n – 1 element in each call. Thus. there will be n – 1 division in all. The efficiency of quick sort is affected by the initial order of elements, This sort is also called partition exchange sort.
The quick sort has the property that it works best for files that are ” completely unsorted and worst for files that are completely sorted. The situation is precisely the opposite for the bubble sort, which works best for sorted files and worst for unsorted files. It is possible to speed up quick sorting for sorted files by choosing a random element of each sub-file as the pivot value.
If a file is known to be nearly sorted this might be a good strategy (although in that case choosing the middle element as a pivot would be even better). However, if nothing is known about the file such a strategy does not improve the worst-case behavior since it is possible (although improbable) that the random element chosen each time might consistently be the smallest element of each sub-file.
As a practical matter, sorted files are more common than a good random number generator happening to choose the smallest, element repeatedly. The analysis for the case in which the file size is not an integral power is similar but slightly more complex the results however remain the same. It can be shown however that on average (over all files of size n) the quick sort makes approximately 1.386n Log2n comparisons even in its unmodified version.
Because of its low overhead and its practical situations, quick sort is often the fastest average O (N log N) behavior. The space nested recursion calls or the size of treatments for the quick sort depend on the number of The reason for this is that a smaller sub-array will be divided fewer times than a larger sub-array of course, the larger sub-array will ultimately be processed, and subdivided but this will occur after the smaller sub-arrays have already been sorted and therefore removed from the stack.
Another advantage of quick sorting is the locality of reference. That is over a short period of time all array accesses are to one or two relatively small portions of the array (a sub-file or portion thereof) This ensures efficiency in the virtual memory environment where pages of data are constantly being swapped back and forth between external and internal storage. The locality of reference results in fewer page swaps being required for a particular program A simulation study has shown that environment quick sort uses fewer space-time resources than any other sort considered. As such, The efficiency can be improved by:
- Choosing a better pivot element.
- Using a better algorithm for small sub-lists.
- Eliminating recursion.
Algorithm for Quick sorting in c programming.
QUICKSORT (A, LB, UB)
Here A is an array with LB lower bound and UB upper bound. This algorithm sorts the A array in ascending order.
1. Set MID = 0.
2. If LB > = UB, then Return.
3. [Calling of Partition Function].
Call PARTITION (A, LB, UB, MID).
4. [Calling of Quick sort Function].
Call QUICKSORT (A, LB, MID – 1).
5. [Calling of Quick sort Function]
Call QUICKSORT (A, MID + 1. UB).
6. Return
PARTITION (A, LB, UB, MID)
Here A is an array with LB lower bound and UB upper bound. This algorithm assigns the mid value of the total elements in the array in the MID.
1. Set DOWN = LB
2. Set UP = UB
3. Set PIVOT = A [DOWN]
4. Repeat Steps 5 to 9 While DOWN < UP
5. Repeat Step (a) While A [DOWN] < = PIVOT AND DOWN < UB :
(a) Set DOWN := DOWN + 1.
[End of Step 5 loop.]
6. Repeat Step (a) While A [UP] > PIVOT :
(a) Set UP := UP – 1.
[End of Step 6 loop.]
7. If DOWN < UP, then :
(a) Set TEMP : = A [DOWN]
(b) Set A [DOWN] : = A [UP]
(c) Set A [UP] : = TEMP.
[End of If Structure.]
[End of Step 4 loop.]
8. Set A [LB] : = A [UP].
9. Set A [UP] : = PIVOT
10. Set MID = UP.
11. Exit.
Quick sorting (Recursive) program in c programming.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
int partition(int [], int, int);
void quick_sort(int [], int, int);
void main()
{
int a[SIZE],n,i;
clrscr();
printf("Enter how many elements");
scanf("%d",&n);
/*Input Array */
for(i=0;i<=n;i++)
{
printf("Enter element %d ", i+1);
scanf("%d",&a[i]);
}
quick_sort(a,0,n-1);
/* Output Array */
for(i=0;i<n;i++)
printf("%dn",a[i]);
getch();
}
int partition(int a[], int lb, int ub)
{
int down, up, t, pivot;
down = lb;
up = ub;
pivot = a[lb];
while(down < up)
{
while(a[down] <= pivot && down < up)
down ++;
while(a[up] > pivot)
up--;
if(down < up)
{
t = a[down];
a[down] = a[up];
a[up] = t;
}
}
a[lb] = a[up];
a[up] = pivot;
return(up);
}
void quick_sort(int a[], int lb, int ub)
{
int mid;
if(lb >= ub)
return;
mid = partition(a,lb,ub);
quick_sort(a,lb,mid-1);
quick_sort(a,mid+1,ub);
}
Quick sorting (Non-Recursive) program in c programming.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
#define MAXSTK 20
struct stack
{
int data[MAXSTK];
int top;
};
void push(struct stack *, int);
int pop(struct stack *);
int isfull(struct stack);
int isempty(struct stack);
void quick_sort(int [], int);
int partition(int a[],int,int);
void main()
{
int a[SIZE],n,i;
clrscr();
printf("Enter how many elements ");
scanf("%d",&n);
/*Input Array */
for(i=0;i<n;i++)
{
printf("Enter element %d ",i+1);
scanf("%d",&a[i]);
}
quick_sort(a,n);
/*Output Array */
for(i=0;i<n;i++)
{
printf("%d", a[i]);
}
getch();
}
void quick_sort(int a[], int n)
{
struct stack stklb, stkub;
int mid = 0, lb, ub;
lb = 0;
ub = n-1;
stklb.top = -1;
stkub.top = -1;
if(n > 1)
{
push(&stklb, lb);
push(&stkub, ub);
}
while(!isempty(stklb))
{
lb = pop(&stklb);
ub = pop(&stkub);
mid = partition(a, lb, ub);
if(lb < mid-1)
{
push(&stklb,lb);
push(&stkub,mid-1);
}
if(mid+1 < ub)
{
push(&stklb,mid+1);
push(&stkub,ub);
}
}
}
int partition(int a[], int lb, int ub)
{
int t = 0, up = 0, down = 0, temp = 0;
down = lb;
up = ub;
temp = a[down];
while(down < up)
{
while ((a[down] <= temp) && ( down < up))
down++;
while(a[up] > temp)
up--;
if(down < up)
{
t = a[down];
a[down] = a[up];
a[up] = t;
}
}
a[lb] = a[up];
a[up] = temp;
return(up);
}
void push(struct stack *p, int val)
{
if(isfull(*p))
{
printf("Stack is Full ");
return;
}
p->top++;
p->data[p->top]=val;
}
int pop(struct stack *p)
{
int val;
if(isempty(*p))
{
printf("Stack is Empty. ");
return NULL;
}
val = p->data[p->top];
p->top--;
return(val);
}
int isfull(struct stack p)
{
return(p.top == MAXSTK - 1);
}
int isempty(struct stack p)
{
return(p.top == -1);
}Also, Read