Page 240 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

A pivot is chosen from the elements of the data set. Notes

Notes The list must be reordered in such a way that the elements with the value less than
the pivot come before it and the ones that are greater come after it. This is called the
partition operation, and after this was completed, the pivot is in its final position, then,
recursively, sort the rest of the elements.

Example: Having the following list, let’s try to use quick sort to arrange the numbers
from lowest to greatest:
Unsorted list:

6 1 4 9 0 3 5 2 7 8

We go from START to END, with the pivot being the first element 6, and let us hide it.

8 1 4 9 0 3 5 2 7 6

I j

Now we scan with i and j. We have to find with i the first value greater than the pivot and with
j the first value lower than the pivot. We found that the first value greater than the pivot is 8, and
we are still looking for the first value lower than the pivot:

8 1 4 9 0 3 5 2 7 6

I j

8 1 4 9 0 3 5 2 7 6

i j

We found with j the number 2 which is lower than the pivot, so now we swap the elements
pointed by i with j:

2 1 4 9 0 3 5 8 7 6

i j

LOVELY PROFESSIONAL UNIVERSITY 233