Searching and Sorting

Introduction

Searching is the process of finding particular piece of data (the key) within a data structure. Sorting is the process of taking a set of data and creating an ordering based on some criteria. In this section of the notes, we will be looking at sorting a list of data which will help support certain methods of searching for data within the list.

caution

In this section of the notes, we will be refering to the data structure we are searching and sorting as a "list". With some of these algorithms, we specifically require the list to be array based/like as those algorithms require you to have fast random access to any element given its index. For simplicity, you can assume that the list we are talking about is array based/like.

Types of lists that are "array based/like":

• Python lists.
• Vectors from the C++ standard library
• C++ arrays

List that are not "array based/like":

• list from C++ standard library

Python provides a number of built-in functions to perform searching and sorting. However, a programmer should know how these functions work, not just be able to call them.

This section of the notes will look at 2 different searching, and 5 different sorting algorithms. A 6th sorting algorithm will be presented later in the course.