It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.

# CISC 3130 Data Structures: Algorithms

Professor Chuang Spring 2020 OER

## What are algorithms?

Algorithms refer to the logistics in manipulating data in these structures, such as searching or sorting. It is a method for solving a problem expressed as a sequence of steps. It serves the role that recipe is used in cooking.

Main Points

• We are interested in designing good algorithms, so we have to be able to measure the performance.
• Good algorithms are measured by running time and space usage. This is to say we could measure the space or time complexity required.
• Often, the metric is the maximum number of operations. The upper bound of possible operations, which is commonly called Big O where O is used to denote the order of growth.

## Visualizations https://visualgo.net/en https://www.toptal.com/developers/sorting-algorithms http://sorting.at/

## Algorithms

Sorting Algorithms

• Simple Sorts
• Divide & Conquer
• Recursive

Searching Algorithms

• Linear Search
• Binary Search

Tree Traversals

• Depth First Search
• Binary Search

Algorithm Chapter
Linear Search,
Binary Search
Lafore Ch 2
Bubble Sort,
Insertion Sort,
Selection Sort
Lafore Ch 3
Quicksort Lafore Ch 7,
CLRS Ch 7
Mergesort Lafore Ch 6,
CLRS Ch
Heapsort

Lafore Ch 12,

CLRS Ch6

Tree Traversal Lafore Ch 8

## Comparing Sorting Algorithms

Big O notation for algorithm efficiency

Sorting Algorithm Worst Case Best Case In Place? Stability
Bubble Sort O(n2) O(n) Yes Yes
Insertion Sort O(n2) O(n) Yes Yes
Selection Sort O(n2) O(n2) Yes No - When moving selected value,
it introduces a new index.
Mergesort O(nlogn) O(nlogn) No - Requires additional memory for
merge operation.
Yes
Quicksort O(n2) O(nlogn) Yes No - partitioning based on pivot
values moves elements into
different locations
Heapsort O(nlogn) O(nlogn) Yes No - heapify reshifts nodes in the
heap