# Quick sort program in C

In this post, you will learn about the **Quick Sort** and how to write a quick sort program using the **C** programming language.

Quick sort is a widely used sorting algorithm, developed by **C.A.R**.

In **quick sort**, it first selects one element called a pivot. After that, it rearranges the elements in the array in such a way that all the elements less than the pivot element appear before the pivot and all the elements greater than the pivot appear after the pivot. After this, partitioning the pivot is in the final position.

Quick sort is the fastest algorithm and is the best choice. It is faster than other algorithms like bubble sort, selection sort, and insertion sort. But this can be complex on the flip side.

## Quick Sort Example

These are the quick sorting techniques.

We choose the first element as a pivot. So set loc at **0 index**, left at **0 index** and right at the **5th index**.

Now scan from right to left until **a[loc] < a[right]**, then decrease the value of right.

Since **a[loc] > a[right]**, interchange the two values and set **loc = right**.

Now scan from left to right until **a[loc] > a[left]**, then increment the value of left.

Since **a[loc] < a[left]**, interchange the values and set **loc = left**.

Since from right to left, since **a[loc] < a[right]**, decrease the value of right.

Start scanning from left to right. Since **a[loc] > a[left]**, increment the value of left.

Since **a[loc] > a[right]**, interchange the two values and set **loc = right**.

## Complexity of Quick sort

Suppose **n** is the number of elements in an array.

`Best Time Complexity - `**O(n log(n))**
Worst Time Complexity - **O(n**^{2})

## Quick sort program in C

```
#include <stdio.h>
void quick_sort (int [], int, int);
int main()
{
int array[50];
int size, i;
printf("Enter the number of elements: ");
scanf("%d", &size);
printf("Enter %d numbers : ",size);
for (i = 0; i < size; i++)
{
scanf("%d", &array[i]);
}
quick_sort(array, 0, size - 1);
printf("Quick Sorted List \n");
for (i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
void quick_sort(int array[], int low, int high)
{
int pivot, i, j, temp;
if (low < high)
{
pivot = low;
i = low;
j = high;
while (i < j)
{
while (array[i] <= array[pivot] && i <= high)
{
i++;
}
while (array[j] > array[pivot] && j >= low)
{
j--;
}
if (i < j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
temp = array[j];
array[j] = array[pivot];
array[pivot] = temp;
quick_sort(array, low, j - 1);
quick_sort(array, j + 1, high);
}
}
```

**Output of the above code:**

```
Enter the number of elements: 8
Enter 8 numbers : 87 39 81 42 73 49 61 53
Quick Sorted List
39 42 49 53 61 73 81 87
Enter the number of elements: 6
Enter 6 numbers : 302 202 504 104 893 404
Quick Sorted List
104 202 302 404 504 893
```

### Related Articles

**Prime factors of a number in c**

Armstrong number program in c

Write a program to check leap year in c

C program to find area of rectangle

C program to convert celsius to fahrenheit

Fibonacci series program in C using recursion

Write a program to find area of circle in C

C program to find greatest of three numbers

C program for addition of two numbers

C program to calculate compound interest

C program to find the ASCII value of a character

C program to convert Decimal to Octal

C program to convert decimal to binary

Write a C program to calculate Simple Interest

C program to check whether a number is even or odd

C program to reverse a number

C program to check palindrome number

C program to check whether an alphabet is a vowel or consonant

Program to find square root of a number in C

C program to check whether a number is positive or negative

Armstrong number program in c

Write a program to check leap year in c

C program to find area of rectangle

C program to convert celsius to fahrenheit

Fibonacci series program in C using recursion

Write a program to find area of circle in C

C program to find greatest of three numbers

C program for addition of two numbers

C program to calculate compound interest

C program to find the ASCII value of a character

C program to convert Decimal to Octal

C program to convert decimal to binary

Write a C program to calculate Simple Interest

C program to check whether a number is even or odd

C program to reverse a number

C program to check palindrome number

C program to check whether an alphabet is a vowel or consonant

Program to find square root of a number in C

C program to check whether a number is positive or negative