Sorting
Finding better algorithms to sort a given set of data is an ongoing problem in the field of computer science. Sorting is placing a given set of data in a particular order. Simple sorts place data in ascending or descending order. For discussion purposes, we will look at sorting data in ascending order. However, you may modify the code to sort the data in descending order by reversing the relational operators (i.e. change 'nums[j] < nums[j-1]' to 'nums[j] > nums[j-1]').
In this lesson we will analyze sorts of different efficiency, and discuss when and where they can be used. In order to simplify the explanation of certain algorithms, we will assume a swap() function exists that switches the values of two variables. An example of such a function for int variables is displayed below.
void swap(int &item1,int &item2) //reference parameters, point directly to the storage location of the variables passed. Local copies are not made, and these values are saved after the function life span ends. See 'Functions' in the preliminary lesson for further information.
{
int tmp;
tmp = item1;
item1 = item2;
item2 = tmp;
}
We will first analyze sorts that are O(N^2). These sorts are very easy to understand, however they are very slow when there are a lot of elements to be sorted.
The first sort we will look it is called the insertion sort. The algorithm processes each element in turn, and compares it to the elements before it. The first element has no elements before it for comparison, so it is left alone. In the next iteration, the second element is evaluated. It is compared to the element directly before it, which is the first element in the structure. If the second element has a value less than the first, their positions are switched. If they second element is more than the first, then they are left as they are, and the third element is processed. The third element is then compared to the second element in the new list ('new' list here since the first two items may have been swapped). If it is less than the second, then they are swapped, and it is then compared to the first element. If it is more than the second element, it is left in place and the process continues to the next element.
In short, each element is moved to the front of the list by switching positions with the previous elements as long as it is smaller than the elements before it.
The algorithm is programmed using two nested for loops. The first loop creates n-1 iterations, where n is the number of elements in the list. Since element[0] does not have any elements before it to compare to, we start with the second element. The nested loop statement starts at the element that is being processed by the first loop, and works backwards, comparing the element to the one before it. If it is smaller, a swap is made and the loop continues. If it is larger, the loop ends, and the next iteration begins in the outer loop. The code for the insertion sort algorithm is shown below. A standard array of int variable is used for simplicity. However, you can modify the code to work for any linear structure.
void InsertionSort(int *nums,int n) //array called nums with n elements to be sorted
{
for(int i=1; i<n; i++)
for(int j=i; (j>0) && (nums[j]<nums[j-1])); j--)
swap(j,j-1);
}
The next O(N^2) algorithm that we will analyze is the bubble sort. The bubble sort works from the bottom-up (back to front), and evaluates each element to the one before it. If the element on the bottom has a smaller value than the top, the two are swapped, if not - they remain in their original position. The algorithm compares the next two elements from the bottom-up, no matter what the outcome of the previous comparison was. In this fashion, the smallest value "bubbles up" to the top in each iteration. In subsequent comparisons, the values that were bubbled up in previous iterations are no longer compared, since they are in place.
The code for the bubble sort is shown below, using a standard array of int variables. Two nested for loops are used. The first loop has n iterations, the number of elements. Each iteration, at least one element is set into its proper sorted position. The inner for loop runs from the bottom-up, comparing adjacent values, and stops at the group of values that have already been set in place, this position being one more each iteration of the outer loop.
void BubbleSort(int *nums, int n)
{
for (int i=0; i<n-1; i++)
for (int j=n-1; j>i; j--)
if(nums[j] < nums[j-1]
swap(j,j-1);
}
The selection sort will be the final O(N^2) sorting algorithm that we will look at. In a selection sort, the entire list is searched to find the smallest value. That is, we compare every element in the structure and find the smaller value, and then swap it with the first item. Then, every element but the first is searched to find the smallest value out of that group, and it is then swapped with the item in the second position. This continues until all items are in the correct order.
This technique is similar to what would be done if a person were sorting a list of items by hand. The list is searched for the smallest value, which is then crossed out and written as the first item in a new list. The computer algorithm is the same, however, in order to preserve memory and not have to make two lists, we use a swap operation.
The selection sort uses two nested for loops, the outer having n-1 iterations. When there is only one item left, it will appear in its correct position, last in the structure. The inner for loop searches the unsorted portion of structure (from bottom-top) by assuming the first element in the unsorted section is the smallest, and then comparing it to each element in turn. If a smaller element is found, it is considered to be the smallest, and compared to the rest of the elements. The code for selection sort is shown below.
void SelectionSort(int *nums, int n)
{
int low; //holds the index of the smallest element in the unsorted portion
for (int i=0; i<n-1; i++)
{
low = i; //assume the first item in the unsorted section is the lowest, unless a smaller value is found
for (int j=n-1; j>i; j--)
{
if (nums[j] < nums[low]) //if element has smaller value than low
low = j; //it then becomes the new low
}
swap(i,low); //switch the current position item with the smallest in the unsorted portion
}
}
The algorithms that follow are O(N log N).
The next sorting algorithm that will be covered is the Shell sort, named after its creator D.L. Shell. It is the first algorithm that we will look at that swaps non-adjacent elements, and takes a "divide and conquer" approach. The list is divided into many sublists, which are sorted, and are then merged together. The shell sort takes advantage of the insertion sort, which is very efficient in a best case scenario (that is, the list being sorted is already 'near sorted').
The shell sort divides the list into n/2 sublists, each being n/2 apart. For instance, in a list of ten elements, the first iteration would consist of five lists, two elements each. The first list would be list[0] and list[5], the second would be list[1] and list[6], and so on. Each of these lists is then sorted using an insertion sort. During the next iteration, we divide the list into bigger sublists, with the elements being closer together. In the second iteration, there are n/4 lists, each element being n/4 apart. These lists are then sorted using insertion sort, and so on. The process continues with twice the amount of lists each iteration as in the one before. Each iteration, the list becomes closer to being sorted. The last sort is done on the entire list, using a standard insertion sort. Since the list should be 'near sorted', the algorithm is very efficient.
Note, during some iterations, sublists will contain unequal amount of elements, since the amount of sublists does not evenly divide into the total number of elements. Remember, in integer division, the decimal in the answer is dropped, e.g. 5/2 = 2. Therefore, if we have seven elements, there are three lists during the first iteration. One contains three elements, and the other two each contain two elements.
{6,3,1,5,2,4,9} -> {6,3,1,5,2,4,9}
In the example, list one starts at
The code for shell sort is very simple and straightforward. A slightly modified version of the insertion sort is used however. Since the elements of the sublists to be sorted are not adjacent, an increment parameter is added, which specifies how far apart the elements of the sublists are. The value '1' is then replaced by the increment in the original insertion sort code, since it now compares values that are increment apart.
void ShellSort(int *nums, int n)void InSortShell(int *nums,int n, int incr) //array called nums with n elements to be sorted, incr apart
{
for(int i=incr; i<n; i+=incr)
for(int j=i; (j>=incr) && (nums[j] < nums[j-incr]); j-=incr)
swap(nums[j],nums[j-incr]);
}
{
for(int i=n/2; i>2; i/=2) //each iteration there are twice as many sublists. Divide the distance between each element by 2.
for(int j=0; j<i; j++) //sort each sublist
InSortShell(&nums[j],n-j,i); //the first element of each sublist begins at j, and therefore the entire list is j items shorter (n-j). The elements of the sublist are i apart.
InSortShell(nums,n,1); //do a standard insertion sort on the now nearly sorted list.
}
QuickSort is the quickest algorithm in the average case, however it has a very bad running time in a worst case scenario (e.g. items completely out of order, in reverse of how they should appear sorted, etc). The QuickSort takes a "divide and conquer" approach. A value called a pivot is first selected, usually it is the value of the middle element. A "partition" of the array is then preformed. Any elements that are less than the pivot value will be moved to the beginning of the list, followed by the pivot element, and then all values that are bigger will appear at the end. The elements in each 'sublist' do not need to be sorted in any way with respect to each other, but this order must be maintained. The QuickSort algorithm is then used on each sublist, through recursion. This continues until the structure has been sorted.
Let's take a look at how the partitioning algorithm is implemented. The algorithm starts at each end of the sublist being analyzed. It then moves inward from each end. First, it uses a while loop to find the first value from the left that is greater than the pivot. Then, it uses another while loop to find the first value from the right that is less than the pivot. It swaps these two values, and continues the process until the left position value and right position value meet somewhere in the center. When this algorithm is finished, every element at the left position and after is greater than the pivot, and the elements before it are less than the pivot. The code for the partition algorithm is shown below.
int part(int *nums,int left,int right,int pivot)
{
do
{
while(nums[left] < pivot) //find the next position greater than the pivot from the left
left++;
while(nums[right] > pivot) //find the next position less than the pivot from the right
right--;
swap(nums[left],nums[right]); //swap these two values
} while(left<right); //move inward until they cross
swap(nums[left],nums[right]); //the last swap occurs after left and right have crossed (i.e. left is already < right, after which the outer loops end), therefore we must re-swap these elements back into their correct positions
return left;
}
The pivot of each list is simply the middle element.
int getpivot(int left,int right) //the left and right indices of the sublist
{
return (left+right)/2;
}
Now let's take a look how QuickSort brings everything together. The left and right indices of the sublist must be passed into the QuickSort() function. Recursion is used by the algorithm to run QuickSort on each partition, which is why these values are required as parameters. On the initial call to sort an array, 0 would be used for left index, and n-1 for the right index. The pivot value itself is already locked in the correct position. Note, the pivot itself is not evaluated for the partition algorithm to work correctly. To accomplish this, we swap it with the position of the last element, and start the partition with right-1. After the partition, it is then swapped with the element at the first position of the right sublist. Now, all the elements to the left are less than the pivot, and all those to the right are greater than the pivot.
void QuickSort(int *nums, int left, int right)
{
int pivot = getpivot(left,right); //find the pivot
swap(nums[pivot],nums[right]); //move the pivot to the last position
int r_sublist = part(nums,left,right-1,nums[right]); //partition left->right-1, excluding the pivot
swap(nums[r_sublist],nums[right]); //move the pivot in the proper position
if((r_sublist - left) > 1) //if a left sublist exists, sort it
QuickSort(nums,left,r_sublist-1);
if((right - r_sublist) > 1) //if a right sublist exists, sort it
QuickSort(nums,r_sublist+1,right);
}
The merge sort is another algorithm which takes a "divide and conquer" approach. It begins by dividing a list into two sublists, and then recursively divides each of those sublists until there are sublists with one element each. These sublists are then combined using a simple merging technique.
In order to combine two lists, the first value of each is evaluated, and the smaller value is added to the output list. This process continues until one of the lists has become exhausted, at which point the remainder of the other list is simply appended to the output list. Two closest lists are combined at each end, until all the elements are merged back into a single list.
The code for merge sort is very straightforward. The algorithm uses two arrays to accomplish the task. First, the items to be sorted are copied to a temporary array, where they are divided. The original array acts as the output array, and will contain the sorted list at the end. The parameters of the MergeSort() function consist of these two arrays, as well as the left and right boundaries of the list to be sorted. This is required since the MergeSort() function is recursive, and repeats the algorithms to sublists within the array. On the initial call, left will have a value of 0, and right will have a value of n-1.
void MergeSort(int *nums, int *tmp, int left, int right)
{
if (left==right) return; //if the boundaries are the same, the sublist has only one element, and cannot be further split
int mid = (left+right)/2;
MergeSort(nums,left,mid); //sort the first half
MergeSort(nums,mid+1,right) //sort the second half
//copy the sublist into the temporary array
for(int i = left; i<=right; i++)
temp[i] = array[i];
//merge the lists
int l = left; //the first element in the first sublist
int r = mid + 1; //the first element in the second sublist
for(int j=left; j<=right; j++)
{
if(l == mid+1) //if the index of the left list is equal to the first element of the right list, the left list has ended. Insert next item from right list.
nums[j] = tmp[r++];
else if (r > right) //if the index of the right sublist has exceeded it's right boundary, the right list has ended. Insert next item from the left list.
nums[j] = tmp[l++];
else if(tmp[l] < tmp[r]) //if two lists exist, and the current element in the left is smaller than the right, insert it into the next position in the output array and move to the next element in the left list.
nums[j] = tmp[l++];
else //the current element in the right sublist is smaller than the one in the left sublist, insert it into the output array and move to the next element in the right list.
nums[j] = tmp[r++];
}
}
The next algorithm, HeapSort, is very simple to implement. The array to be sorted is first inserted as a heap structure. Then, a loop is used to remove each element of the heap. Remember from the lesson on heaps, when an element is removed, it is still part of the physical array, and is swapped with the last item of the heap. The process continues and each time the largest item is pushed to the end of the heap (which is directly before the item discarded the previous iteration, since the heap becomes smaller). This approach requires a slightly modified version of the heap class. The changes that were made are shown in bold below.
template <class ItemType>const int MAX_SIZE = 100;
class Heap
{
public:
Heap(ItemType*,int);
int left(int) const;
int right(int) const;
int parent(int) const;
void insert(const ItemType&);
ItemType remove_max();
bool IsEmpty() const;
bool IsFull() const;
int count() const;
ItemType value(int) const;
private:
ItemType *array;
int elements; //how many elements are in the heap
void ReHeap(int);
void BuildHeap();
};
This version of the heap class accepts a pointer to the array to be sorted in the class constructor. The second parameter of the constructor is the size of the array. The array is initialized as a pointer (which will point to the array passed to the construtor), and a the function BuildHeap() has been added, which will make the array into a heap.
template <class ItemType>
Heap<ItemType>::Heap(ItemType *array_ptr, int size)
{
array = array_ptr;
elements = size;
BuildHeap();
}
The BuildHeap() function begins at the first non-leaf node and works up the array, sorting each subtree with the
By working up, the subtrees of a node are made into heaps first, which allows the
template <class ItemType>
void Heap<ItemType>::BuildHeap()
{
for(int j = n/2 - 1; j >= 0; j--)
ReHeap(j);
}
The heap sort algorithm makes the array to be sorted into a heap, and then follows the above procedure.
template <class ItemType>
void HeapSort(ItemType *array, int size)
{
Heap<ItemType> sort(array, size);
for(int j = 0; j < size; j++)
sort.remove_max();
}
Note, although algorithms such as the QuickSort seem to be the only ones that should be used, this is not always the case. If you know that the array to be sorted is very small, a O(N^2) algorithm is much more simple to implement, and the difference will not be significant.