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.