There are many different approaches or algorithms for sorting data. This slide introduces four: two of them are quite intuitive and easy to understand or program; the other two are less intuitive, but faster, especially on large, random data sets.
Introduction to a Few Sorting Algorithms
-
Look at the Description and Animation for each of the 4
algorithms below.
Relatively Intuitive Sorting Algorithms
Less Intuitive, But Faster Algorithms
Comparing Sorting Algorithms
- Run comparisons of the four sorting algorithms above to see how
they differ.
- This page of comparisons will let you run several sorting algorithms simultaneously, to compare their running speed. The data sets are a little too small, though, to truly grasp some of the differences in efficiency.
- This page provides animations with larger datasets, to see some of the differences more clearly. (You may want to turn off the audio, especially if you are sharing a physical space with other people who might find the audio annoying!)
-
In the Timed Sort section of the
small-scale, step-by-step animations
page, run each of our four sorting algorithms at least twice.
(You can run Bubble Sort too, if you want.)
Scroll down to the Log below the Timed Sort section.
- What do you notice about the number of comparisons and number of copies for Selection Sort? Is the same true for other sorting algorithms?
- What do you notice about the number of comparisons, the number of copies, and the overall speed of Selection Sort vs. Insertion Sort? Can you explain the difference in the number of copies by looking at the algorithms descriptions (or the code, even)?
- Given that Merge Sort and Quick Sort are much harder to understand (and code correctly) than Insertion Sort and Selection Sort, why would anyone ever program them?
- What do you notice about the number of comparisons, the number of copies, and the overall speed of Merge Sort vs. Quick Sort? Can you explain the difference in the number of copies by looking at the algorithms descriptions (or the code, even)?
- If you run Bubble Sort, what do you notice about the number of comparisons, the number of copies, and the overall speed of Selection Sort vs Bubble Sort? If you're interested, look up a description of Bubble Sort and see if you can figure out the similarities and differences between these two sorts.