# Quick Sort Algorithm

Quick Sort Algorithm is the important topic of the Data structure. Moreover, Freestudy9 has all kind of important topic and information about the subject.

- Quicksort is the currently fastest known sorting algorithm and is often the best practical choice for sorting, as its average expected running time is O(n log(n)).
- Pick an element, called a pivot, from the array.
- Moreover, Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). Also, After this partitioning, the pivot is in its final position. This is called the partition operation.
- also, Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
- Quicksort, like merge sort, is a divide-and-conquer recursive algorithm.
- Similarly, The basic divide-and-conquer process for sorting a subarray A[
*.j*] is summarized in the following three easy steps:**Divide:**Partition T[*.j*] Into two sub-arrays T[*i*..*l*-1] and T[*l*+1…*j*] such that each element of T[*i..l*-1] is less than or equal to T[*l*], which is, in turn, less than or equal to each element of T[*l*+1…*j*]. Moreover, Compute the index*l*as part of this partitioning procedure**Conquer:**Sort the two sub-arrays T[*i*..*l*-1] and T[*l*+1…*j*] by recursive calls to quicksort.**Combine:**Also, Since the sub-arrays are sorted in place, no work is needed to combine them: the entire array T[*.j*] is now sorted.

**Algorithm for Quick Sort**

**Procedure*** pivot *(T [*i… j*]*; var *

*l*)

{Permutes the elements in array T [*i… j*] and returns a value l such that, at the end, *i<=l<=j*, T[*k*]<=P for all *i ≤ k<l*, T[*l*] =P, and T[*k*] > P for all *l<k <= j,* where P is the initial value T[*i*]} P ← T[*i*]

*K* ← *i*; *l* ← *j*+1

**Repeat** *k* ← *k*+1 **until** T[*k*] > P

**Repeat** *l* ← *l*-1 **until** T[*l*]

<= P

**While** *k*<*l* **do**

Swap T[*k*] and T[*l*]

**Repeat** *k* ← *k*+1 **until** T[*k*]>P

**Repeat** *l* ← *l*-1 **until** T[*l*]

<= P Swap T[*i*] and T[*l*]

**Procedure** *quicksort* (T [*i… j*])

{Sorts sub array T [*i… j*] into non decreasing order}

**if** *j ← i* is sufficiently small **then** insert (T[*i,…*,j])

**else **

pivot (T[*i,…,j*],*l*) quicksort (T[*i,…, l* – 1]) quicksort (T[*l*+1,…,*j*]

**Program for Quick Sort Algorithm**

#include<stdio.h>

void quicksort(int [10],int,int);

int partition(int [10],int, int);

void main()

{

int x[20],size,i;

printf(“Enter size of the array: “); scanf(“%d”,&size);

printf(“Enter %d elements: “,size);

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

{

scanf(“%d”,&x[i]);

}

quicksort(x,0,size-1);

printf(“Sorted elements: “);

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

{

printf(” %d”,x[i]);

}

getch();

}

void quicksort(int x[10],int first,int last)

{

Int mid;

if(first<last)

{

mid= partition(int x,int first,int last);

quicksort(x,first,mid-1);

quicksort(x,mid+1,last);

}

}

int partition(int x[10],int p,int r)

{

int value, i, j, temp;

value=x[r]; i=p-1;

for(j=p;j<=r-1;j++)

{

If(x[j] <=value)

{

i=i+1;

temp=x[i]; x[i]=x[j]; x[j]=temp;

}

}

temp=x[i+1]; x[i]=x[r];

x[r]=temp;

Return (i+1);

}

**Related** **Terms**

Data Structure, Bubble Sort Algorithm, Clustering Indexes, Engineering Study.

## Leave a Reply