Book Image

Getting Started with Python

By : Fabrizio Romano, Benjamin Baka, Dusty Phillips
Book Image

Getting Started with Python

By: Fabrizio Romano, Benjamin Baka, Dusty Phillips

Overview of this book

This Learning Path helps you get comfortable with the world of Python. It starts with a thorough and practical introduction to Python. You’ll quickly start writing programs, building websites, and working with data by harnessing Python's renowned data science libraries. With the power of linked lists, binary searches, and sorting algorithms, you'll easily create complex data structures, such as graphs, stacks, and queues. After understanding cooperative inheritance, you'll expertly raise, handle, and manipulate exceptions. You will effortlessly integrate the object-oriented and not-so-object-oriented aspects of Python, and create maintainable applications using higher level design patterns. Once you’ve covered core topics, you’ll understand the joy of unit testing and just how easy it is to create unit tests. By the end of this Learning Path, you will have built components that are easy to understand, debug, and can be used across different applications. This Learning Path includes content from the following Packt products: • Learn Python Programming - Second Edition by Fabrizio Romano • Python Data Structures and Algorithms by Benjamin Baka • Python 3 Object-Oriented Programming by Dusty Phillips
Table of Contents (31 chapters)
Title Page
Copyright and Credits
About Packt
Contributors
Preface
8
Stacks and Queues
10
Hashing and Symbol Tables
Index

Randomized selection


In the previous chapter, we examined the quick sort algorithm. The quick sort algorithm allows us to sort an unordered list of items but has a way of preserving the index of elements as the sorting algorithm runs. Generally speaking, the quick sort algorithm does the following:

  1. Selects a pivot.
  2. Partitions the unsorted list around the pivot.
  3. Recursively sorts the two halves of the partitioned list using step 1 and step 2.

One interesting and important fact is that after every partitioning step, the index of the pivot will not change even after the list has become sorted. It is this property that enables us to be able to work with a not-so-fully sorted list to obtain the ith-smallest number. Because randomized selection is based on the quick sort algorithm, it is generally referred to as quick select.

Quick select

The quick select algorithm is used to obtain the ith-smallest element in an unordered list of items, in this case, numbers. We declare the main method of the algorithm...