What is meant by quick sort?
Image result for Quick Sorting
Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.
What is the divide and conquer approach?
A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
Code:
#include <stdio.h>
void quick_sort(int[], int, int);
int partition(int[], int, int);
int main()
{
int n, i, j, temp, min, key;
int arra[50];
printf("\nAim: Quick Sorting technique using Divide and Conquer approach in C");
printf("\nUser Input: By user");
printf("\n==============================================\n");
printf("\nEnter 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", &arra[i]);
}
// Printing the array
printf("\nEntered %d elements list of the array: \n", n);
for (i = 0; i < n; i++)
{
printf("A[%d]\t %d\n ", i + 1, arra[i]);
}
quick_sort(arra, 0, n - 1);
printf("\n\nThe Sorted elements\n");
for (i = 0; i < n; i++)
printf(" %d\t", arra[i]);
return 0;
getch();
}
void quick_sort(int a[], int l, int u)
{
int j;
if (l < u)
{
j = partition(a, l, u);
quick_sort(a, l, j - 1);
quick_sort(a, j + 1, u);
}
}
int partition(int a[], int l, int u)
{
int v, i, j, temp;
v = a[l];
i = l;
j = u + 1;
do
{
do
i++;
while (a[i] < v && i <= u);
do
j--;
while (v < a[j]);
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} while (i < j);
a[l] = a[j];
a[j] = v;
return (j);
}
Output:
