Quicksort Using Arrays in C/C++
A Fast Sorting Algorithm for Programmers Needing to Post Sort Data
An alternative to bubble sorting or insertion sorting, the QuickSort algorithm is accessible from either C or C++ and can be used with many data types.
Introduction
Sorting is a useful programming exercise, and it is important to understand the various algorithms that can be used to sort a list of data. We shall be looking at the QuickSort algorithm, as implemented through a simple call in C and C++ to the qsort function.
The qsort function is available in the stdlib.h library, and requires:
- an array
- a comparison function
- the array length
- the size of each element
Due to the fact that the quicksort algorithm implemented in the qsort function is designed to work with any data type, the programmer must provide in the call to the qsort function. This allows us to use any kind of simple or complex type, including linked lists.
Comparison Function
The comparison function must return a specific set of values for the Quick Sort routine to be able to process the array (list) of values. The actual return logic is the same as for the string comparison function strcmp, namely:
- 0 = the items are the same
- 1 = the left-hand item should be after the right-hand item
- -1 = the right-hand item should be after the left-hand item
If we implement, for example, a simple structure:
{
char szFirst[25];
char szLast[50];
};
When we compare two sName items, we want to first position on the basis of the Last Name, and then on the First Name. Since the contents of the First Name only come into play of the Last Names are both the same, we cannot use a simple strcmp function call. So, we construct the following:
{
if (strcmp(oLeftName.szLast, oRightName.szLast) == 0)
{
return strcmp(oLeftName.szFirst, oRightName.szFirst);
}
return strcmp(oLeftName.szLast, oRightName.szLast);
}
(There are better ways to do this, with less calls to strcmp, but this illustrates the point).
Bubble Sort Implementation
With our comparison function in hand, we could use it to implement a simple bubble sort. A bubble sort algorithm does the following:
- starting at item i
- compare item i with item i+1
- if they should be swapped, swap them
- repeat with next item
This is performed until no more swaps are made, at which point the list is sorted. If we wanted to write slightly more accurate pseudocode, it would look like:
if CompareNames == -1
SwapNames
Set [swapped]
This will sort the names in descending order, as the ones that occur at the front of the alphabet are bubbled to the end of the list. If we wanted to sort in the other direction, we would test for equality with 1 and not -1.
Calling the QuickSort qsort Function
From here it is a simple step to using the qsort function. All we need is an array of elements to sort:
sName oNameList[NUMBER_OF_NAMES];
We can then make a single call to quick sort:
This will sort the list, based on whatever we use in the CompareNames function as our sorting criteria.
