The ones who are crazy enough to think they can change the world are the ones who do.
- Steve Jobs

Quick Sort

Quick sort technique uses divide and conquer method, the n number of elements sorted in an array are divided into three segments.

  • Left Segment
  • Right Segment
  • Middle Segment

In the middle segment we will be having only one element and it is called the pivot. Also note that no element in left segment has a key larger than the key of the element in the middle and no element in right has a key that is smaller than that of the middle element. Due to this, the element in the left side and the middle side can be sorted independently, and no merge is needed following the sorting of left and right.

Advantages - Quick Sort

  • The quick sort algorithm produces the most effective and widely used method of sorting a list of any size of array.

Disadvantages - Quick Sort

  • Split stage is complex in quick sort algorithm as compared to merge sort algorithm.
  • In worst case of quick sort algorithm, the time efficieny is very poor which is very much likely to selection sort algorithm i.e) n(log 2 n).

C program - Quick Sort

Here is the program to demonstrate Quick Sort.

quick-sort.c 
#include <stdio.h>
int partition(int a[], int beg, int end);
void quick_sort(int a[], int beg, int end);
int main()
{
int arry[10], i, n;
printf("\n Enter the size of the array : ");
scanf("%d", &n);
printf("\nEnter %d elements in the array : \n",n);
for(i=0; i < n; i++)
scanf("%d",&arry[i]);
quick_sort(arry, 0, n-1);
printf("\nSorted Array in ascending order is : \n");
for(i = 0; i<n; i++)
printf("%d ", arry[i]);
return 0;
}
int partition(int a[], int beg, int end)
{
int left, right, temp, loc, flag;
loc = left = beg;
right = end;
flag = 0;
while(flag != 1)
{
while((a[loc] <= a[right]) && (loc != right))
right--;
if(loc == right)
flag = 1;
else if(a[loc] > a[right])
{
temp = a[loc];
a[loc] = a[right];
a[right] = temp;
loc = right;
}
if(flag != 1)
{
while((a[loc] > = a[left]) && (loc != left))
left++;
if(loc == left)
flag = 1;
else if(a[loc] < a[left])
{
temp = a[loc];
a[loc] = a[left];
a[left] = temp;
loc = left;
}
}
}
return loc;
}
void quick_sort(int a[], int beg, int end)
{
int loc;
if(beg < end)
{
loc= partition(a, beg, end);
quick_sort(a, beg, loc-1);
quick_sort(a, loc+1, end);
}
}
Enter the size of the array : 5 
Enter 5 elements in the array :
4 3 1 2 5 
Sorted Array in ascending order is : 
1 2 3 4 5

Related to Quick Sort

Take a test

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report