Data Structures and Algorithms in Swift: An Introduction

The goal of a software developer is to solve a problem in the most efficient way possible. Data Structures and Algorithms work hand-in-hand to help us achieve this goal; Data Structures store data, while algorithms solve problems using data. We will discuss linear data structures and the basics of algorithms.

What is a Data Structure?

A data structure is a method of storing and organising data in a specific format. Several operations can be performed on data structures which enable them to be used by algorithms. The common operations are:

• Sorting — The contents of a data structure can be sorted in ascending or descending order.
• Searching — Search through a data structure for a specific data element.
• Insertion — An element can be inserted into a data structure at a given position.
• Deletion — An element can be deleted from a data structure from a given position.
• Updation — An element in a data structure can be changed or updated to a new value.
• Traversion — Looping through a data structure to visit each of its elements.

Types of data structures

There are several types of data structures, but for this article, we will focus on linear data structures.

Linear data structures consist of data elements arranged in sequential order, allowing us to perform the operations mentioned above on them. Some examples of linear data structures are:

• Arrays — Store an ordered collection of elements of the same data type. An array can be sorted using the sort() method in swift. We can also update a specific element in an array by using its index.

// Creating an array of names
var names = ["John", "Steve", "Anushka", "Elizabeth", "Mark"]
// Using the sort() function
names.sort()
// The resulting array will look like this:
["Anushka", "Elizabeth", "John", "Mark", "Steve"]
// Updating "Elizabeth" element to be "Jennifer"
names[1] = "Jennifer"

• Sets — Store an unordered collection of elements of the same data type. Searching for a specific element in an array can be achieved using the contains() method in swift. We can also traverse through a set by using a for loop.

// Creating a set of names
var names: Set = ["Rosa", "Doug", "Waldo"]
// Searching through the set to see if it contains an element
print(names.contains("Lola")) 
// This prints false
// Traversing through set using for loop and printing each element
for name in names {
    print(name)
}

• Stacks — In this data structure, data elements can be added or removed at one end only. It can be thought of as a pile of elements. It follows a last in, first out (LIFO) protocol. The latest element added to a stack is the element which will be removed first. We can add an element to the top of a stack using the push() method.

// Creating stack data structure
struct Stack {
  var array: [Int] = []
  
// Implementing method to add elements to a stack
  mutating func push(_ element: Int) {
    array.append(element)
  }
}
// Initialising a stack object
var example = Stack()

// Adding an element (1) to the stack
example.push(1)

• Queues — Similar to a stack, data elements are removed or added at one end only. However, queues follow the first in, first out protocol (FIFO). The last element added to a stack is the element which will be removed first. We can delete the first element of a queue using the dequeue() method.

// Creating queue data structure
struct Queue {
  var array: [String] = ["Adam"]
// Implementing method to delete an element from a queue
  mutating func dequeue() -> String? {
    guard !array.isEmpty else {
        return nil
    }
    return array.removeFirst()
  }
}
// Initialising a queue object
var example = Queue()

// Deletes "Adam" element from queue
example.dequeue()

• Linked Lists — A data structure where elements are not stored at contiguous locations. Instead, the elements are linked using pointers to an address in memory. Data elements are stored in nodes, and each node is linked to the previous and next node, as depicted below.

What is an Algorithm?

An Algorithm is a sequence of steps to solve a particular problem. In simple terms, it may be thought of as a recipe. There are several types of algorithms:

• Brute Force Algorithm — A brute force algorithm is the simplest approach to a problem. It is the first approach to solving a problem. It is inefficient and is usually refined to improve performance.
• Recursive Algorithm — Recursion is a technique in which the solution to a problem is defined in terms of a simpler version of itself. The problem is broken down into smaller, simpler versions of itself. The problem is solved by a function calling itself repetitively. Solving for factorials is a common recursive problem:

// Function to find the factorial of a number  
func factorial(num: Int) -> Int {     
    // Base condition     
    if (num == 0 || num == 1) {
        return 1    
    } else {           
    // Recursive call, the function calling itself     
        return num * factorial(num: num - 1)     
    }  
}

• Sorting Algorithm — Sorting is arranging a list of data elements into a specific order by comparing elements. The algorithms which help in performing this function are called sorting algorithms. Sorting algorithms are commonly used to sort data elements in ascending or descending order.
• Searching algorithms — Searching is used for retrieving elements that fit a specific criteria from a data structure.
• Divide-and-Conquer Algorithm — This algorithm breaks a problem into smaller, simpler sub-problems. It solves a single sub-problem and merges the solutions to get the final solution. The sub-problems are divided and solved individually, and these solutions are combined to solve the overall problem.
• Dynamic Programming Algorithm — This technique is an optimised combination of the recursive and divide-and-conquer algorithms. It involves breaking a problem into sub-problems and saving the result for future purposes so that it does not need to be computed again.
• Greedy Algorithm — An approach for solving a problem by selecting the best option available. The optimal choice of solving a problem at each stage of the algorithm is made, and this decision is never reversed, even if the current best result will not bring the overall optimal result. This algorithm takes a top-down approach.
• Randomised Algorithm — A randomised algorithm uses randomised decisions to solve a problem. Unlike the algorithms mentioned above, it does not make deterministic decisions at each stage of the algorithm but makes arbitrary decisions instead.

Asymptotic analysis is used to determine the efficiency of an algorithm so that it may be compared to other algorithms. It measures an algorithm's efficiency and computational time as its input size grows. We use Big O Notation to classify algorithms according to their complexity. For example:

• If an algorithm solves a problem in constant time (it takes the same time to solve a problem regardless of the input data size), then we say it solves the problem in O(1) (order 1) time.
• If the time it takes an algorithm to solve a problem increases linearly as its input data size increases, then we say it solves the problem in O(N) (order N) time, with N being the input data size.
• If the time it takes an algorithm to solve a problem increases quadratically as its input data size increases, then we say it solves the problem in O(N²) (order N²) time, with N being the input data size.

Graph illustrating different algorithmic complexities

Asymptotic analysis of an algorithm is performed by testing three cases:

• Best Case Scenario — A scenario in which the algorithm performs the best and takes the least amount of time to solve the problem.
• Worst Case Scenario — A scenario in which the algorithm performs the worst and takes the most amount of time to solve the problem.
• Average Case Scenario — The average time it takes for the algorithm to solve the problem given different data sizes.

We will use the linear searching algorithm to illustrate asymptotic analysis of an algorithm.

The linear search algorithm searches through an array of integers and returns the index of the specific integer that we would like to search.

func linearSearch(_ array: [Int], _ object: Int) -> Int? {
// Looping through the array from beginning to end
for (index, obj) in array.enumerated() where obj == object {
    return index
  }
  return nil
}

• Best Case Scenario — The best case of the linear search algorithm would be if the element that we are searching for is the first element in the array. The algorithm would always return the first element of the array in this case, hence the size of the array will not impact the time it takes for the algorithm to search for the element. Therefore, the complexity of the linear search algorithm in the best case is O(1).
• Worst Case Scenario — The worst case of the linear search algorithm would be if the element that we are searching for is the last element in the array. The algorithm would always return the last element of the array in this case, hence the time it takes the algorithm to search for the element would be relative to the size of the array. Therefore, the complexity of the linear search algorithm in the worst case is O(N), with N being the size of the array.
• Average Case Scenario — On average, the linear search algorithm needs to loop through half of the elements in the array. The complexity of the linear search algorithm in the average case would be O(N/2), with N being the size of the array. However, if we consider very large array sizes, halving N would not majorly impact the time it takes to solve the problem. Therefore, the complexity of the linear search algorithm in the average case is O(N).