# Quicksort

**Sorting** is a technique to arrange the** sequence** of elements either in **ascending** or **descending** order. Quicksort is an efficient way to sort elements of array.The average running time of quicksort is O(nlogn).The steps followed in **quicksort** are :

- Choose the
**pivot**element(Say we choose the pivot element in the beginning of array). - Scan from
**right**to**left**and find**first**element in list which is**less**than the**pivot**element.**Stop**scanning as soon the element is f**ound**. **Swap**it with the**pivot**element.- Now scan from
**left**to**right**to find the**first**element which is**greater**than pivot element. **Swap**the element with**pivot**.- Continue the process till the list is
**sorted**or we get a list for which the above process fails to be followed up. **Divide/partition**the array with**pivot**in between into two**sub-arrays**.- Same
**process**is followed on both the**sub-arrays**separately and further partitioning and processing is done if necessary. - Combine all the
**sub-arrays**and their**pivot**elements to get a**sorted**array.

**Program**

#include<stdio.h> void swap (int arr[], int left, int right) { int temp; temp=arr[left]; arr[left]=arr[right]; arr[right]=temp; } void quicksort( int arr[], int low, int high ) { int pivot; if ( high > low ) { pivot = partition( arr, low, high ); quicksort( arr, low, pivot-1 ); quicksort( arr, pivot+1, high ); } } int partition( int arr[], int low, int high ) { int left, right; int item_pivot; int pivot = left = low; item_pivot = arr[low]; right = high; while ( left < right ) { while( arr[left] <= item_pivot ) left++; while( arr[right] > item_pivot) right--; if ( left < right ) swap(arr,left,right); } arr[low] = arr[right]; arr[right] = item_pivot; return right; } void printarray(int arr[], int); int main() { int arr[30], i, n; //printf("\nEnter no. of elements: "); scanf("%d", &n); //printf("\nEnter the elements: \n"); for (i=0; i<n; i++) scanf ("%d", &arr[i]); printf("\nUnsorted array: \n"); printarray(arr,n); quicksort(arr,0,n-1); printf("\nSorted array: \n"); printarray(arr,n); } void printarray(int arr[], int n) { int i; for (i=0; i<n; i++) printf(" %d ", arr[i]); printf("\n"); }

**Example**

Say we have an array with elements **7,44,2,10,1,35,74,88,5,3,15**.Scanning from **right to left** is done to to find element **less** than pivot and from **left to right** is done to find element** greater** than pivot.

*Figure 1*

- The
**pivot**element is the first element i.e**7**. - Scan from right to left and find element less than
**7**.**3**is the first element so it is swapped with the pivot element. - Scan from left to right and find element greater than
**7**.**44**is the first element encountered so it swapped with**7**. - Scan from right to left.
**5**is less than pivot element i.e.**7**so they are swapped. - Scan from left to right.
**10 >7**,so it swapped with**7**. - Scan right-left.
**1 <7**so they are swapped. - Scan from left to right.There is
**no element**in the list before pivot which is greater than pivot itself.Thus list is divided into two sub-lists**S1**and**S2**such that elements in S1 are less than pivot and elements in S2 are greater than pivot.

*Figure 2*

- S1 has
**3,5,2,1**with pivot element**3**and S2 has**35 74 88 10 44 15**with pivot element**35**.(Fig 2) - Scan right to left in
**S1**and find element less than**3**.**1 <3**so they are exchanged. - Scan left-right in
**S1**and find element greater than**3**.**5>3**so they are swapped. - Scan right-left in
**S1**.**2<3**so they are swapped and sub-list S1 gets sorted.

*Figure 3*

- Scan right-left in
**S2**.**15<35**,so they are swapped - Left-right -
**74>35**so they are swapped. - Right-left-
**10<35**so they are swapped. - Left-Right -
**88 >35**so they are swapped.

*Figure 4*

- Partition the sub-list into two further sub-lists
**S3**and**S4**.**S3**has**15,10**and**S4**has**88,44,74**. - Scan right-left in
**S3**.**10<15**so they are swapped and scanning from left-right does not gives any result. - S3 becomes sorted.

*Figure 5*

- Scan right-left in
**S4**.Pivot is**88**.**74<88**so they are swapped. - Scanning left to right is a failed attempt.

*Figure 6*

- Partition S4 into
**S5 and S6**.S5 has**74,44**and S6 is**empty**. - Scan right-left in
**S5**.Pivot is**74**.**44<74**so they are swapped and list becomes sorted.

Combine sub-lists to obtain a sorted list.

Thank you for sharing this fine article. Very interesting ideas! (as always, btw)