Quick Sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. It was invented by C.A.R. Hoare. it is still a very commonly used algorithm for sorting. it is a divide and conquer algorithm.

**Algorithm:**

The steps are as follows:

- Pick an element, say
(the pivot).*P* - Re-arrange the elements into 3 sub-blocks:
- Less than or equal to
say*P**S1* (the only element in the middle-block).*P*- Greater than or equal to
say*P***S2**. - Repeat the process recursively for
and*S1*.**S2**

**Example:**

**Choosing Pivot:**

- Always pick first element as pivot.
- Always pick last element as pivot.
- Pick a random element as pivot.(Recommended)
- Pick median as pivot.

**Why is Quick Sort preferred for arrays?**

Quick Sort in its general form is an in-place sort whereas merge sort requires O(n) extra storage. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both type of sorts have O(nlogn) average complexity but the constants differ. For arrays, merge sort loses due to the use of extra O(n) storage space.

**Implementation:**

//Using random element as pivot

int partition(int arr[], int l, int r)

{

srand(time(NULL));

int pivot = rand() % (r - l + 1) + l;

std::swap(arr[l], arr[pivot]);

int j = l + 1;

for(int i = l+1; i <= r; ++i)

{

if(arr[i] < arr[l])

std::swap(arr[j++], arr[i]);

}

std::swap(arr[--j], arr[l]);

return j;

}

void quick_sort(int arr[], int l, int r)

{

if(l < r)

{

int p = partition(arr, l, r);

quick_sort(arr, l, p-1);

quick_sort(arr, p+1, r);

}

}

**Complexity:**O(nlogn)

## No comments:

## Post a Comment