Data Structures & Algorithms in Swift Updated for Swift 4.2

Section IV: Sorting Algorithms

• Chapter 26: O(n²) Sorting Algorithms: O(n²) time complexity is not great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. These algorithms are space efficient; they only require constant O(1) additional memory space. In this chapter, you’ll be looking at the bubble sort, selection sort, and insertion sort algorithms.us shapes and sizes.
• Chapter 28: Merge Sort: In this chapter, you’ll look at a completely different model of sorting. So far, you’ve been relying on comparisons to determine the sorting order. Radix sort is a non-comparative algorithm for sorting integers in linear time. There are multiple implementations of radix sort that focus on different problems. To keep things simple, in this chapter you’ll focus on sorting base 10 integers while investigating the least significant digit (LSD) variant of radix sort.
• Chapter 30: Radix Sort: A binary search tree facilitates fast lookup, addition, and removal operations. Each operation has an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.
• Chapter 32: Heapsort: Heapsort is another comparison-based algorithm that sorts an array in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 21, “The Heap Data Structure.” Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree.
• Chapter 34: Quicksort: Quicksort is another divide and conquer technique that introduces the concept of partitions and a pivot to implement high performance sorting. You‘ll see that while it is extremely fast for some datasets, for others it can be a bit slow.

Real-world examples help you apply the book’s concepts in a concrete and relevant way!

Real-world examples help you apply the book’s concepts in a concrete and relevant way!

Section V: Graphs

• Chapter 36: Graphs: What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs! A graph is a data structure that captures relationships between objects. It is made up of vertices connected by edges. In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. This lets you choose the cheapest or shortest path between two vertices.
• Chapter 38: Breadth-First Search: In the previous chapter, you explored how graphs can be used to capture relationships between objects. Several algorithms exist to traverse or search through a graph’s vertices. One such algorithm is the breadth-first search algorithm, which can be used to solve a wide variety of problems, including generating a minimum spanning tree, finding potential paths between vertices, and finding the shortest path between two vertices.
• Chapter 40: Depth-First Search: In the previous chapter, you looked at breadth-first search where you had to explore every neighbor of a vertex before going to the next level. In this chapter, you will look at depth-first search, which has applications for topological sorting, detecting cycles, path finding in maze puzzles, and finding connected components in a sparse graph.
• Chapter 42: Dijkstra’s Algorithm: Have you ever used the Google or Apple Maps app to find the shortest or fastest from one place to another? Dijkstra’s algorithm is particularly useful in GPS networks to help find the shortest path between two places. Dijkstra’s algorithm is a greedy algorithm, which constructs a solution step-by-step, and picks the most optimal path at every step.
• Chapter 44: Prim’s Algorithm: In previous chapters, you’ve looked at depth-first and breadth-first search algorithms. These algorithms form spanning trees. In this chapter, you will look at Prim’s algorithm, a greedy algorithm used to construct a minimum spanning tree. A minimum spanning tree is a spanning tree with weighted edges where the total weight of all edges is minimized. You’ll learn how to implement a greedy algorithm to construct a solution step-by-step, and pick the most optimal path at every step.

The book moves beyond fundamentals to more advanced concepts, such as Dijkstra’s Algorithm!

The book moves beyond fundamentals to more advanced concepts, such as Dijkstra’s Algorithm!

Data Structures and Algorithms in Swift will teach you how to implement the most popular and useful data structures, and when and why you should use one particular data structure or algorithm over another.

This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs. And the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

About the Authors

Kelvin Lau is a physicist turned Swift-iOS Developer. While he’s currently entrenched with iOS development, he often reminisces of his aspirations to be part of the efforts in space exploration. Outside of programming work, he’s an aspiring entrepreneur and musician. You can find him on Twitter: @kelvinlauKL.

Vincent Ngo is a software developer by day, and an iOS-Swift enthusiast by night. He believes that sharing knowledge is the best way to learn and grow as a developer. Vincent starts every morning with a homemade green smoothie in hand to fuel his day. When he is not in front of a computer, Vincent is training to play in small golf tournaments, doing headstands at various locations while on a hiking adventure, or looking up how to make tamago egg. You can find him on Twitter: @vincentngo2.

Part of the iOS 12 Launch Bundle

So many of you have asked for a book bundle to go with the iOS 12 update season, and we’re happy to announce the release of the iOS 12 Launch Party Bundle!

This three-book bundle contains our newest iOS 12 books:

• Advanced iOS App Architecture
• Machine Learning by Tutorials
• Push Notifications by Tutorials

This bundle is on sale for only $99.99 — that’s a savings of 33%! But don’t wait, since this bundle won’t be available forever.

Where To Go From Here?

Data Structures and Algorithms in Swift, Second Edition, is now 100% complete, fully updated for Swift 4.2 and Xcode 10, and it’s available today.

• If you’ve already bought Data Structures & Algorithms in Swift digital edition, you can log in to the store and download the updated version here.
• If you haven’t already bought this must-have addition to your development library, head over to our store page to grab your copy today!

And to help sweeten the deal, the digital edition of the book is on sale for $44.99! But don’t wait — this sale price is only available for a limited time.

Speaking of sweet deals, be sure to check out the great prizes we’re giving away this year with the iOS 12 Launch Party, including over $9,000 in giveaways!

To be eligible for for this epic iOS 12 giveaway, all you have to do is leave a comment on the original launch post, letting us know which book or course is your favorite on this list — or which upcoming book or course you’re most excited about!

We hope you enjoy this free update, and stay tuned for more book releases and updates coming soon!