Module 11: Sorting and Searching Algorithms

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

Leave a Reply

Your email address will not be published. Required fields are marked *