Select Page

Quick sort is based on the divide & conquer sorting technique. It was developed by Tony Hoare in 1960. In this sorting technique, the elements of arrays are divided into two smaller arrays. Quick sort is a type of In-Place sorting.

In this sorting, firstly, one element is selected from the list, which is called a pivot element. All elements that are smaller than the pivot value remain on the left side of the array, and all elements that are larger than the pivot value remain on the right side of the array. The worst-case complexity of quick-sort is very low, so it is very fast and efficient.

### Quick sort algorithm

Step 1: Select an element in the array list which is call pivot value.

Step 2: Arrange the array elements in such a way that all those elements which are smaller than pivot value remain on the left side of the array, and all those elements which are larger than pivot value remain on the right side of the array.

Step 3: Both parts of the array are again sorted using the quick sort algorithm.

### Example of Selection sort

Suppose we have the following array, which we have to sort.

Given,

p = 1, r = 6

x = A[r] = 6

i ← 1 -1 = 0

j ← 1 to 9

Step 1:  j = 1

If A[j] < x

11 < 6  // false

Step 2: j = 2

If A[j] < x

A[2] < x

8 < 6 // false

Step 3: j =3

If A[j] < x

A[3] < x

2 < 6 // true

i = i + 1,            i = 1

Step 4 : j = 4

If A[j] < x

A[1] < x

1 < 6 // true

i = i + 1                 i = 2

Step 5: j = 5

If A[j] < x

A[5] < x

9 < 6 // false

Step 6: Swap A[i + 1] and A[r]

Quicksort(A, 1, 2) Quicksort(A, 4, 6)

Output

Output