Page 243 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes cout << “Input” << i << “ element: “;
cin >>a[i]; // Adding the elements to the array
}
cout << “Unsorted list:” << endl; // Displaying the
unsorted array
for(int i=0; i<n; i++)
{
cout << a[i] << “ ”;
}
QuickSort(a, 0, n-1);
cout << “nSorted list:” << endl; // Display the sorted
array
for(int i=0; i<n; i++)
{
cout << a[i] << “ ”;
}
return 0;
}
The output is shown below:

Source: http://www.exforsys.com/tutorials/c-algorithms/quick-sort.html
The partition function does what it is called, it chooses the pivot, then, like in the example, while
l is smaller than high (or i smaller than j like in the example) it checks the list for the elements
that must be greater or smaller, and when it has found them, a swap function is executed. Then,
inside the QuickSort function, after the pivot was found, the list is divided into two smaller lists,
according to the pivot, then recursively the partition function is called for each sub-list and in
the end the initial list is sorted.
Some of the advantages of quick sort are:
One of the fastest algorithms on average;

Does not need additional memory (the sorting takes place in the array – this is called
in-place processing).
Some of the disadvantages of quick sort are:

The worst-case complexity is O(N2);
It is recursive;

236 LOVELY PROFESSIONAL UNIVERSITY