CSE 100 Lecture 40: Finishing Ch. 9
27 Apr 2018
School
Department
Course
Professor
Chapter 9
● 9.5 Sorting an Array of Objects
○ as with searching, arrays to be sorted can contain objects or structures
○ the key field determines how the structures or objects will be ordered
○ when exchanging the contents of array elements, entire structures or objects
must be exchanged, not just the key fields in the structures or objects
○ sorting and searching algorithms can be applied to vectors as well as to arrays
○ You need slight modifications to functions to use vector arguments
■ vector ,type/ & used in prototype
■ There is no need to indicate the vector size, as functions can use the
vector's size member function
● 9.6 Introduction to Analysis of Algorithms
○ given two algorithms to solve a problem, what makes one better than the other?
○ efficiency of an algorithm is measured by
■ space (computer memory used)
■ time (how long to execute the algorithm,)
○ analysis of algorithms is more effective way to find efficiency than by using
empirical data
○ Analysis of Algorithms: Terminology
■ Computational Problem: a problem solved by an algorithm
■ Instance of the Problem: a specific problem that is solved by the algorithm
■ Size of an Instance: the amount of memory needed to hold the data for
the specific problem
○ Analysis of Algorithms:
■ More Terminology
● Basic step: an operation in the algorithm that executes in a
constant amount of time
● Examples of basic steps:
○ exchange the contents of two variables
○ compare two values
● Non-example of a basic step:
○ find the largest element in an array
■ Complexity of an algorithm: the number of basic steps required to execute
the algorithm for an input of size N (N = number of input values)
■ Worst-case complexity of an algorithm: the number of basic steps for
input of size N that requires the most work
■ Average case complexity function: the complexity for typica, average
inputs of size N
○ Comparison of Algorithmic Complexity
■ Given algorithms F and G with complexity functions f(n) and g(n) for input
of size n
Document Summary
As with searching, arrays to be sorted can contain objects or structures. The key field determines how the structures or objects will be ordered. When exchanging the contents of array elements, entire structures or objects must be exchanged, not just the key fields in the structures or objects. Sorting and searching algorithms can be applied to vectors as well as to arrays. You need slight modifications to functions to use vector arguments. There is no need to indicate the vector size, as functions can use the vector"s size member function. Efficiency of an algorithm is measured by. Time (how long to execute the algorithm,) Analysis of algorithms is more effective way to find efficiency than by using empirical data. Computational problem: a problem solved by an algorithm. Instance of the problem: a specific problem that is solved by the algorithm. Size of an instance: the amount of memory needed to hold the data for the specific problem.
