Write a C Program to Implement the Quick Sort Algorithm

by

Aim:

To write a program in C to sorting the elements using Quick sort method.

Theory:

The quick sort is an in-place, divide-and-conquer, massively recursive sort. As a normal person would say, it’s essentially a faster in-place version of the merge sort. The quick sort algorithm is simple in theory, but very difficult to put into code.

The recursive algorithm consists of four steps:

  1. If there are one or less elements in the array to be sorted, return immediately.
  2. Pick an element in the array to serve as a “pivot” point. (Usually the left-most element in the array is used.)
  3. Split the array into two parts – one with elements larger than the pivot and the other with elements smaller than the pivot.
  4. Recursively repeat the algorithm for both halves of the original array.

The quick sort is by far the fastest of the common sorting algorithms.

Algorithm:

  • Get N elements which are to be sorted, and store it in the array A.
  • Select the element from A[0] to A[N-1] for middle. This element is the pivot.
  • Partition the remaining elements into the segments left and right so that no elements in left has a key larger than that of the pivot and no elements in right has a key smaller than that of the pivot.
  • Sort left using quick sort recursively.
  • Sort right using quick sort recursively.
  • Display the sorted array A.

Program:

#include <stdio.h>
#define size 100
int partition(int a[], int beg, int end);
void quick_sort(int a[], int beg, int end);
void main()
{
int arr[size], i, n;
printf("\n Enter the number of elements in the array: ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, n-1);
printf("\n The sorted array is: \n");
for(i=0;i<n;i++)
printf(" %d\t", arr[i]);

}
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);
}
}

Execution:

Input:
10 8 9 6 7 5 4 2 3 1 10

Output:

Enter the number of elements in the array: 
Enter the elements of the array: 
The sorted array is: 
1	 2	 3	 4	 5	 6	 7	 8	 9	 10

Result:

Thus, Implement of Quick Sort was executed successfully.

Leave a Comment