Computer Science II -- Week 13
Introduction
Note that the links from this page are to handouts that will be distributed the night of class. Only print out those handouts if you could not attend class.
Main topics this week:
Sorting
Insertion Sort
Shell Sort
Merge Sort
Quick Sort
Radix Sort
Indirect Sorting
Sorting is one of the most common tasks in computer science (imagine trying to find a name in an unsorted telephone book).
Two general categories of sorting:
All the following sorts are internal.
An insertion sort works by inserting an unsorted element into the proper place in an already sorted portion of the array. It works like this:
Starting with an unsorted array, let's consider the first element to be in the right spot of a one element array. For example, if the array has the elements 10, 5, 9, 7, 3, and 6 we would consider the first element (10) to be sorted, and the rest of the elements to be unsorted. Don't spend too much time worrying about it.
Now, take the second element and put it into its proper place with respect to the portion of the array that's already sorted (which at the moment is just 10).
Now, take the third element and put it into its proper place with respect to the portion of the array that's already sorted (which is now 5 and 10).
Continue doing that for each of the remaining unsorted elements in the array.
Let's look at how we put an unsorted element into the right spot in the sorted portion of the array. We compare the unsorted element with the previous element, and swap them if the unsorted element is less than the previous element. We continue doing that until the unsorted element is not less than the previous element (which means it is in the right spot).
What would the big Oh rating of this sort be?
Somebody decided the insertion sort wasn't efficient enough, and noticed that some of the elements must move many times to get to their final location in the array. And each time an element is moved, it only moves one space closer to its final position. Wouldn't it be great, they reasoned, if an element could move more than one space in a single move?
Their solution is the Shell sort. In the Shell sort, you start with an unsorted array, and you will sort it in the same manner as the insertion sort. But instead of putting the entire array in order, you will put every hth element in order (where h usually starts off as N/2, where N is the number of elements in the array).
Let's look at this. Consider the unsorted array containing 10, 5, 9, 7, 3, and 6. A Shell sort approach to this would start by putting every 3rd element in order. Every third element is put in order using an insertion sort, as if the only elements in the array were every 3rd element.
So we use an insertion sort on 10 and 7. Then on 5 and 3. Then on 9 and 6.
Now we make h = h / 2 rounded down, and do it all over again. So this time we would sort every element (3 / 2 = 1) using an insertion sort.
Note that individual items moved quite a distance in that first pass, which saved some moves later on. Believe it or not, this extra complexity does make this sort more efficient than the insertion sort.
What's the big Oh of the Shell sort?
The merge sort is a divide and conquer algorithm. It uses the logic that sorting half an array must be easier than sorting the entire array, so that's what it does. It sorts the first half of the array and the second half of the array independently, and then merges the two sorted halves together.
Let's look at the sorting portion first. Each half of the array is sorted using a recursive call to merge sort.
Now let's look at the merging, which is really the heart of the algorithm. Given two sorted arrays, you can merge them by comparing their first elements (let's say the first array's first element is at index i, and the second array's first element is at index j). Whichever one is less we place into our destination array, and we increment the index for that array (so we'll compare against the next element in that array). We keep comparing elements and placing the lesser one into the destination array until we run out of one array. Then we place the rest of the other array into the destination array.
Let's see how this whole process works on a real array: 10, 5, 9, 7, 3, and 6.
What do you suppose the big Oh of the merge sort is?
Quick sort is another recursive algorithm. The general idea is to partition the array such that one of the array elements is in the right spot. In the right spot means that all the elements that are less than that element are to the left of it in the array, and all the elements that are greater than that element are to the right of it in the array. Now that the one element is in position, we'll sort the left half and right half of the array separately.
The general algorithm looks like this:
quicksort (array, low, high)
{
q = partition (array, low, high);
quicksort (array, low, q - 1);
quicksort (array, q + 1, high);
}
Obviously, most of the work is being done in the partition step. The partition step does 3 basic things:
1) Picks an element to use as a pivot
2) Moves everything greater than the pivot to the right of it
3) Moves everything less than the pivot to the left of it
By the end of the partition step, the pivot element is in the right spot.
When we partition an array, you are given the low index and high index for the elements to partition. On the first pass through this, low will be 0 and high will be the size of the array - 1. Consider partitioning the array containing 10, 5, 9, 7, 3, 2, and 6.
We can pick a pivot in many different ways. For our purposes, we'll just pick the middle element. There are ways of picking a pivot that are more efficient, but you'll get the general idea of the quick sort by just using the middle element.
We want to put the middle element out of the way while we move everything else around, so we'll swap it with the element at the high index. Then we'll decrement high so we don't move the pivot again until we're ready.
The actual partition algorithm looks like this:
while (low < high)
{
if (array [low] <= pivot && array[high] > pivot)
{
low++
high--
}if (array [low] <= pivot && array[high] <= pivot)
low++if (array [low] > pivot && array[high] > pivot)
high--if (array [low] > pivot && array[high] <= pivot)
{
swap (array[low], array[high])
low++
high--
}
}if (array[low] <= pivot)
swap (array[low + 1], pivot)
else
swap (array[low], pivot)
This basically makes a single pass through the array, moving anything that's on the wrong side of the pivot. By the end of it, the pivot is in its final spot in the array.
Quick sort isn't very efficient for small arrays, so normally when it gets down to an array of five elements or so, it uses another sort (perhaps insertion sort) to sort the last few elements.
What would the big Oh of quick sort be?
That's actually the most efficient that any sort which involves comparing and swapping values can be.
Radix sort is useful if you can meet a couple of conditions:
1) The values you are sorting must be integral values (no decimals)
2) The values must be in a known range. The exact range doesn't matter, but you need to know ahead of time what that range is.
Assuming your data meets those requirements, here's how the radix sort works.
You have a number of buckets (the exact number can be whatever you want, but as you'll see, 10 buckets makes it easier to demonstrate). We'll number our buckets 0 through 9.
Let's look at using the radix sort to sort these numbers: 53, 206, 99, 34, 33, 59, 4, and 101.
You start by considering the rightmost digit of each number, and putting them into a bucket based on that rightmost number.
Once everything is in a bucket, you take them out of the buckets in order from 0 to 9, and build a new list of items to sort.
Now you make another pass on the next digit (the 10s digit). You recombine the items into a new list, and make another pass on the next digit (the 100s digit). You keep doing this until you run out of digits.
What do you think the big Oh of the radix sort is?
The sorting algorithms we've looked at all involve large amounts of copying. A single element might be copied many times before the sort finally gets the element into the right position. This is fine for sorting integers, but what if we are sorting an array where every element is a class that contains a megabyte of information? Clearly, we do not want to do anymore copying of that amount of data than is absoutely necessary.
Indirect sorting is an approach that can be used with any of the sorting algorithms. The basic approach is to have a second array where each element is an array index into the array you really want to sort. Let's look at how this might look for the array 10, 5, 9, 7, and 3.
Now, when we sort we do our comparisons on the actual array, but we do our moves on the index array. Only once everything is sorted do we finally make a pass to move the elements of the actual array into the right places in the array.