4061CEM - Programming and Algorithms 1
Searching and Sorting
Dr Ian Cornelius
Hello
Learning Objectives
Understand the concept of searching and sorting in Python
Demonstrate the ability to use sorting algorithms
Introduction to Searching Algorithms
Searching algorithms are a series of instructions to retrieve information stored in a data structure
Split into two categories:
Sequential
Interval
There are many searching algorithms
i.e. linear search, binary search, interpolation search and exponential search
Linear Search
A method to find a target value in a list
It will sequentially check each element of the list for a target value
this is repeated until a match is found or until all elements have been searched
Algorithm Instructions
Start at the left-most (or right-most) element of the list
One-by-one compare each element of the array to a target
If the element matches the target, return the index number
If the element does not match the target, go back to step 2
If any of the elements do not match the target value, then return
False
Linear Search Demonstration
Demonstration of the Linear Search algorithm
Refer to the pre-recorded video for a demonstration
Binary Search
An efficient search algorithm to solve problems
It will search a
sorted
array by dividing the search interval in half
Algorithm Instructions
Compare the target value with the middle element
If the target value matches with the middle element, return the middle index
If the target value is greater than the middle element, perform a search on the right half of the list
If the target value is less than the middle element, perform a search on the left half of the list
If the element does not match any of the elements, return
False
Binary Search Demonstration
Demonstration of the Binary Search algorithm
Refer to the pre-recorded video for a demonstration
Introduction to Sorting
Sorting algorithms are made up of a series of instructions
they accept a list as an input and outputs a sorted list
There are many examples of sorting algorithms:
i.e. selection sort, bubble sort, insertion sort, merge sort etc.
In this lecture we shall look at two sorting algorithms: bubble and insertion sort
Bubble Sort
A simple algorithm that works by swapping adjacent elements if they are in the incorrect order
Algorithm Instructions
Compare each adjacent element in the list
Swap the two elements if necessary
Repeat the process for all elements in the list until the list is sorted
Bubble Sort Demonstration
Demonstration of the Bubble Sort algorithm
Refer to the pre-recorded video for a demonstration
Insertion Sort
A sorting algorithm that works in a similar method to how we would sort playing cards in our hands
Algorithm Instructions
Compare the first element (
\(n\)
) of the list to the next one (
\(n+1\)
)
If
\(n\)
is less than
\(n+1\)
, add
\(n\)
to the sorted sub-list, move onto the next element
Compare the current element to all the elements in the sub-list
Shift all elements in the sorted sub-list if it is greater than the current element
Insert the current element into the sorted sub-list
Repeat this process until the list is sorted
Insertion Sort Demonstration
Demonstration of the Insertion Sort algorithm
Refer to the pre-recorded video for a demonstration
Goodbye
Questions?
Post them in the
Community Page
on Aula
Contact Details:
Dr Ian Cornelius,
ab6459@coventry.ac.uk
