## Quick sort or Partition-Exchange sort

- This is very well defined sorting method used for performing sorting on large tables.

- At each step a particular value is placed in its final position within the table.

- All records which precede this record have smaller keys, while all records that follow it have larger keys.

- This technique partitions table into two subtables.

- The same process can then be applied to each of these subtables and repeated until all records are placed at their final positions.

** **

**Procedure QUICK_SORT(K, LB, UB)****.**

** ** Given a table K of N records, this recursive procedure sorts the table in ascending order. A dummy record with key K[N+1] is assumed where K[I] £ K[N+1] for all 1 £ I £ N. The LB and UB denote the lower and upper bounds of the current subtable being processed. The indices I and J are used to select certain keys during processing of each subtable. KEY contains the key value which is being placed in its final position within the sorted subtable. FLAG is a logical variable which indicates the end of the process that places a record in its final position. When FLAG becomes false, the input subtable has been partitioned into two disjointed parts.

**K – Vector to be sorted**

**LB – Lower bound of sub table**

**UB – Upper bound of sub table**

**KEY – Key vector which is to be places in final position**

**FLAG – Logical variable**

**I, J – Loop variables**

1) [Initialize]

FLAG <- *true*

2) [Perform sort]

If LB < UB

then I ß LB

J <- UB + 1

KEY ß K[LB]

Repeat while FLAG

I <- I + 1

Repeat while K[I] < KEY (scan from L-R)

I <- I + 1

J <-J – 1

Repeat while K[J] > KEY (scan from R-L)

J<-J – 1

If I < J

then K[I] <–> K[J] (interchange records)

else FLAG <- *false*

K[LB] <–> K[J] (interchange records)

Call QUICK_SORT(K, LB, J – 1) (sort first subtable)

Call QUICK_SORT(K, J + 1, UB) (sort second )

3) [Finished]

Return

### Example:

Consider the following key set

42 23 74 11 65 58 94 36 99 87

- Two index variables i and j can be used with initial values 2 and 10.

- The two keys 42 and Ki are compared, and if an exchange is required then i is incremented by 1 and the process is repeated until Ki <= 42. After that Kj is compared with 42. If Kj >= 42 it will be decremented and the process is repeated.

- At this point if i<j then Ki and Kj are interchanged and the entire process is then repeated with fixed j and i being incremented once again.

- When i>=j, the desired key is placed in its final position by interchanging the key 42 and Kj.

- The sequence of exchanges for placing 42 in its final position is given as follows:

- The original key set has been partitioned into the subtables, namely, the set {11, 23, 36} and {65, 58, 94, 74, 99, 87}. The same process can be applied to each of these sets until the table is completely sorted.

### Tracing :-

Example 2:

Example 3:

There are no comments yet, add one below.