#### Overview of this book

Explore a new world of data structures and their applications easily with this data structures book. Written by software expert William Smith, you?ll learn how to master basic and advanced data structure concepts. ? Fully understand data structures using Java, C and other common languages ? Work through practical examples and learn real-world applications ? Get to grips with data structure problem solving using case studies
Everyday Data Structures
Credits
www.PacktPub.com
Customer Feedback
Preface
Free Chapter
Data Types: Foundational Structures
Arrays: Foundational Collections
Lists: Linear Collections
Stacks: LIFO Collections
Queues: FIFO Collections
Dictionaries: Keyed Collections
Sets: No Duplicates
Structs: Complex Types
Trees: Non-Linear Structures
Heaps: Ordered Trees
Graphs: Values with Relationships
Sorting: Bringing Order Out Of Chaos
Searching: Finding What You Need

## Insertion sort

An insertion sort is a very simple algorithm that looks at an object in a collection and compares its key to the keys prior to itself. You can visualize this process as how many of us order a hand of playing cards, individually removing and inserting cards from left to right in ascending order.

For example, consider the case of ordering a collection in ascending order. An insertion sort algorithm will examine an object at index i and determine if it's key is lower in value or priority than the object at index i - 1. If so, the object at i is removed and inserted at i - 1. At this point, the function will repeat and continue to loop in this manner until the object key at i - 1 is not lower than the object key at i.

Given the following set of values:

S = {50, 25, 73, 21, 3}

Our algorithm will begin examining the list at i = 1. We do this because at i = 0, i - 1 is a non-existent value and would require special handling.

Since 25 is less than 50, it is removed and reinserted at i...