Page 241 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Now, we look again for greater values than the pivot with i:

2 1 4 9 0 3 5 8 7 6

i j

We found the element of 9 which is greater. Now we seek an element lower with j:

2 1 4 9 0 3 5 8 7 6

i j

We found 5. Now we swap them:

2 1 4 5 0 3 9 8 7 6

i j

We begin the search again, but this time, the index i passes over the index j, so this means at the
position where i is the index is the proper place for the pivot, and we swap the value of the pivot
with the value that is currently there:

2 1 4 5 0 3 9 8 7 6

j i

2 1 4 5 0 3 6 8 7 9

j i

If you look closely, all the elements before 6 are smaller and all the elements after the former
pivot are greater. Now, we split the initial list into two smaller lists according to the former
pivot: 2, 1, 4, 5, 0, 3 and 8, 7, 9. We repeat the same procedure for each of the sub-lists. The pivot
will be the first element in each case, and when the proper place for the pivot was discovered and
moved in accordance to this, again we split the list into two smaller ones using the same rule:
one list will be composed by the elements smaller than the pivot and the next list composed by
elements greater than the pivot. By the end, the initial list will be put together and it will be
sorted.
The implementation of Quick Sort in C is shown as below:
#include < iostream >
using namespace std;
void swap(int &a, int &b)
{

234 LOVELY PROFESSIONAL UNIVERSITY