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:

Bubble Sort| Bubble Sorting Method technique | Sy BCA Notes | BCA HUB

Example 3:

Quick sort or Partition-Exchange sort

Share

About the Author

Akash Padhiyar

Visit Website

There are no comments yet, add one below.

Leave a Comment

Your email address will not be published. Required fields are marked *

*

Time limit is exhausted. Please reload CAPTCHA.