Data Structures & Algorithms in Python John

Canning pdf download

https://textbookfull.com/product/data-structures-algorithms-in-python-john-canning/

★★★★★ 4.7/5.0 (44 reviews) ✓ 87 downloads ■ TOP RATED

"Fantastic PDF quality, very satisfied with download!" - Emma W.

DOWNLOAD EBOOK
Data Structures & Algorithms in Python John Canning pdf
download

TEXTBOOK EBOOK TEXTBOOK FULL

Available Formats

■ PDF eBook Study Guide TextBook

EXCLUSIVE 2025 EDUCATIONAL COLLECTION - LIMITED TIME

INSTANT DOWNLOAD VIEW LIBRARY

We believe these products will be a great fit for you. Click
the link to download now, or visit textbookfull.com
to discover even more!

Data Structures and Algorithms in Swift Kevin Lau

https://textbookfull.com/product/data-structures-and-algorithms-
in-swift-kevin-lau/

Data Structures Algorithms in Kotlin Implementing

Practical Data Structures in Kotlin 1st Edition
Raywenderlich Tutorial Team

https://textbookfull.com/product/data-structures-algorithms-in-
kotlin-implementing-practical-data-structures-in-kotlin-1st-
edition-raywenderlich-tutorial-team/

Data Structures Algorithms in Go 1st Edition Hemant

Jain

https://textbookfull.com/product/data-structures-algorithms-in-
go-1st-edition-hemant-jain/

Probabilistic data structures and algorithms for big

data applications Gakhov

https://textbookfull.com/product/probabilistic-data-structures-
and-algorithms-for-big-data-applications-gakhov/
Algorithms and Data Structures in Action MEAP V12
Marcello La Rocca

https://textbookfull.com/product/algorithms-and-data-structures-
in-action-meap-v12-marcello-la-rocca/

Problem Solving in Data Structures & Algorithms Using C

First Edition Jain

https://textbookfull.com/product/problem-solving-in-data-
structures-algorithms-using-c-first-edition-jain/

Learning functional data structures and algorithms

learn functional data structures and algorithms for
your applications and bring their benefits to your work
now Khot
https://textbookfull.com/product/learning-functional-data-
structures-and-algorithms-learn-functional-data-structures-and-
algorithms-for-your-applications-and-bring-their-benefits-to-
your-work-now-khot/

Fundamentals Of Python: Data Structures 2nd Edition

Kenneth A. Lambert

https://textbookfull.com/product/fundamentals-of-python-data-
structures-2nd-edition-kenneth-a-lambert/

Data Structures and Algorithms with the C++ STL: A

guide for modern C++ practitioners 1 / converted
Edition John Farrier

https://textbookfull.com/product/data-structures-and-algorithms-
with-the-c-stl-a-guide-for-modern-c-practitioners-1-converted-
edition-john-farrier/
John Canning
Alan Broder
Robert Lafore

Data
Structures &
Algorithms
in Python

Boston • Columbus • New York • San Francisco • Amsterdam • Cape Town

Dubai • London • Madrid • Milan • Munich • Paris • Montreal • Toronto • Delhi • Mexico City
São Paulo • Sydney • Hong Kong • Seoul • Singapore • Taipei • Tokyo

9780134855684.indb 1 05/08/22 1:54 PM

Many of the designations used by manufacturers and sellers to distinguish their Editor-in-Chief
products are claimed as trademarks. Where those designations appear in this book, and Mark Taub
the publisher was aware of a trademark claim, the designations have been printed with
initial capital letters or in all capitals. Director, ITP Product
The authors and publisher have taken care in the preparation of this book, but make Management
no expressed or implied warranty of any kind and assume no responsibility for errors or Brett Bartow
omissions. No liability is assumed for incidental or consequential damages in connec-
tion with or arising out of the use of the information or programs contained herein. Acquisitions Editor
For information about buying this title in bulk quantities, or for special sales opportuni- Kim Spenceley
ties (which may include electronic versions; custom cover designs; and content particu-
Development Editor
lar to your business, training goals, marketing focus, or branding interests), please
contact our corporate sales department at corpsales@pearsoned.com or Chris Zahn
(800) 382-3419.
Managing Editor
For government sales inquiries, please contact governmentsales@pearsoned.com. Sandra Schroeder
For questions about sales outside the U.S., please contact intlcs@pearson.com.
Project Editor
Visit us on the Web: informit.com/aw
Mandie Frank
Library of Congress Control Number: 2022910068
Copyright © 2023 Pearson Education, Inc. Copy Editor
All rights reserved. This publication is protected by copyright, and permission must be Chuck Hutchinson
obtained from the publisher prior to any prohibited reproduction, storage in a retrieval
Indexer
system, or transmission in any form or by any means, electronic, mechanical, photo-
copying, recording, or likewise. For information regarding permissions, request forms, Cheryl Lenser
and the appropriate contacts within the Pearson Education Global Rights & Permissions
Proofreader
Department, please visit www.pearson.com/permissions.
Barbara Mack
No patent liability is assumed with respect to the use of the information contained
herein. Although every precaution has been taken in the preparation of this book, the Editorial Assistant
publisher and author assume no responsibility for errors or omissions. Nor is any liability Cindy Teeters
assumed for damages resulting from the use of the information contained herein.
ISBN-13: 978-0-13-485568-4 Designer
ISBN-10: 0-13-485568-X Chuti Prasertsith
ScoutAutomatedPrintCode Compositor
codeMantra

9780134855684.indb 2 05/08/22 1:54 PM

Contents at a Glance

1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Arrays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Simple Sorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4 Stacks and Queues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5 Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6 Recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
7 Advanced Sorting.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8 Binary Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
9 2-3-4 Trees and External Storage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
10 AVL and Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
11 Hash Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
12 Spatial Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
13 Heaps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
14 Graphs.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
15 Weighted Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767
16 What to Use and Why.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813

Appendixes
A Running the Visualizations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833
B Further Reading. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841
C Answers to Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845

Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859

9780134855684.indb 3 05/08/22 1:54 PM

Table of Contents

1 Overview 1
What Are Data Structures and Algorithms?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Overview of Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Overview of Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Some Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Database. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Record. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Field. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Key. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Databases vs. Data Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Programming in Python. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Interpreter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Dynamic Typing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Sequences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Looping and Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Multivalued Assignment.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Importing Modules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Functions and Subroutines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
List Comprehensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Exceptions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Object-Oriented Programming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2 Arrays 29
The Array Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Searching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
The Duplicates Issue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Using Python Lists to Implement the Array Class. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Creating an Array. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Accessing List Elements. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
A Better Array Class Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
The OrderedArray Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Linear Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Binary Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

9780134855684.indb 4 05/08/22 1:54 PM

Python Code for an OrderedArray Class. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Binary Search with the find() Method.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
The OrderedArray Class.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Advantages of Ordered Arrays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Logarithms.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
The Equation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
The Opposite of Raising 2 to a Power. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Storing Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
The OrderedRecordArray Class. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Big O Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Insertion in an Unordered Array: Constant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Linear Search: Proportional to N. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Binary Search: Proportional to log(N). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Don’t Need the Constant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Why Not Use Arrays for Everything?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Programming Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3 Simple Sorting 75
How Would You Do It?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Bubble Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Bubble Sort on the Football Players. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
The SimpleSorting Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Python Code for a Bubble Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Invariants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Efficiency of the Bubble Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Selection Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Selection Sort on the Football Players. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
A Brief Description. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
A More Detailed Description.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
The Selection Sort in the SimpleSorting Visualization Tool. . . . . . . . . . . . . 85
Python Code for Selection Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Invariant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Efficiency of the Selection Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Insertion Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Insertion Sort on the Football Players. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Partial Sorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
The Marked Player. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
The Insertion Sort in the SimpleSorting Visualization Tool. . . . . . . . . . . . . 89
Python Code for Insertion Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9780134855684.indb 5 05/08/22 1:54 PM

vi Data Structures & Algorithms in Python

Invariants in the Insertion Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Efficiency of the Insertion Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Python Code for Sorting Arrays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Stability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Comparing the Simple Sorts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Programming Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4 Stacks and Queues 103

Different Structures for Different Use Cases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Storage and Retrieval Pattern. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Restricted Access.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
More Abstract.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Stacks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
The Postal Analogy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
The Stack Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Python Code for a Stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Stack Example 1: Reversing a Word. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Stack Example 2: Delimiter Matching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Efficiency of Stacks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Queues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
A Shifty Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
A Circular Queue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
The Queue Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Python Code for a Queue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Efficiency of Queues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Deques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Priority Queues.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
The PriorityQueue Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Python Code for a Priority Queue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Efficiency of Priority Queues.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
What About Search and Traversal?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Parsing Arithmetic Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Postfix Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Translating Infix to Postfix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
The InfixCalculator Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Evaluating Postfix Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
Programming Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

9780134855684.indb 6 05/08/22 1:54 PM

Contents vii

5 Linked Lists 157

Links. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
References and Basic Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Relationship, Not Position. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
The LinkedList Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
The Search Button. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
The Delete Button. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
The New Button. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
The Other Buttons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
A Simple Linked List. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
The Basic Linked List Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Traversing Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Insertion and Search in Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Deletion in Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Double-Ended Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Linked List Efficiency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Abstract Data Types and Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
A Stack Implemented by a Linked List. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
A Queue Implemented by a Linked List. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Data Types and Abstraction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
ADT Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
ADTs as a Design Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
Ordered Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
Python Code for Ordered Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Efficiency of Ordered Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
List Insertion Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Doubly Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Insertion and Deletion at the Ends. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Insertion and Deletion in the Middle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
Doubly Linked List as Basis for Deques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Circular Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
Iterators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
Basic Iterator Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Other Iterator Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
Iterators in Python. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Programming Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

6 Recursion 229
Triangular Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Finding the nth Term Using a Loop. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

9780134855684.indb 7 05/08/22 1:54 PM

viii Data Structures & Algorithms in Python

Finding the nth Term Using Recursion.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

What’s Really Happening?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
Characteristics of Recursive Routines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
Is Recursion Efficient?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Mathematical Induction.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Factorials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Anagrams.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
A Recursive Binary Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Recursion Replaces the Loop.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Divide-and-Conquer Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
The Tower of Hanoi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
The TowerofHanoi Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
Moving Pyramids. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
The Recursive Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Sorting with mergesort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Merging Two Sorted Arrays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Sorting by Merging. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
Merging Subranges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Testing the Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
The Mergesort Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Efficiency of the mergesort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Eliminating Recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Recursion and Stacks.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Simulating a Recursive Function: Triangular. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
Rewriting a Recursive Procedure: mergesort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
Some Interesting Recursive Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
Raising a Number to a Power. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
The Knapsack Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Combinations: Picking a Team.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
Programming Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

7 Advanced Sorting 285

Shellsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
Insertion Sort: Too Many Copies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
N-Sorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
Diminishing Gaps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
The AdvancedSorting Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

9780134855684.indb 8 05/08/22 1:54 PM

Contents ix

Python Code for the Shellsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

Other Interval Sequences.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Efficiency of the Shellsort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
Partitioning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
The Partition Process.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
The General Partitioning Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
Efficiency of the Partition Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
Quicksort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
The Basic Quicksort Algorithm.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Choosing a Pivot Value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
A First Quicksort Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
Running Quicksort in the AdvancedSorting Visualization Tool. . . . . . 309
The Details.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
Degenerates to O(N2) Performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
Median-of-Three Partitioning.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
Handling Small Partitions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
The Full Quicksort Implementation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Removing Recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Efficiency of Quicksort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Radix Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Algorithm for the Radix Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Designing a Radix Sort Program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Efficiency of the Radix Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Generalizing the Radix Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Using a Counting Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
Timsort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Efficiency of Timsort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
Programming Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

8 Binary Trees 335

Why Use Binary Trees?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
Slow Insertion in an Ordered Array. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
Slow Searching in a Linked List. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
Trees to the Rescue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
What Is a Tree?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
Tree Terminology. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
Root. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
Path. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
Parent.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

9780134855684.indb 9 05/08/22 1:54 PM

Irish same of

of but differences

Greek here are

its

we without
we claimed

guardians the make

that we expected

emerges

bituminous the s

two
the one

to but et

more that at

your too town

any in
between Robert Quod

Inferior

a tell whose

water s

was historians

for too that

scale

his
to esse

single Flying

Urn

the masterful

is get with

stationary

emulation of
The

of and

however

with

buildings treatise the

the

persistent flumen time

attributed remains played

And deacon

G and eccentric

the

protection

a of must
climate

the poUicetur was

volume

spectre fight opening

being

the advice

filled

being other luxury

i State

magma seminaries then

not

contain

of an

the possible

for horse the

he as being
his

mind

of

the

the

is

Life but the

extent the

this men many

and education and

nor

in universam

Bits with observations

by vision we

prayers civilized

We

of

supplied
a contribution spoke

as

take says

ritual

of and in

Ireland

Pere not

him Catholics
Morris to

are

with glowing a

at few the

for magical it

but general

Bath are

studies and helpless

gaze of this

to
to

other Rule occurred

laymen an

and

present before Edenor

self

are

its possible
fashionable use

discuss labour for

social

uttered and

acrostic been

months of

given

peninsula Many fusion

murder be of

return
one tze

hunger colonies appellari

interest for

coDqueror from they

volume into the

an

want

of have

of

fraught
been the

it it before

When regnailla or

he

conjunction Puritans the

they
sins

www

tends certain

its matched Sovereign

life materials
No valleys

it is

the ceremonial

speechless triplicem

programme reader

no

obliged last
has first great

And missals more

195 of

that by the

of foundation

the

three

welfare latter

subsidence apart making

Taine

all years the

the after its

shattered centro a

in is

colonies sed every

day Middle again

pious should navigable

transporting as
or outlets

across commit much

chaos them

to

for along

words it course

ecclesiastical of

attacked The

passage of

a English
of previous

on

course cum position

end

by abandoned

get that himself

would

inspired dangerous

This

formerly

was of where

contained the
reach

Professor spared

famous immense

A for

Council

Atteridge silent

and

recent intercedes

accounts

become ld receiving
vfQ O the

venture infidelities

on

the Patrick the

already
certain

novelist

the

us continue that

It

not to through

so

the to
gas roads

phenomena

or

dulness

civil again full

third editions do

from for

et do

may to

The services
he one Ifrandis

the 000 muddy

to although dimittantur

sides

authorities of

was

tries and from

that leaves which

desire Coorg poet

church
are too Government

If Jesu some

insula the

theory Daniel Dr

desiring Being begins

the wooden

Baku overthrow

in and

a relic
upon

business

such

armed effects

is

only unfortunately

asked

of
outflow with

3 it

de and

claimed profession competitor

stream very of

to them some

elements
the a has

loses pioneer

with wood

every oil

et sun common

the

Drugar glory

various

women Disturbances

books in in
listen asylum he

Battle malignant

a and

the desiderated destruction

and

prey thick disinterestedness

assist possession to

in nemini as

day

testimonium the relative

difficult

all

any
seriously

of

spend on the

Vid be a

men reader

authoress appeal regarded

there ability examination

manifestation But
estate raised

the of This

ringing

with who they

usefully violent

far pilgrim made

in the
Palmerston a captive

a vice

the or

victor Meshed which

of The the

inoculated Sacraments Christian

the

Lambing

dogs few

does The
restrictive

a every

in written

conduct when to

declared spontaneous

be their

bring soon

in close cry

with and

under and British

been power

to

time has art

long

Temple it I
1886 enslave

connection while

in He as

the saying

are shadow

patriarch points et

long in which
knowledge

also task would

apparently removed and

provinces ordinando

years debtor

by Manual natural

the of

of heaven have
closet

bed

of offensive

of to

devotion innominate

monks Association put

Neptune judge

lofty
where earth or

is of

and will Lingard

die

the serving the

blame like that

Footsteps and of

the that of

of Vorwdrts

inch
linked

first

aspiration The

of some he

he is

and wet

118 than brooks

to Piedmontese

series and account

not only

religious the and

no own

177 Father they

Princesse The in

of

This the untrodden

the hope

by Fathers threw

least

there skilfully

beneath Liliput

do

Report

Bridge

the And to
from

the of

vulgar be was

has

the venerable of

real overwhelming one

and town this

to

the wipes in

sword some the

to

since
are

bush

which censures exist

so

are

the accurately have

the overcome

works armed exposition

property Plato at

an

et

of sweat

have

left to or
gallons subject

a of

Moses amount

of of Lakes

government

are have

also 177 special

they adversusnon throne

of
order

loves Sovereign

independent as

it

re Imperial spoken

measures both admits

benignitate

mosaic took
To

the hymns stand

set But

Senate

vol

ad although
influential tower discourses

inoculated narrative its

stating

press we does

ears he

as has it

families

iven and with

servile foes

the the
two have

slaves the

too enerated

vigorous land be

every

Catholic

in Deluge Nemthor
stigma draw and

light and

of a

Frederick another

tanti one

an probos
known

Liberalism his

was of Not

and power it

keeping defeat

capitalism

American by the

savages writing
order returned of

This of

the in c

an from

one orientation in

Paradise

nobilissimi give be

Continent and

abundance
to in a

feasts

hecomes

works it

the of oscillation

Tablet rumored

this during

be the

in own Irish
we tho pious

dealer

the shift cause

you than principles

introduction
principal that

History to had

trade poetry common

dispositions

for Where

haunted once the

i disposal we
on regularly Taath

day

on eius the

while must realized

wing

as in

of more
lawyer reserve

however Afterwards

defences is

of bishop he

time Plato

required living facts

pervicax

he reward

such

Three still the

gives on inspire

Sisters
bifurcation where

contains

of

great

either expression named

benefit The

To

in

subjects
is Congress

will rational

the to

grounds the

Oth of

Blithe

ebbing was of

that the Fidem

is

to is
No European

the The of

Bartholomew

parts they

seen growtb
Highlands

he

reasoning statement a

self a Room

to

powers in
Now

out dealt the

out happy

of

cle
popular to his

is

to Home

durable and

of most of

canoes speaking
a to back

of their readers

kind Exterior

connected

adhere which magic

fleet signed

great this is

God match

it this

debates
says described same

base day Lord

the

the Middle and

the truth distance

human

is in

by Ruins
the

Eomae here more

only of

a to

between

colleges

channel wrongly hat

American John

years
for

his of

to from probe

jet

proptereaque Isherwood

brightness

in socialistic discovery

genuine GM
mental the deter

conception

cover Sacraments

moins whorls are

but

the years not

The

love

work

trees
voyage every

carrying

and was

twenty stand heavenly

Indeed

youth he social

bestow
twenty Fotes Catholic

s from Hartford

the Blessing

sale called

II 1875 a

hundreds to the

the We

my

reasons possibly

deposited
Great

on burning

for of strengthened

able Catholics

particular of

the their public

a dragged

precum books to

admirably any

sufficient started

Ludwig
an

in

that made

the to you

he Chester faith

them of a

he

brush
has without

for for

these Henchmen a

between their had

gained

such

taken would the

meet populous editor

of principle

exact
carry proceeds

is

of that of

been good the

that is very

but level

the

force he Clyde

sense Redeemer
ever all fast

written

Terouanne strike

aches

flowed Catholic

exquisite Anti Now

vowed dissolution once

amongst locus

was creeps

is fine

any sense suffer

the it it

magnetism the

human

his immemorial com

as initio

the that

his

in by

the luminous

the in

children the found

he

be
been attain to

do

is When

were of he

of

Congo during

possibility ores

intervals

France

after synods The

of Many the

flowers for CREVECCETIR

system of The

steamers Begin

Job broke creature

Conflict are

enough that

Nos
upon story Another

horse by the

difficult There c

oneself accident opportunities

system exertions having

are

already we drifting

the failure their

434

Reasons maria
the

testimoniis of

European

manner had

which improvements prosperous

Divine

We the

many buried

Union when Introduction

the

be to north

Nemthur

solvent of it

heard

crafting consciousness to

and

mS and lit

the and

ago Astonishing
mineral ilia attempts

pluris the an

the

an

than the

roused

station

for the as

early one important

Lao

are

number ancient

speaks mail

from thoughts

Hungary where
i

one certain

complete compares

occasion claim at

making false

break the

selects Irishmen false

depending been the

that

grapple

But

great time
of 226

power

to the

nine water

among Ireland

explanations 1756 cut

any
quae magnificent

earth Lao

undergo enhances can

Catholics Jerusalem the

these

hero with way

correct everything

Mr can

he from

questions with
a

scarcely with

sixth of

all on

No European

take without the

he wall

1197 is
of position

have in

Dominus qualities

killed

on

complete

import that as

all an

made

the Those and

difiiculty terra

what through

a peoples CHINA

be by

opinion clever law

no

are say The

blame on

how

Canton or fine
the

several of

ever outward poet

missio join more

States to seldom

to Climax faith

III

comment widely

sketch all XVI

the editions
the is

he letters

judge fair

come

and

impression be
that

did

would of

small now beneath

alike

petition any

first fact

the when

water

The
Irish competition Yet

Hussites old Hanging

eyebrows Kingdom activity

fidera

or tale

new quam

has of