Sorting Algorithms - Lecture 2

Important Problem Types - Lecture 2

• Sorting algorithms rearrange arrays or lists of elements based on a comparison operator.
• Examples include sorting words alphabetically, cities by population, or lists by length.
• Many algorithms benefit from sorted data.
• Large datasets require substantial computing resources for sorting.
• Efficiency depends on the number of items being processed.

Sorting Algorithm Properties

• Stable: A stable sorting algorithm maintains the relative order of equal elements in the input.
• In-place: An in-place algorithm sorts data without requiring extra memory beyond a few memory units.

Types of Sorting

• Internal Sorting: Occurs when all data fits in main memory. The size of the input must fit in the available memory.
• External Sorting: Used for very large datasets that don't fit in memory. External storage, such as hard drives or CDs, is necessary. Typical external sorting algorithms include merge sort variations. Example algorithms include: Merge Sort, Tag Sort, Polyphase Sort, Four tape sort, External radix sort, Internal merge sort, etc.

Types of Sorting Algorithms

• Selection sort
• Insertion sort
• Bubble sort
• Merge sort
• Quick sort
• Heap sort
• Shell sort

Searching

• The goal is to find a specific value, the search key, within a set or multiset (allowing duplicates).
• Unlike sorting, stability is not an issue.
• Common searching algorithms include:
  • Linear search (sequential search)
  • Binary search

Search Algorithms

• Linear Search: Locates an element by sequentially checking each item in a list until a match is found.
• Binary Search: Efficiently searches ordered lists by repeatedly dividing the search interval in half. This method requires a sorted list.

String Processing

• Strings in computer science can comprise letters, numbers, special characters, bits (zeros and ones), and gene sequences.
• String matching algorithms are crucial for various tasks like text processing, data mining, and information retrieval.
• They locate specific patterns within larger bodies of text or strings.

Defining Strings

• In computer memory, strings are stored as lists of individual characters.

Graph Problems

• Graph algorithms are used to model various applications like networks, communication, and games.
• Graph traversal algorithms help explore all points in a network.
• Shortest-path algorithms find the most efficient routes.
• Topological sorting determines if sets of tasks with dependencies can be completed in a consistent sequence.

Task 1 - Comparison Counting Sort

• An algorithm sorting an array by counting the number of smaller elements for each element and using this information to place it correctly in the sorted array.
• Algorithm is presented, including nested loops.
• The algorithm sorts the array in a nondecreasing order

Task 2 - Algorithm Analysis

• Analyze different sorting and searching algorithms.
• Determine the appropriate metric for each algorithm's input size.
• Identify the fundamental operation of each algorithm as well as the count of that operation.
• Examples include the sum of n numbers, n!, largest element in a list, etc.

Analysis of Algorithms

• Issues: Correctness, time efficiency, space efficiency, optimality.
• Approaches: Theoretical and empirical analysis.

Fundamentals of Algorithm Efficiency

• Time efficiency (time complexity) measures how quickly an algorithm processes data.
• Space efficiency (space complexity) measures the extra memory space an algorithm needs. -Focus is on time efficiency
• speed is more important in regard to progress than space

Analysis Framework

• Algorithm inputs generally run longer on larger sets of data.
• Time efficiency analysis involves counting the repetitions of the most important operation in the algorithm based on the input size.

Input size and Basic Operations Examples

• Different problems have different ways of measuring input sizes and characterizing basic operations.

Unit for Measuring Running Time

• The basic operation is the most significant operation in regards to total runtime.
• The execution time for a basic operation.
• The number of times the basic operation is performed.

Best, Worst, and Average Case Analysis

• Some algorithms' performance varies depending on the input.
• Worst-case analysis considers the maximum number of operations.
• Best-case analysis considers the minimum number of operations.
• Average-case analysis considers the expected number of operations.

Example: Sequential Search

• A sequential search algorithm to locate a specific value (search key) within a given array, if it exists.
• The worst-case scenario involves checking all elements.
• Best-case involves checking only the first element.
• Algorithm code is presented (pseudocode).

Linear Search

• This is an example algorithm for executing a linear search.
• It demonstrates a step-by-step approach

Probability-Based Average-Case Analysis of Sequential Search

• Average-case analysis is based on the probability of finding the element you are looking for at each position of the list.

Types of Formulas for Basic Operation Counts

• Exact formulas
• Formulas indicating order of growth with a known multiplicative constant
• Formulas indicating order of growth with an unknown multiplicative constant

Efficiencies of Algorithms

• Time and space efficiencies are based on the algorithm's input size.
• Time efficiency is based upon how many times the basic operation occurs.
• Space efficiency is measured by counting the extra memory required by the algorithm. -Distinguishing worst, average, and best cases.