Trusted answers to developer questions

Rithika Velicheti

Quick sort is a way of sorting an array.

In quick sort, we take an element of the array called the **pivot element**. We then try to rearrange the array by comparing elements with the pivot element. Elements are put on the left side of the pivot element in the array if the elements are less than the pivot element. If elements are greater than the pivot element, they are put to the right of the array.

After rearranging elements to the left or right of the pivot element, consider the left side of the pivot element as one sub-array and the right side of the pivot as another sub-array. Repeat the whole process on these two subarrays (consider an element as the pivot, compare elements with the pivot, and put them to the left or right).

Repeat this process until the length of the sub-array is equal to one.

We can consider the first element, the middle element, or the last element as our pivot element.

```
int a[10]={5,1,0,8,2,7,3,6,4,9};
```

We will consider the first element of the array as the pivot element.
Here `pivot = a[0]`

.

Consider variables `i`

and `j`

to iterate from the`beginning`

and the `end`

until `i > j`

.

`i`

should only be incremented as `i = i + 1`

if `a[i] < pivot`

, so that all the elements less than the pivot are to the left of the pivot.

`j`

should only be decremented as `j = j - 1`

if `a[i] > pivot`

, so that all the elements greater than the pivot are to the right of the pivot.

```
while(i < j)
{
while(a[i]<=
pivot && i<=high)
i=i+1;
while(a[j]>pivot)
j=j-1;
}
```

While iterating, `i`

with condition `a[i]<pivot`

might fail, i.e, we may come across numbers larger than the `pivot`

. Similarly, `j`

with the `a[i]>pivot`

condition might fail,
i.e, we may come across numbers smaller than the `pivot`

. In such cases, we have to swap `a[i]`

with `a[j]`

.

```
if(i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
```

When `i < j`

condition fails, swap the `pivot`

element with `a[j]`

.

Repeat this process for the sub-arrays till the length of the sub-arrays equals one.

Take a look at the illustration below:

#include<stdio.h> int Partition(int a[],int low,int high) { int i = low,j = high; int pivot = a[low],temp; while(i < j) { while(a[i] <= pivot && i <= high) i = i + 1; while(a[j] > pivot) j = j - 1; if(i < j) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } a[low] = a[j]; a[j] = pivot; return j; } void quicksort(int a[],int low, int high) { int j,l = low,h = high; if(low < high) { j = Partition(a, l, h); quicksort(a, l, j-1); quicksort(a, j+1, h); } } int main() { int low = 0,high = 10, i; int a[10]= {9,0,8,1,7,2,6,3,4,5}; printf("given array elements:\n"); for(i = 0;i < high;i++) printf("%d ",a[i]); quicksort(a,low, high-1); printf("\narray sorted by quick sort:\n"); for(i=0;i < high;i++) printf("%d ",a[i]); return 0; }

RELATED TAGS

communitycreator

c

CONTRIBUTOR

Rithika Velicheti

RELATED COURSES

View all Courses

Keep Exploring

Related Courses