## Quick Sort

Reference : https://commons.wikimedia.org/wiki/File:Quicksort.gif

The sorting method by exchange that works best is **Quick Sort**. Additionally, this is a much faster version of **Bubble Sort** overall because it has been enhanced.

In many circumstances, **Quicksort** requires fewer resources than any other sorting technique and is simple to use.

It functions by: dividing the file into two subdirectories; and recursively sorting each of these two subdirectories separately.

An array is divided into two halves using **Quick Sort**. These parts aren’t always the array’s two halves. It rearranges the array’s items after selecting the pivot element ‘a’ This way,

– Elements that appear before the pivot are either equal to or less than the pivot

– Elements are greater than or equal to the pivot in places after the pivot.

The configuration is referred to as an array partition.

We have several options when choosing pivot.

– Use the first component as your pivot.

– Select the pivot as the final element.

– Select the pivot as the median.

– Select a pivotal element at random.

**Partition**

Let n be the number of elements in the array that need to be sorted, and let x be the array.

– Select one element, a (pivot), at a certain location in the array (for example, a can be selected as the first member such that a=x[0]).

Assume that once the element of x is divided, an is positioned at position j and the subsequent criteria are met:

1. Every element from position 1 to j-1 is smaller than to a

2. Every element in locations j+1 through n exceeds or equals a

An example of **Quick Sort**

When an array has the value [20, 55, 50, 43, 11, 91, 85, 31],

– Assuming pivot value [20] is set at x[0].

[(11), 20, (55, 50, 43, 91, 85, 31)] //1st element 25 is placed in its proper position

If **55** is our pivot number

[(11), 20, (50, 43, 31), 55, (91, 85)] //55 is placed its proper position

If the pivot values are **50** and **91**

[(11), 20, (43, 31), 50, 55, (86), 91] //Here 50, 91 is its proper position

If **37** is used as the pivot value

[11, 20, 31, 43, 50, 55, 86, 91] //Sorted array

**Quick Sort Algorithm**

//Sort the array elements A[first] through A[last] Input: Array A, int first, int last Output: quicksort(A, first, last){ if(first < last){ Choose a pivot Partition the array about the pivot pivotIndex = index of the pivot quicksort(A, first, pivotIndex-1) quicksort(A, pivotIndex+1, last) } }

**Partition Algorithm **

Assume that the element whose final location is sought is a = x[index].

Consider these two sources. The sub-array’s upper and lower boundaries are initialized for variables i and j, correspondingly.

Every element in a position above i is greater than an at any given moment in the execution.

In the following manner, two references, i and j, are shifted in the direction of one another.

– **Step 01**: Until x[j] > a, raise the pointer j by one position at a time.

–** Step 2**: Until x[i] =< a, keep moving the pointer i down by one place at a time.

– **Step 3:** if i > j then interchange x[j] with x[i].

Until the condition in Step 03 (i.e., i =< j) fails, the process is repeated. At that point, j is set to i and x[i] is swapped out for x[index], which equals a, whose final position was sought.

**Parse 01**

[20 j--> 55 50 43 11 91 85 31 <--i] //1st step [20 55 j--> 50 43 11 91 85 31 <--i] //1st step [20 55 j--> 50 43 11 91 85 31 <--i] //1st step fail [20 55 j--> 50 43 11 91 85 <--i 31] //2nd step [20 55 j--> 50 43 11 91 <--i 85 31] //2nd step [20 55 j--> 50 43 11 <--i 91 85 31] //2nd step fail [20 12 j--> 50 43 55 <--i 91 85 31] //***** transition [20 11 j--> 50 43 55 <--i 91 85 31] //***** [20 11 j--> 50 43 55 <--i 91 85 31] //1st step [20 11 50 j--> 43 55 <--i 91 85 31] //1st step fail [20 11 50 j--> 43 55 <--i 91 85 31] //2nd step [20 11 50 j--> 43 55 <--i 91 85 31] //2nd step [20 11 50 j--> 43 <--i 55 91 85 31] //2nd step [20 11 50 i j 43 55 91 85 31] //2nd step [20 11 <--i 50 <--j 43 55 91 85 31] //2nd step fail [(11) 20 (50 43 55 91 85 31)] //********** transition

**Runtime analysis**

– The efficiency of the sort is impacted by the pivot selection. The array may exhibit worst-case behavior if it is sorted or almost sorted. **O(n²)** is the worst possible running time.

– In most cases, **Quick Sort** is **O (nlogn)**. The additional memory that **Merge Sort** requires for merging is not needed for **Quick Sort**.