book

Data Structures and Algorithms in Python

by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

March 2013

Intermediate to advanced

748 pages

21h 42m

English

Wiley

Read now

Unlock full access

Book FeaturesOnline ResourcesContents and OrganizationPrerequisitesRelation to Computer Science CurriculumAbout the AuthorsAdditional Books by These AuthorsAcknowledgments
1.1 Python Overview1.2 Objects in Python1.3 Expressions, Operators, and Precedence1.4 Control Flow1.5 Functions1.5.1 Information Passing1.6 Simple Input and Output1.7 Exception Handling1.8 Iterators and Generators1.9 Additional Python Conveniences1.10 Scopes and Namespaces1.11 Modules and the Import Statement1.12 Exercises
2.1 Goals, Principles, and Patterns2.2 Software Development2.3 Class Definitions2.4 Inheritance2.5 Namespaces and Object-Orientation2.6 Shallow and Deep Copying2.7 Exercises
3.1 Experimental Studies3.2 The Seven Functions Used in This Book3.3 Asymptotic Analysis3.4 Simple Justification Techniques3.5 Exercises
4.1 Illustrative Examples4.2 Analyzing Recursive Algorithms4.3 Recursion Run Amok4.4 Further Examples of Recursion4.5 Designing Recursive Algorithms4.6 Eliminating Tail Recursion4.7 Exercises

5.1 Python's Sequence Types5.2 Low-Level Arrays5.3 Dynamic Arrays and Amortization5.4 Efficiency of Python's Sequence Types5.5 Using Array-Based Sequences5.6 Multidimensional Data Sets5.7 Exercises
6.1 Stacks6.2 Queues6.3 Double-Ended Queues6.4 Exercises
7.1 Singly Linked Lists7.2 Circularly Linked Lists7.3 Doubly Linked Lists7.4 The Positional List ADT7.5 Sorting a Positional List7.6 Case Study: Maintaining Access Frequencies7.7 Link-Based vs. Array-Based Sequences7.8 Exercises
8.1 General Trees8.2 Binary Trees8.3 Implementing Trees8.4 Tree Traversal Algorithms8.5 Case Study: An Expression Tree8.6 Exercises
9.1 The Priority Queue Abstract Data Type9.2 Implementing a Priority Queue9.3 Heaps9.4 Sorting with a Priority Queue9.5 Adaptable Priority Queues9.6 Exercises
10.1 Maps and Dictionaries10.2 Hash Tables10.3 Sorted Maps10.4 Skip Lists10.5 Sets, Multisets, and Multimaps10.6 Exercises
11.1 Binary Search Trees11.2 Balanced Search Trees11.3 AVL Trees11.4 Splay Trees11.5 (2,4) Trees11.6 Red-Black Trees11.7 Exercises
12.1 Why Study Sorting Algorithms?12.2 Merge-Sort12.3 Quick-Sort12.4 Studying Sorting through an Algorithmic Lens12.5 Comparing Sorting Algorithms12.6 Python's Built-In Sorting Functions12.7 Selection12.8 Exercises
13.1 Abundance of Digitized Text13.2 Pattern-Matching Algorithms13.3 Dynamic Programming13.4 Text Compression and the Greedy Method13.5 Tries13.6 Exercises
14.1 Graphs14.2 Data Structures for Graphs14.3 Graph Traversals14.4 Transitive Closure14.5 Directed Acyclic Graphs14.6 Shortest Paths14.7 Minimum Spanning Trees14.8 Exercises
15.1 Memory Management15.2 Memory Hierarchies and Caching15.3 External Searching and B-Trees15.4 External-Memory Sorting15.5 Exercises

Content preview from Data Structures and Algorithms in Python

Chapter 12 Sorting and Selection

images

Contents

12.1 Why Study Sorting Algorithms?

Much of this chapter focuses on algorithms for sorting a collection of objects. Given a collection, the goal is to rearrange the elements so that they are ordered from smallest to largest (or to produce a new copy of the sequence with such an order). As we did when studying priority queues (see Section 9.4), we assume that such a consistent order exists. In Python, the natural order of objects is typically¹ defined using the < operator having following properties: