Binary Search and Selection, Bubble, and Insertion Sort

Chapter 18

Introduction

Objectives

After the next two lectures and labs, you will be able to:

Implement the sequential and binary search algorithms.
Explain how these search algorithms perform.
State lower bound on comparison-based search algorithms.
Implement various sorting algorithms.
Use the asymptotic notation, Big-, to analyze these algorithms’ performance.

With a Search Algorithm, you can:

Determine whether a particular item is in an array or list.
If the data is specially organized (for example, sorted), find the location in the list where a new item can be inserted.
Find the location of an item to be deleted.

Search Algorithm Terminology

An item’s key – a special member that uniquely identifies the item in the data set.
A key comparison – comparing the key of the search item with the key of an item in the list.
- We can count the number of key comparisons as a measure of performance.
The key that we are searching for is called the target or search item.

Sequential Search

Sequential Search (a.k.a. Linear Search)

Same for both array-based and linked lists.
Starts at the first element and examines each element until a match is found.
Can be implemented iteratively (using a loop) or recursively.

Iterative Sequential Search of ArraysRecursive Sequential Search of Arrays

C++

template <typename Type>
unsigned int sequentialSearch(const Type array[], 
	unsigned int size, const Type& key)
{
	unsigned int index;

	// Iterate until we find the key or reach the end of the array
	for (index = 0; index < size && array[index] != key; ++index)
	{
	}

	// If we found the key, return the index, otherwise return UINT_MAX
	return index < size ? index : UINT_MAX;
}

C++

template <typename Type>
unsigned int sequentialSearchRecursive(const Type array[], 
	unsigned int size, const Type& key)
{
	unsigned int index;

	// Base case, empty list
	if (size == 0)
	{
		index = UINT_MAX;
	}

	// Base case, key found in first location
	else if (array[0] == key)
	{
		index = 0;
	}

	// Recursive case, run these checks again with a smaller array.
	else
	{
		// Call ourself
		index = sequentialSearchRecursive(array + 1, size - 1, key);
		if (index != UINT_MAX)
			++index;
	}

	return index;
}

Key Comparisons of a Sequential Search

Remember, the speed of a computer does not affect the number of key comparisons required.
Statements before and after the loop are executed only once, .
Statements in the while loop repeated some number from 1 to times (where is the number of keys).
If the search key is not in the list, there will be comparisons.
In the best case, the first key matches the search item with just one comparison.
In the worst case, the target is not in the list, so there will be comparisons.
Average number of comparisons:

Binary Search (for Sorted Lists)

Binary search can be applied to sorted arrays or lists.
Uses the “divide and conquer” technique.
Steps
1. First, compare the target to the middle element.
2. If the search item is less than the middle element, restrict the search to the lower half of the list.
3. Otherwise, restrict the search to the upper half of the list.
4. Repeat until found.

Find the location of 75 in this sorted array.

1 / 1

The Performance of the Binary Search on Arrays

Every iteration cuts the size of the search list in half.
If list has items, at most iterations are needed to find .
Every iteration makes two key comparisons.
- For , binary search has at most key comparisons.
- Max number of comparisons = .
- The sequential search required key comparisons (average) to find if is in .

Asymptotic Notation (Big-O Notation)

After an algorithm is designed, it should be analyzed.
There are often various ways to design a particular algorithm.
Certain algorithms take very little computer time to execute.
Others take a considerable amount of time.


1	0	0	1	2
2	1	2	4	4
4	2	8	16	16
8	3	24	64	256
16	4	64	256	65,536
32	5	160	1,024	4,294,967,296
64	6	384	4,096	1.84467e+19

Time for instructions if executing 1-billion instructions per second. * μs is a microsecond or 10e-6 seconds.

μs	μs	μs	μs	μs
μs	μs	μs	μs	ms
μs	μs	μs	μs	μs
μs	μs	μs	μs	min
μs	μs	μs	μs	days
μs	μs	μs	μs	years
μs	μs	μs	ms
μs	μs	μs	ms
ms	μs	ms	μs
ms	μs	ms	m
μs	μs	μs	days
μs	μs	μs	days

Let be a function of .
Asymptotic: the study of the function as becomes larger and larger without bound.
Let and be real-valued, non-negative functions.
is Big-O of , written if there are constants and such that

Growth Rate


10	100	160
50	2,500	2,720
100	10,000	10,420
1,000	1,000,000	1,0004,020
10,000	100,000,000	100,040,020
100,000	10,000,000,000	10,000,400,020

Growth Rate Functions

Function	Growth rate of
	Constant (is independent of the problem’s size).
	Logarithmic (increases increases slowly as the problem size increases).
	Linear (increases directly with the size of the problem).
	(increases more rapidly than a linear algorithm).
	Quadratic (increases rapidly with the size of the problem).
	Cubic (increases more rapidly with the size of the problem than the time requirement for a quadratic algorithm).
	Exponential (too rapid to be practical, as the size of the problem increases).

Comparing Sequential and Binary Search

Algorithm	Successful Search	Unsuccessful Search
Sequential Search
Binary Search

The number of comparisons for a list of length .

Lower Bound on Comparison-Based Search

Comparison-based search algorithms: Search a list by comparing the target element with list elements.

Theorem: Let be a list of size . Suppose that the elements of are sorted. If denotes the minimum number of comparisons needed, in the worst case, by using a comparison-based algorithm to recognize whether an element is in , then .

Corollary: The binary search algorithm is an optimal worst-case algorithm for solving search problems by the comparison method. From these results, it follows that if we want to design a search algorithm that is of an order less than , then it cannot be comparison based.

Sorting Algorithms

To compare the performance of commonly used sorting algorithms, one must provide some analysis of these algorithms.
These sorting algorithms can be applied to either array-based lists or linked lists.

Selection Sort

The Selection Sort Algorithm: rearrange the list by selecting an element and moving it to its proper position.
Steps for a selection sort:
- Find the smallest element in the unsorted portion of the list
- Move it to the top of the unsorted portion by swapping it with the currently-first element.
- Start again with the rest of the list.
Can also be applied to linked lists.

Example Selection Sort:

1 / 1

Analysis: Selection Sort

swap:
Does three assignments; executed times.
minIndex:
- For a list of length , key comparisons.
- Executed times (by selectionSort)
- The number of key comparisons:

Bubble Sort

Suppose list[0]...list[n-1] is a list of elements, indexed to .
In a series of iterations, compare successive elements, list[index] and list[index + 1].
If list[index] is greater than list[index + 1], then swap them.

Example Bubble Sort:

1 / 1

Performance Analysis

The Bubble-Sort algorithm contains nested loops.
- The outer loop executes times.
- For each iteration of the outer loop, the inner loop executes a certain number of times.
The total number of comparisons is:
The number of assignments (worst case):
because there are 3 assignments per swap operator.

Insertion Sort

The insertion sort algorithm sorts the list by moving each element to its proper place in the sorted portion of the list.

Example Insertion Sort:
(This diagram shows just the first few steps.)

1 / 1

Implementation for Arrays

Let’s implement the Insertion Sort.

Performance Analysis

The for-loop executes times.
Best case (list is already sorted):
Key comparisons:
Worst case: for each iteration, the if statement evaluates to true.
Key comparisons:
Average number of key comparisons and of item assignments:

Lower Bound

Sorting Algorithm Comparison

Average Case Behavior of the Bubble Sort, Selection Sort, and Insertion Sort Algorithms for a List of Length .

Algorithm	Comparisons	Swaps
Bubble Sort
Selection Sort
Insertion Sort (Array Based)
Insertion Sort (Linked-List Based)

Lower Bound on Comparison-Based Sort Algorithms

Can we do better than for sorting?

What is the best we can do?

(Find the answers to these questions in the next module.)

Lab 10: Selection Sort, Bubble Sort, and Binary Search

Let’s take a look at Lab 10.

Binary Search and Selection, Bubble, and Insertion Sort ​

Introduction ​

Objectives ​

With a Search Algorithm, you can: ​

Search Algorithm Terminology ​

Sequential Search ​

Sequential Search (a.k.a. Linear Search) ​

Key Comparisons of a Sequential Search ​

Binary Search (for Sorted Lists) ​

The Performance of the Binary Search on Arrays ​

Asymptotic Notation (Big-O Notation) ​

Growth Rate ​

Growth Rate Functions ​

Comparing Sequential and Binary Search ​

Lower Bound on Comparison-Based Search ​

Sorting Algorithms ​

Selection Sort ​

Analysis: Selection Sort ​

Bubble Sort ​

Performance Analysis ​

Insertion Sort ​

Implementation for Arrays ​

Performance Analysis ​

Lower Bound ​

Sorting Algorithm Comparison ​

Lower Bound on Comparison-Based Sort Algorithms ​

Lab 10: Selection Sort, Bubble Sort, and Binary Search ​

Binary Search and Selection, Bubble, and Insertion Sort

Introduction

Objectives

With a Search Algorithm, you can:

Search Algorithm Terminology

Sequential Search

Sequential Search (a.k.a. Linear Search)

Key Comparisons of a Sequential Search

Binary Search (for Sorted Lists)

The Performance of the Binary Search on Arrays

Asymptotic Notation (Big-O Notation)

Growth Rate

Growth Rate Functions

Comparing Sequential and Binary Search

Lower Bound on Comparison-Based Search

Sorting Algorithms

Selection Sort

Analysis: Selection Sort

Bubble Sort

Performance Analysis

Insertion Sort

Implementation for Arrays

Performance Analysis

Lower Bound

Sorting Algorithm Comparison

Lower Bound on Comparison-Based Sort Algorithms

Lab 10: Selection Sort, Bubble Sort, and Binary Search