Data Structure

# Quick sort

Quicksort is a simple sorting algorithm using the divide-and-conquer recursive procedure.It is the quickest comparison-based sorting algorithm in practice with an average running time of O(n log(n)).It is also known as partition-exchange sort.

### Algorithm

```QUICKSORT(A, p, r)

1. if p < r

2.	q = PARTITION(A, p, r)

3.	QUICKSORT(A, p, q - 1)

4.	QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)

1. x = A[r]

2. i = p - 1

3. for j = p to r - 1

4.		if A[j] <= x

5.			i = i + 1

6.			exchange A[i] with A[j]

7. exchange A[i + 1] with A[r]

8. return i + 1

```

### Quick sort Implementation

```#include<stdio.h>

#include<conio.h>

void quicksort(int arr[], int lb, int ub);

void main()

{

int arr[20], n, i;

clrscr();

printf("\n\t\t\t------Quick Sort------\n\n");

printf("Enter the size of the array:");

scanf("%d",&n);

printf("Enter the elements to be sorted:\n");

for(i=0;i < n;i++)

scanf("%d",&arr[i]);

quicksort(arr, 0, n-1);

printf("\n\t\t\t-----Quick Sorted Elements-----\n\n");

printf("Sorted array:");

for(i = 0; i < n; i++)

printf("\t%d ",arr[i]);

getch();

}

void quicksort(int arr[], int lb, int ub)

{

int pivot, i, j, temp;

if(lb < ub)

{

pivot = lb;

i = lb;

j = ub;

while(i < j)

{

while(arr[i] <= arr[pivot] &&  i <= ub)

i++;

while(arr[j] > arr[pivot] && j >= lb)

j--;

if(i < j)

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

temp = arr[j];

arr[j] = arr[pivot];

arr[pivot] = temp;

quicksort(arr, lb, j-1);

quicksort(arr, j+1, ub);

}

}

```

### OUTPUT

`About Me`