Advanced Sorts
From
(→Merge Sort) |
|||
| Line 1: | Line 1: | ||
| - | We will consider 4 advanced sorting algorithms: Merge Sort, Shell’s Sort, Heap Sort, and Quick Sort. | + | We will consider 4 advanced sorting algorithms: ''Merge Sort, Shell’s Sort, Heap Sort'', and ''Quick Sort''. |
== Merge Sort == | == Merge Sort == | ||
| Line 5: | Line 5: | ||
The basis Merge Sort algorithm is to divide the array in half. Sort each half separately, and merge the two halves back into one array. Does this actually work? Consider using a basic bubble sort on an array of 1,000 items (a really dumb idea!). Basic Bubble Sort takes N<sup>2</sup> – 2N + 1 comparisons. When N is 1,000, this is 998,001 comparisons. If the array is divided into two arrays of 500, each array would take 249,001 comparison and it would take 1,000 (i.e. N ) steps to perform the merge. Thus, a total of 2 × 249,001 + 1,000 steps are required, and this is a total of 499,002 steps versus 998,001 steps. | The basis Merge Sort algorithm is to divide the array in half. Sort each half separately, and merge the two halves back into one array. Does this actually work? Consider using a basic bubble sort on an array of 1,000 items (a really dumb idea!). Basic Bubble Sort takes N<sup>2</sup> – 2N + 1 comparisons. When N is 1,000, this is 998,001 comparisons. If the array is divided into two arrays of 500, each array would take 249,001 comparison and it would take 1,000 (i.e. N ) steps to perform the merge. Thus, a total of 2 × 249,001 + 1,000 steps are required, and this is a total of 499,002 steps versus 998,001 steps. | ||
| + | <br> | ||
| - | + | The next question is, “Is Bubble Sort a good choice to use for sorting each side?” Why not just use Merge Sort? So now we have a recursive sorting algorithm.<br> | |
| - | The next question is, “Is Bubble Sort a good choice to use for sorting each side?” Why not just use Merge Sort? So now we have a recursive sorting algorithm. | + | |
| - | + | ||
| - | + | ||
<pre>If the array has size 1 then | <pre>If the array has size 1 then | ||
it is sorted | it is sorted | ||
| Line 15: | Line 13: | ||
Divide the array in half | Divide the array in half | ||
Merge Sort each half | Merge Sort each half | ||
| - | Merge the two halves.</pre> | + | Merge the two halves. |
| + | </pre> | ||
Analyzing the run-time performance of a recursive algorithm requires the use of a mathematical technique called a recurrence relation. If we apply this technique to the Merge Sort algorithm, we find that it is O( N log N ). This is better than the simple sorts, which were O( N<sup>2</sup> ). | Analyzing the run-time performance of a recursive algorithm requires the use of a mathematical technique called a recurrence relation. If we apply this technique to the Merge Sort algorithm, we find that it is O( N log N ). This is better than the simple sorts, which were O( N<sup>2</sup> ). | ||
| + | <br> | ||
| + | The mathematical analysis, however, hides certain details about Merge Sort. First, the recursion takes time because of the overhead of making recursive calls. Part of this overhead is the creation of many activation records, since each recursive call to a method required a new activation record be pushed onto the run-time stack. Secondly, the merge process requires the use of a temporary array, so Merge Sort has a high memory requirement. Remember the trade-off between time and space? To make something use less time often requires using more space. | ||
| - | + | ||
| + | |||
| + | ==Shell’s Sort==<br>This sort, sometimes called Shell Sort, was developed by Donald Shell and published in 1959 (CACM). This sort is an extension of Insertion Sort. It uses the idea that Insertion Sort runs quickly given two conditions: (1) The array being sorted is small, and (2) the array being sorted is almost in order. | ||
Revision as of 22:54, 24 March 2009
We will consider 4 advanced sorting algorithms: Merge Sort, Shell’s Sort, Heap Sort, and Quick Sort.
Merge Sort
The basis Merge Sort algorithm is to divide the array in half. Sort each half separately, and merge the two halves back into one array. Does this actually work? Consider using a basic bubble sort on an array of 1,000 items (a really dumb idea!). Basic Bubble Sort takes N2 – 2N + 1 comparisons. When N is 1,000, this is 998,001 comparisons. If the array is divided into two arrays of 500, each array would take 249,001 comparison and it would take 1,000 (i.e. N ) steps to perform the merge. Thus, a total of 2 × 249,001 + 1,000 steps are required, and this is a total of 499,002 steps versus 998,001 steps.
The next question is, “Is Bubble Sort a good choice to use for sorting each side?” Why not just use Merge Sort? So now we have a recursive sorting algorithm.
If the array has size 1 then it is sorted else Divide the array in half Merge Sort each half Merge the two halves.
Analyzing the run-time performance of a recursive algorithm requires the use of a mathematical technique called a recurrence relation. If we apply this technique to the Merge Sort algorithm, we find that it is O( N log N ). This is better than the simple sorts, which were O( N2 ).
The mathematical analysis, however, hides certain details about Merge Sort. First, the recursion takes time because of the overhead of making recursive calls. Part of this overhead is the creation of many activation records, since each recursive call to a method required a new activation record be pushed onto the run-time stack. Secondly, the merge process requires the use of a temporary array, so Merge Sort has a high memory requirement. Remember the trade-off between time and space? To make something use less time often requires using more space.
==Shell’s Sort==
This sort, sometimes called Shell Sort, was developed by Donald Shell and published in 1959 (CACM). This sort is an extension of Insertion Sort. It uses the idea that Insertion Sort runs quickly given two conditions: (1) The array being sorted is small, and (2) the array being sorted is almost in order.
