CMPS 260: Data Structures
Introduction
Data structures go hand in hand with algorithms. Here we will look at some of the major classes of algorithms: sorting and searching. Sorting algorithms take an array of unordered elements and order them. This can be achieved in many different ways and some are slow and some are fast. We will study and implement several. Searching algorithms check whether an element is in an array or not and we will look at two approaches. The first one does a simple sequential search through the array and checks every element, which also means it is slow. The second approach is a binary search and requires a sorted array. Every step the array is divided in half by comparing the element we are looking for to the current middle element. This allows the number of elements to be halved every step and is therefore much quicker than a linear search. Note that we implemented something similar with the binary search tree.
Module Objectives
- Describe sorting algorithms
- Implement and use sorting algorithms
- Describe searching algorithms
- Implement and use searching algorithms
Learning Resources
- Module 11 Readings: Chapter 10 (skip ECMAScript and heap sort sections)
- Module 11 Slides: Chapter 10
Learning Activities
- Module 11 Assignment
For Further Study
- Read more about sorting algorithms on Wikipedia
- Read more about searching algorithms on Wikipedia