Searching and Sorting Algorithms

For the Computer Science A exam, you are responsible for knowing the concepts behind the following algorithms, being able to code them or read code utilizing them, and understanding their relative efficiency:

• Sorting Algorithms
  
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
• Searching Algorithms
  
  • Sequential (or Linear) Search
  • Binary Search

Students taking the Computer Science AB exam are responsible for all of the above, plus:

• Sorting Algorithms
  
  • HeapSort
• Searching Algorithms
  
  • Hashing

Below are a selection of links for you to visit.

Your goal: to understand the general concept and method behind each of the algorithms: Selection Sort, Insertion Sort, Merge Sort, Quick Sort and the Binary Search. Eventually, you should be able to write the code for them, as well.

Java animations are very helpful to help you see what is going on, but you should probably first read a small, general explanation of the type of sort before viewing an animation. This will help you to get more out of the animation.
A Tip: When viewing the animations, if you use the "Step" button, it will go through only one step at a time. This is slower and may allow you to see better what is going on. If you choose a button that says "Run" or "Finish" it will just go quickly to the end, maybe too quickly for you to watch. (Depends on which page you are viewing.)

[Note: Some of the code provided on these pages linked below is not C++. It may be C, Ada, or other languages altogether. In the programs that are C code, you need to recognize that vectors are sometimes declared like this:

int *numvect;
-or-
int numvect[];

Each of the above statements declares a vector.
In our course of study, a nearly equivalent declaration would be:

apvector <int> numvect;

]

Discussion of sorting methods: Selection, Insertion, Bubble sorts.

A discussion of sorts. Insertion, Quick, Hash Tables, Binary Search Trees. Explains the algorithms, and walks you through them step-by-step.

A nice, simple, Insertion Sort Animation.

Java animations for several sorts For Selection and Insertion sorts, look under "Quadratic Sorts". For MergeSort and QuickSort, look under "Efficient Sorts". Also discussions of Hashing, Hash Tables and Binary Trees. (These animations have a lot of control features. I think they are one of my favorites of my collection.)

Merge Sort: Discussion and Java animation

Merge Sort Psuedocode..

Discussion of QuickSort Algorithm, complete with code examples and an animation. (Scroll down to find the button that activates the animation.)

Another Quick Sort Java Animation.

.Java animation of Quadratic Sorts (Bubble, Selection, Insertion): includes a comparison of the three (entitled "Sorting examples"), counting number of comparisons and swaps. Especially visit the Comparison animation.

Java animations of Insertion, Selection and Bubble Sorts. Counts the number of comparisons and swaps to help with analysis of efficiency.

Several Java animations, with C++ code. Nice for comparing algorithms.

C code for several sorts. Although it is not C++ you will be able to read and understand it. Bubble Sort, Insertion Sort, Selection Sort, Quick Sort (recursive), Merge Sort (non-recursive), Shell Sort and Heap Sort.

A review of Insertion, Selection and Bubble Sorts. Includes a Java animation of Insertion sort, but it is hard to read the numbers (too small). The animation also has the Insertion sort code.

On-line Dictionary of Computing: Sort entry

Dictionary of Algorithms, Data Structures and Problems: Sort entry

Discussion of Heap Sort with Java Animation.

A review of Searching Algorithms: Sequential and Binary (follow the link at the bottom of the page for info on searching in Trees).

Another Animation Site for sorting algorithms.


(last updated Mon. April 9, 2001)